# Prove that number is a primitive root for all $k$ in range

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?

## 1 Answer

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: $$$$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}$$$$ 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: $$$$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$$$$ 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.

• How do we get $u^{p-2}+\dots+v^{p-2} \equiv (p-1)u$ (mod $p$)? – Kristin Petersel Apr 29 '19 at 8:16
• I am sorry. It is congruent to $(p-1)u^{p-1}$. It is still coprime with p, and the conclusion still holds. – JPaucar Apr 29 '19 at 21:19
• 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 :). – JPaucar Apr 29 '19 at 22:15