Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.