1
$\begingroup$

I'm trying to prove the following problem:

$p$ is a prime iff for all $n\in \mathbb{Z}$ with $n\not \equiv 0\mod p$, we have $n^{p-1}\equiv 1 \mod p$.

The ($\Rightarrow$) direction is easy: we have that if $p$ is a prime, then $n\not \equiv 0\mod p$ is equivalent to $(n,p)=1$, and then we use the Fermat's little theorem.

I'm having trouble with the second direction: I've read that the Fermat's little theorem have a converse (Lehmer's theorem) that changes slightly the hypothesis but I don't if it's useful for my problem and how can I use it.

$\endgroup$
  • $\begingroup$ I'm assuming that where you wrote $n$ you wanted to write $n$ $\endgroup$ – PenasRaul Oct 3 '14 at 17:31
  • $\begingroup$ Apart from the uninteresting counterexample $n=1$, the other direction is even easier. The interesting question comes when we restrict to $a$ relatively prime to the modulus. For such matters, which are not needed to answer your question, please look at Wikipedia, Carmichael Numbers. $\endgroup$ – André Nicolas Oct 3 '14 at 17:33
  • $\begingroup$ @PenasRaul: I'm assuming that where you wrote "I'm assuming that where you wrote $n$ you wanted to write $n$" you wanted to write "I'm assuming that where you wrote $a$ you wanted to write $n$". $\endgroup$ – TonyK Oct 3 '14 at 17:46
  • $\begingroup$ The question is fixed. Thanks @PenasRaul for the answer. Yes, the problem has a second part that ask about if we can change the hypothesis and use $(n,p)=1$ instead of modulus, so I used the Carmichael Numbers there. $\endgroup$ – jiyanez Oct 3 '14 at 17:47
  • $\begingroup$ You assumed correctly, my apologies $\endgroup$ – PenasRaul Oct 3 '14 at 18:19
0
$\begingroup$

The other implication, you assume $p$ is not prime, you just have to take a non trivial divisor of $p$, $n$ and then for sake of contradiction assume $n^{p-1}\equiv_p 1$, then $ n \mid p \mid n^{p-1} - 1 $, so $n \mid 1$ contradiction to $n$ be non trivial divisor.

$\endgroup$
0
$\begingroup$

Remark: $p$ is prime iff $(p,k)=1$ for all $k$ s.t $1<k<p$.

Let $k$ s.t $1<k<p$, then by hypothesis we have $k^{p-1}\equiv 1$ mod $p$, hence there exists $m\in \Bbb Z$ s.t $k^{p-1}=1+mp$, so $k.k^{p-2}+(-m)p=1$, by Bezout theorem we get $(k,p)=1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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