Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $x^{n-1} \equiv 1 \pmod{n}$, and for all divisors $q$ of $n - 1$, $a^{q} \not\equiv 1 \pmod{n}$, then $n$ is prime. $(n > 1)$

I read the proof in the book and it was very straightforward; however, I wonder is there a way to prove it by just using congruence property?

And another related question about power residue:
If we have $a^{n - 1} \equiv 1 \pmod{n}$. Is there any relation between $n - 1$ and $\phi(n)$? Because I thought of $a^{\phi(n)} \equiv 1 \pmod{n}$, when $(a, n) = 1$. I try to think of away to connect these two ideas, but I still cannot see it.
Any idea?


share|cite|improve this question
up vote 0 down vote accepted

HINT $\ \ $ The conditions imply that the order $\rm\:k\:$ of $\rm\:x\:$ is a divisor of $\rm\:n-1\:$ but not a proper divisor, therefore $\rm\: k = n-1\:.\ $ By Euler, $\rm\ k\ |\ \phi(n)\ $ so $\rm\ n-1\: \le\: \phi(n)\:.\ $ This implies that $\rm\:n\:$ is prime, since $\rm\ \phi(n) \:\le\: n-\color{red}{2}\ $ for composite $\rm\:n\:,\:$ since they have at least $\:\color{red}2\ $ smaller naturals non-coprime to $\rm\:n\:.$

share|cite|improve this answer
When you say order $k$ of $x$, do you mean $ord_{k}x$? – Chan Mar 10 '11 at 6:44
@Chan: $\rm\ mod\ n\::\ k\ $ is the order of $\rm\ x\:,\ $ so $\rm\ x^j\equiv 1\ \iff\ k\ |\ j\:$ – Bill Dubuque Mar 10 '11 at 6:47
Thanks, sorry my mathematics vocabulary are very limited. I tried to understand your hint, but I was confused because the argument that you used is very similar to the way the book proved using primitive root. – Chan Mar 10 '11 at 6:51
@Chan: What book? – Bill Dubuque Mar 10 '11 at 6:54
I'm currently reading "Elementary Number Theory and Its application" by Kenneth H. Rosen 6th edition. Thanks. – Chan Mar 10 '11 at 7:07

Do you understand the definition of $\phi(n)$? It's the number of natural numbers less than $n$ which are relatively prime to $n$. If $n$ is prime, then $\phi(n)$ is necessarily $n-1$ (since only 1 is relatively prime with $n$). Likewise, if $\phi(n) = n-1$ then only one number less than $n$ is relatively prime to it, which must be the number 1, so $n$ is prime. So that would be the relationship between them.

share|cite|improve this answer
The above definition of $\rm\:\phi(n)\:$ is incorrect. $\rm\:\phi(n)\:$ is the number of units (invertibles) modulo $\rm\:n\:$ or, equivalently, the number of naturals smaller than $\rm\:n\:$ that are coprime to $\rm\:n\:.\:$ Also it is not true that $\rm\ a^{\phi(n)}\equiv 1\ (mod\ n)\ $ for all $\rm\ a\neq 0$. – Bill Dubuque Mar 10 '11 at 18:43
Yeah, I meant to say "less than n which are relatively prime to n", I just had a little brain-fart and typed "divides" instead. And you're also correct about the second mistake. Clearly I wasn't at my best. I'll edit the answer substantially. – Keith Irwin Mar 11 '11 at 6:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.