Thread: If a has order n - 1 modulo n, then n is prime.

I'm stuck on this question. Prove that if a has order n - 1 modulo n, then n is prime.

So this means a^(n-1) is congruent to 1 (mod n). This looks exactly like Fermat's Theorem for primes but I'm not sure how to prove that n is prime. I tried contradiction but am getting nowhere. Hints please. Thank you.

Originally Posted by mathguy71421

I'm stuck on this question. Prove that if a has order n - 1 modulo n, then n is prime.

So this means a^(n-1) is congruent to 1 (mod n). This looks exactly like Fermat's Theorem for primes but I'm not sure how to prove that n is prime. I tried contradiction but am getting nowhere. Hints please. Thank you.

Let be composite.





Clearly, - Contradiction!

Ah Thank you so much. I figured that phi(n) =/= n - 1 but couldn't quite connect that to a contradiction in my head. Thanks so much.