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?



Hint $\ $ The conditions imply that the order $\rm\:k\:$ of $\rm\:x\:$ is a divisor of $\rm\:n-1\:$ but not a proper divisor, hence $\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.$

Remark $ $ In fact we can we can restrict to maximal proper divisors $\,q\,$ using the following.

Order Test $\ \,a\,$ has order $\,n\iff a^n \equiv 1\,$ but $\,a^{n/p} \not\equiv 1\,$ for every prime $\,p\mid n.\,$

Proof $\ (\Leftarrow)\ $ If $\,a\,$ has $\,\color{#c00}{{\rm order}\ k}\,$ then $\,k\mid n\,$ (proof). If $\:k < n\,$ then $\,k\,$ is proper divisor of $\,n\,$ therefore $\,k\,$ arises by deleting at least one prime $\,p\,$ from the prime factorization of $\,n,\,$ hence $\,k\mid n/p,\,$ say $\, kj = n/p,\ $ so $\ a^{n/p} \equiv (\color{#c00}{a^k})^j\equiv \color{#c00}1^j\equiv 1,\,$ contra hypothesis. $\ (\Rightarrow)\ $ Clear.

  • $\begingroup$ When you say order $k$ of $x$, do you mean $ord_{k}x$? $\endgroup$ – Chan Mar 10 '11 at 6:44
  • $\begingroup$ @Chan: $\rm\ mod\ n\::\ k\ $ is the order of $\rm\ x\:,\ $ so $\rm\ x^j\equiv 1\ \iff\ k\ |\ j\:$ $\endgroup$ – Bill Dubuque Mar 10 '11 at 6:47
  • $\begingroup$ 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. $\endgroup$ – Chan Mar 10 '11 at 6:51
  • $\begingroup$ @Chan: What book? $\endgroup$ – Bill Dubuque Mar 10 '11 at 6:54
  • $\begingroup$ I'm currently reading "Elementary Number Theory and Its application" by Kenneth H. Rosen 6th edition. Thanks. $\endgroup$ – 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.

  • $\begingroup$ 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$. $\endgroup$ – Bill Dubuque Mar 10 '11 at 18:43
  • $\begingroup$ 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. $\endgroup$ – Keith Irwin Mar 11 '11 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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