I'm trying to write a general proof. I know that if $k=3$ then I have to show that there are no primitive roots modulo 8, and this is given because $8$ has residues $1,3,5,7$; and $ord_8(1)=1, ord_8(3)=2, ord_8(5)=2, ord_8(7)=2$, none of which is $\phi(8)=4$.

A proof I in a textbook said that it can be proved by induction that $a^{2^{k-2}}\equiv 1 \pmod {2^k}$ for all odd numbers $a$ .

I have two questions: (1) What happens if $a$ is even? Why the proof wouldn't work if $a$ is even?; (2) Why is the exponent of $a$ $2^{k-2}$? Is it because it has to be a quadratic nonresidue?

The proof continues: $a^{2^{k-2}}\equiv 1 \pmod {2^k}$, then $a^{2^{k-2}}=1+b2^k$, and squaring both sides $a^{2^{k-1}}=1+b2^{k+1}+b^22^{2k+1}$, then $a^{2^{k-1}}\equiv 1 \pmod {2^{k+1}}$.

I understand why is the formula proved, but I don't understand is how this helps to show that there is no $a$ such that $a^k\equiv 1 \pmod {2^k}$ in general.

  • $\begingroup$ If $a$ is even then no non-zero power of $a$ can be $\equiv 1\pmod 2$. $\endgroup$
    – lulu
    Sep 13, 2016 at 12:37

1 Answer 1


First question: If $a$ is even, it's not relatively prime to the modulus. The induction argument fails because the basis step $a\equiv 1 \mod{2}$ doesn't hold.

Second question: If the exponent were $n-1$, then the order of $a$ might still be $\phi(2^n) = 2^{n-1}$. If we prove the exponent is smaller, then we know for sure that $a$ can't have order $\phi(2^n)$ and so it can't be a primitive root.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.