# question about primitive roots modulo p

I know that every group of units $\bmod p$ has a generator, in fact $\varphi(p-1)$ of them.

I came across a problem that asked to prove that for such a generator, let's call it $a$ (but see below), and $p$ an odd prime:

$$a^{p-1} = 1 + kp$$

where $\gcd(k,p) = 1$

It's the last part that is killing me. I can see that $p$ divides $a^{(p-1)/2} + 1$, since it cannot divide $a^{(p-1)/2} - 1$ (this would contradict that $a$ is a generator), but I have no idea how to show that $p^2$ does not divide $a^{(p-1)/2} + 1$.

Any ideas?

EDIT: The answer turned out to be simple (I thought it might be). If it turns out that k and p are not co-prime, replace a with a+p. My apologies for stating the problem incorrectly, as the original problem asked to find an a such that [a] was a generator.

-
In other words, the problem asked you to prove that there exists a generator $a$ with that property? Very different! And perhaps you might state the corrected problem before writing what "the solution" was? –  Arturo Magidin Feb 18 '12 at 2:50
Downvote for not taking the trouble to get the question right before posting. –  Gerry Myerson Feb 18 '12 at 5:17
My apologies Gerry, but your original answer to my original question was most helpful. I asked what I wanted to know, and I did not feel obligated to say "why". Knowing your response enabled me to re-think my strategy, and if I had to do it all over again, I wouldn't do anything differently. –  David Wheeler Mar 3 '12 at 18:58

There are examples of odd primes $p$ and generators $a$ for the group of units modulo $p$ such that $p^2$ divides $a^{p-1}-1$, so if the problem is as you say it is, it is asking the impossible. See, for example, http://mathoverflow.net/questions/27579/is-the-smallest-primitive-root-modulo-p-a-primitive-root-modulo-p2

-
But that was answering a much more difficult question, for which $a$ was required to be the smallest positive integer that is a primitive root modulo $p$. –  Derek Holt Feb 18 '12 at 4:33
@Derek, yes, and surely there are easier-to-find examples of $a$ and $p$ such that $a$ is a primitive root mod $p$ and $a^{p-1}\equiv1\pmod{p^2}$, but I knew where to find this one so I posted it. –  Gerry Myerson Feb 18 '12 at 5:15

Suppose that $a^{(p-1)} = 1 + kp^2$ for some integer $k$. That would imply that $a$ fails to generate the multiplicative group of units modulo $p^2$. But is that actually unlikely?

In fact, there are integers which are coprime to p, which do not generate the units modulo p2, because raising them to the p−1 power gives you 1 (mod p2.

We have p=2q+1 for every odd prime; and your original question then amounts to showing that −1 has no qth root in the integers mod p2. So for p=3, for example, this is obviously false; 8 is a "1st root" of itself, and so is a counterexample to the original statement. More generally, one can find counterexamples by searching for integers $0 < a < p^2$ such that $a^q \equiv -1 \pmod{p^2}$.

-
@anon: a counterexample to the claim in the question: that for any $a$ which generates the multiplicative group of units modulo $p$, that $a^{p-1} \not\equiv 1 \pmod{p^2}$. –  Niel de Beaudrap Feb 17 '12 at 11:56
could you elucidate a bit further? when you say "counterexample" do you mean if p = 1 (mod 4) there IS such a primitive element a that fails to generate the units mod $p^2$? Because it's the counterexamples I'm actually looking for, but if I understand you correctly, that still leaves me high and dry for p = 3 (mod 4). –  David Wheeler Feb 17 '12 at 19:58