6
$\begingroup$

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.

  • 0
    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.2012-03-03

2 Answers 2

3

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, https://mathoverflow.net/questions/27579/is-the-smallest-primitive-root-modulo-p-a-primitive-root-modulo-p2

  • 0
    @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.2012-02-18
2

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

  • 0
    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).2012-02-17