# Prove n is prime (linked to Fermats little theorem)

• April 10th 2010, 01:08 PM
Prove n is prime (linked to Fermats little theorem)
Show that $n$ is prime iff $a^{n-1}$ $1( \textrm{mod} n)$ for $1 \leq a \leq n-1$.

=> Fermats little theorem.

<= (Wondering)

Perhaps show that $\phi(n) = n-1$ but if this is the case I would need a way to start.
• April 10th 2010, 01:12 PM
FancyMouse
Quote:

Show that $n$ is prime iff $a^{n-1}$ $1( \textrm{mod} n)$ for $1 \leq a \leq n-1$.

=> Fermats little theorem.

<= (Wondering)

Perhaps show that $\phi(n) = n-1$ but if this is the case I would need a way to start.

<= FALSE. Smallest counterexample: 561. Such numbers are called Carmichael numbers.
• April 10th 2010, 01:14 PM
Quote:

Originally Posted by FancyMouse
<= FALSE. Smallest counterexample: 561. Such numbers are called Carmichael numbers.

Well well I now hate my lecturer for making me spend all night on a trick question...
• April 10th 2010, 01:23 PM
Quote:

Originally Posted by FancyMouse
<= FALSE. Smallest counterexample: 561. Such numbers are called Carmichael numbers.

Hold on did you notice the $1 \leq a \leq n-1$ condition? Does it still not hold.
• April 10th 2010, 01:29 PM
Quote:

Originally Posted by FancyMouse
<= FALSE. Smallest counterexample: 561. Such numbers are called Carmichael numbers.

I'm pretty sure this is wrong now.

$3^{560}$ is not equivalent to 1 mod 561 for example. It does not hold for all $a \in [1 \dots n-1]$
• April 10th 2010, 04:43 PM
Bacterius
Generally,
$\Rightarrow$ if $p$ is prime, then $a^{p - 1} \equiv 1 \pmod{p}$ for any $a$ such as $\gcd{(a, p)} = 1$.

$\Rightarrow$ if $a^{p - 1} \equiv 1 \pmod{p}$ for any $a$ such as $\gcd{(a, p)} = 1$, then $p$ is likely to be prime (Carmichael numbers are the only numbers that do not satisfy the statement, they are relatively rare but their existence invalidates the statement).
• April 10th 2010, 05:14 PM
Quote:

Originally Posted by Bacterius
Generally,
$\Rightarrow$ if $p$ is prime, then $a^{p - 1} \equiv 1 \pmod{p}$ for any $a$ such as $\gcd{(a, p)} = 1$.

$\Rightarrow$ if $a^{p - 1} \equiv 1 \pmod{p}$ for any $a$ such as $\gcd{(a, p)} = 1$, then $p$ is likely to be prime (Carmichael numbers are the only numbers that do not satisfy the statement, they are relatively rare but their existence invalidates the statement).

Right. I'm kinda getting a bit mixed up on whether my question is actually true (i.e, is it an 'iff' question or just an 'if' question)...

The counter example given was 561 but the problem as I understand it is...

If $a^{n-1} \equiv 1 \textrm{ mod } n$ for all $1 \leq a \leq n-1$, then $n$ is prime.

But this is not true for 561.

$3^{560} = 375$ mod 561. Hence 561 does not satisfy the above... What am I missing here? It holds true for may primes that I have tested using Maple leading me to believe that the part I'm stuck on can be proved.
• April 10th 2010, 06:51 PM
Bacterius
The original statement is wrong. It is not an "iff" condition because you found a counter-example with 561.

The statement is valid if and only if n is a prime OR a Carmichael number.
• April 11th 2010, 01:03 AM
Quote:

Originally Posted by Bacterius
The original statement is wrong. It is not an "iff" condition because you found a counter-example with 561.

The statement is valid if and only if n is a prime OR a Carmichael number.

Ok look. I get what iff means but 561 is not a counter example.

For 561 to be a counter example then for every $a \in [1 \dots 560]$, $a^{560} \equiv 1$ mod 561.

But after running it through in Maple you can show that for many values for a
$a^{560}\neq 1$ mod 561. (don't know the Latex for not equivalent)

Hence 561 is not prime.
• April 11th 2010, 02:38 PM
FancyMouse
Quote:

I'm pretty sure this is wrong now.

$3^{560}$ is not equivalent to 1 mod 561 for example. It does not hold for all $a \in [1 \dots n-1]$

So then everything in [1,n-1] is relatively prime to n indicates that n does not have a divisor there. So OP's statement is true in that sense, which is trivial to prove, but way less meaningful than the existence of Carmichael numbers.
• April 17th 2010, 03:27 PM
Ok folks, I'm back.

Hopefully with an understanding.

It seems perhaps the proof wasn't so complicated as I first thought...

=> Fermat's little theorem. (since all a in this example are coprime to p if p is prime)

<= If $a^{n-1} \equiv 1 \textrm{ (mod } p) \, \textrm{for } 1 \leq a < n$, all a are coprime to p, hence p has no divisors and so is prime.

Is that all it is?
• April 17th 2010, 05:19 PM
Drexel28
Quote:

$\not\equiv$