Let $a$ be a primitive root for $p > 2$ where $p$ is prime. Show that $a^p+kp$ for $k = 1,\dots,p-1$ are $p-1$ distinct primitive roots modulo $p^2$.

What I have done:

First of all it is easy to see that by Fermat' Little Theorem $a^p+kp \equiv a + kp \equiv a$ (mod $p$), so all of these are primitive roots modulo $p$. Next we would need to see that these are primitive roots modulo $p^2$ as well. For this we would need to see that $(a^p+kp)^{p-1} \not\equiv 1$ (mod $p^2$). I have tried to do this using Newton binomial but I haven't been able to do so. Also we would somehow need to show that for all $k$ the primitive root is distinct so $a^p + k_1p \not\equiv a^p + k_2p$ (mod $p^2$). Any suggestions on how to proceed?


Claim: $(a^p+kp)^{p-1} \not \equiv 1 \pmod {p^2}$, when $a$ is primitive root$\mod p$ and $k \in \{1,2,\ldots,p-1\}$.

Let's denote $u= a^p+kp$ and $v = a^p$. Then, by Euler's theorem $v^{p-1}\equiv 1 \pmod{p^2}$ so the claim is equivalent to $p^2\nmid u^{p-1}- v^{p-1}$. However, we also have that: \begin{equation} u^{p-1}- v^{p-1} = (u-v)(u^{p-2}+u^{p-3}v^1+\ldots+u^{1}v^{p-3}+v^{p-2}) \label{a} \end{equation} Moreover $u-v=pk$, so $u\equiv v\pmod p$, this implies that the second factor in right hand side of the above equality is coprime with $p$. This is so because: \begin{equation} u^{p-2}+u^{p-3}v^1+\ldots+u^{1}v^{p-3}+v^{p-2}\equiv (p-1)u^{p-2}\mod p \end{equation} Then if $p^2| u^{p-1}- v^{p-1}$, as that second term is coprime with $p$, we would have that $p^2|u-v = kp$ which is impossible. Then $p^2\nmid u^{p-1}- v^{p-1}$. Which implies the claim and what you want (The order of $u$ would have to be divided by $p$ and $p-1$).

About the second part, you just need to note that $p^2 | (a^p+k_1p) - (a^p+k_2p)$ implies that $p^2|(k_1-k_2)p$ and that if $p|k_1-k_2$ this implies $k_1 = k_2$.

Apologies for all the mistakes, I just saw that you could just do it with Newton's Binomial, I didn't realize that at the time I wrote this xD.

You should still check out LTE(Lifting the exponent Lemma), it is a popular trick in high school olympiads that gives you more information than what I just used http://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvYy82LzdjNTI1OGIyMmNjYmZkZGY4MDhhY2ViZTc3MGE1NDRmMzFhMTEzLnBkZg==&rn=TGlmdGluZyBUaGUgRXhwb25lbnQgTGVtbWEgLSBBbWlyIEhvc3NlaW4gUGFydmFyZGkgLSBWZXJzaW9uIDMucGRm.

  • $\begingroup$ How do we get $u^{p-2}+\dots+v^{p-2} \equiv (p-1)u$ (mod $p$)? $\endgroup$ – Kristin Petersel Apr 29 '19 at 8:16
  • $\begingroup$ I am sorry. It is congruent to $(p-1)u^{p-1}$. It is still coprime with p, and the conclusion still holds. $\endgroup$ – JPaucar Apr 29 '19 at 21:19
  • $\begingroup$ I meant $u^{p-2}$. Note that $u^iv^{p-2-i}$ is congruent with $u^{p-2}$ mod $p$ because $u$ is congruent with $v$ mod $p$. I will edit the post when I get home. It is hard to write on the cellphone :). $\endgroup$ – JPaucar Apr 29 '19 at 22:15

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.