I need help with the following: Show that if $b$ is a primitive root modulo $m$, then $$\{b,b^2,b^3,...,b^m-1\}$$ is a complete set of units modulo $m$.
Asked
Active
Viewed 272 times
1
-
How is $p$ related to $m$? – André Nicolas Oct 12 '13 at 00:31
-
Sorry, that was a typo, I fixed it. – Benji_Bombadill Oct 12 '13 at 00:32
-
1What is your definition of primitive root? – Pedro Oct 12 '13 at 00:32
-
1I think you want $m$ to be prime. – Pedro Oct 12 '13 at 00:33
-
1If $m$ is not prime, then although your set indeed lists all members of the multiplicative group, there are some repetitions. – André Nicolas Oct 12 '13 at 00:39
-
Yes, m would be a prime. A primitive would be an integer b s.t. {0,b,b^2,...,b^m-1} a complete set of representatives for Z/mZ. I believe I'm meant to write a proof for the primitive root theorem. – Benji_Bombadill Oct 12 '13 at 00:39
-
Primitive roots exist for precisely $1,2,4$ and powers of odd primes. But they are of serious interest mainly for primes. – André Nicolas Oct 12 '13 at 01:00
1 Answers
3
If we define a primitive root as an element with order $\varphi(m)$ modulo $m$, then we can prove as follows. Each power $b^i$ is coprime to $m$, and there are $\varphi(m)$ integers coprime to $m$. Now, if $b^i\equiv b^j\pmod{m}$, then $b^{i-j}\equiv 1\pmod{m}$, so $\varphi(m)|i-j$. It follows that each of the powers are distinct modulo $m$, and thus each integer relatively prime to $m$ is some power $b^i$ modulo $m$.
tc1729
- 3,017