Primitive root modulo n

In modular arithmetic, a number g is a primitive root modulo n, if every number m from 1..(n-1) can be expressed in the form of [math]\displaystyle{ g^x\equiv m \pmod n }[/math]. As an example, 3 is a primitive root modulo 7:

[math]\displaystyle{ 3^1 \equiv 3\ \pmod 7 }[/math]

[math]\displaystyle{ 3^2 \equiv 2\ \pmod 7 }[/math]

[math]\displaystyle{ 3^3 \equiv 6\ \pmod 7 }[/math]

[math]\displaystyle{ 3^4 \equiv 4\ \pmod 7 }[/math]

[math]\displaystyle{ 3^5 \equiv 5\ \pmod 7 }[/math]

[math]\displaystyle{ 3^6 \equiv 1\ \pmod 7 }[/math]

All the elements [math]\displaystyle{ 1, 2, \ldots, 6 }[/math] of the group modulo 7 can be expressed that way. The number 2 is no primitive root modulo 7, because

[math]\displaystyle{ 2^3=8 \equiv 1 \pmod 7 }[/math]

and

[math]\displaystyle{ 2^6=64 \equiv 1 \pmod 7 }[/math]