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

Question

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?

Answer 1

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.