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
    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?2012-02-18
  • 0
    Downvote for not taking the trouble to get the question right before posting.2012-02-18
  • 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