Show that is prime iff ≡ for .

=> Fermats little theorem.

<= (Wondering)

Perhaps show that but if this is the case I would need a way to start.

Printable View

- Apr 10th 2010, 02:08 PMDeadstarProve n is prime (linked to Fermats little theorem)
Show that is prime iff ≡ for .

=> Fermats little theorem.

<= (Wondering)

Perhaps show that but if this is the case I would need a way to start. - Apr 10th 2010, 02:12 PMFancyMouse
- Apr 10th 2010, 02:14 PMDeadstar
- Apr 10th 2010, 02:23 PMDeadstar
- Apr 10th 2010, 02:29 PMDeadstar
- Apr 10th 2010, 05:43 PMBacterius
Generally,

if is prime, then for any such as .

if for any such as , then 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). - Apr 10th 2010, 06:14 PMDeadstar
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 for all , then is prime.

But this is not true for 561.

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. - Apr 10th 2010, 07:51 PMBacterius
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. - Apr 11th 2010, 02:03 AMDeadstar
(Headbang)

Ok look. I get what iff means but 561 isa counter example.*not*

For 561 to be a counter example then for**every**, mod 561.

But after running it through in Maple you can show that for many values for a

mod 561. (don't know the Latex for not equivalent)

Hence 561 is not prime. - Apr 11th 2010, 03:38 PMFancyMouse
- Apr 17th 2010, 04:27 PMDeadstar
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 , all a are coprime to p, hence p has no divisors and so is prime.

Is that all it is? - Apr 17th 2010, 06:19 PMDrexel28