Let $a$ be a primitive root modulo odd prime. Show that in an arithmetic progression $a+kp$, where $k = 0,1,\dots,p-1$ there is exactly one number that is NOT a primitive root modulo $p^2$.

It is obvious that all of these are congruent to $a$ modulo $p$ so they are all primitive roots modulo $p$. To show that all but one are primitive roots modulo $p^2$ as well we would need to see that $(a+kp)^{p-1} \equiv 1$ (mod $p^2$) for exactly one value of $k$. I tried to do so using the Newton binomial but right now have failed to do so? Any suggestions?

  • 1
    $\begingroup$ $(\Bbb{Z/p^2 Z})^\times$ is a group with $p(p-1)$ elements, thus it contains an element $b=c+dp$ of order $p$, reducing modulo $p$ means $c=1$. Whence $(1+dp)^m a^n$ is of order $\frac{p}{gcd(m,p)}\frac{p-1}{gcd(n,p-1)}$. Note you can take $da \equiv 1 \bmod p, (1+d p)^m = 1+dmp\bmod p^2,(1+dp)^m a= a+damp=a+mp\bmod p^2$. $\endgroup$ – reuns Apr 29 at 8:14
  • 1
    $\begingroup$ math.stackexchange.com/questions/227199/… $\endgroup$ – lab bhattacharjee Apr 29 at 9:43

Your Answer

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

Browse other questions tagged or ask your own question.