Proof That Moduli 2^k Have No Primitive Roots
For any
\[k \ge 3\]
, \[2^k\]
does not have a primitive root.Proof
\[\phi (2^k)=2^{k-1}\]
where \[\phi\]
is Euler's Totient Function. The \[2^{k-1}\]
positive integers which are relatively prime to \[2^k\]
are just the odd positive integers less than \[2^k\]
. We have to show that for any odd integer \[a\]
there exists a positive integer \[r \lt 2^{k-1}\]
such that \[a^r \equiv 1 \; (mod \; 2^k)\]
. \[r^{k-2}\]
has this property for every value of \[a\]
.Let
\[P(k)\]
be the proposition \[a^{2^{k-2}} \equiv 1 \; (mod \; 2^k ), \; gcd(a,2)=1\]
. \[P(3)\]
is correct since \[a^2 \equiv 1 \; (nod \; 2^3=8)\]
for odd \[a\]
. Suppose then that \[P(m)\]
is true for \[m \gt 3\]
. Then \[a^{m-2}=1+2^mt\]
for some integer \[t\]
.\[\begin{equation} \begin{aligned} (a^{m-2})^2 &=(1+2^mt)^2 \\ &= 1 +2(2^mt)+(2^mt)^2 \\ &= 1+2^{m+1}(t+t^22^{m-1}) \\ & \equiv 1 \; (mod \; 2^{m+1}) \end{aligned} \end{equation}\]
Hence
\[a^{2^{m-1}} \equiv 1 \; (mod \; 2^{m+1})\]
, confirming \[P(m+1)\]
. 
