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

$\displaystyle \phi(n)<n-1$

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

Clearly, $\displaystyle 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.

,

,

,

order n-1 modulo n then n is prime

Click on a term to search for related topics.