Prove n is prime (linked to Fermats little theorem)

**Deadstar** · April 10th 2010, 01:08 PM

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

=> Fermats little theorem.

<=

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

**FancyMouse** · April 10th 2010, 01:12 PM

Originally Posted by Deadstar

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

=> Fermats little theorem.

<=

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.

**Deadstar** · April 10th 2010, 01:14 PM

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

**Deadstar** · April 10th 2010, 01:23 PM

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.

**Deadstar** · April 10th 2010, 01:29 PM

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]$

**Bacterius** · April 10th 2010, 04:43 PM

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).

**Deadstar** · April 10th 2010, 05:14 PM

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.

**Bacterius** · April 10th 2010, 06:51 PM

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.

**Deadstar** · April 11th 2010, 01:03 AM

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.

**FancyMouse** · April 11th 2010, 02:38 PM

Originally Posted by Deadstar

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.

**Deadstar** · 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?

**Drexel28** · April 17th 2010, 05:19 PM

Originally Posted by Deadstar

(don't know the Latex for not equivalent)

$\not\equiv$

Thread: Prove n is prime (linked to Fermats little theorem)

LinkBack

Thread Tools

Display

Prove n is prime (linked to Fermats little theorem)

Similar Math Help Forum Discussions

Use EVT and Fermats to prove there is a c such that f'(c)=0

New approach to Fermats Last theorem for the prime powers of n

Fermats Little Theorem

Prime problem, Fermats little theorem?

Fermats Last Theorem

Search Tags