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

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

2. ## Re: If a has order n - 1 modulo n, then n is prime.

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 $n$ be composite.

$\phi(n)

$O_n(a) | \phi(n)$

Clearly, $O_n(a)\neq n-1$ - Contradiction!

3. ## Re: If a has order n - 1 modulo n, then n is prime.

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.