Prime divisors of $n-1$, prove $n$ is prime

Can anybody help me out with this number theory question? My question is as follows:

If $n$ is a positive integer and if an integer $x$ exists such that $x^{n-1}\equiv 1 \pmod n$ and $x^{\frac{n-1}{q}} \neq 1 \pmod n$ for all prime divisors $q$ of $n-1$, then $n$ is prime.

I believe we have to use some reasoning on the order of $x$, but I don't know where to start. Thanks!

-
Thank you, Matt for editing my writing! – kira Mar 5 '11 at 19:18
I changed "\ (\text{mod}\ n)" to "\pmod n". That is standard usage. $\LaTeX$ is sophisticated. – Michael Hardy Mar 17 '12 at 17:11

1 Answer

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{#C00}{2}\$ for composite $\rm\:n,\:$ since they have at least $\:\color{#C00}2\$ smaller naturals non-coprime to $\rm\:n.$

Remark $\$ This is frequently called the Lucas Primality Test.

-
Can you explain more on this "This implies that $\rm\:n\:$ is prime, since $\rm\ \phi(n) \:\le\: n-\color{#C00}{2}\$ for composite $\rm\:n\:,\:$ since they have at least $\:\color{#C00}2\$ smaller naturals non-coprime to $\rm\:n\:.$"? Thanks! – kira Mar 6 '11 at 4:10
@kira: For composite $\rm\:n\:,\:$ show that there are at least $2$ naturals $\rm k < n\:$ with $\rm\ gcd(k,n) > 1\:.$ – Bill Dubuque Mar 6 '11 at 8:19
Aha! Thanks for clarification! – kira Mar 6 '11 at 17:49
@BillDubuque You mean at least 2 naturals $k \leq n$ :) Otherwise your statement fails for $n=p^2$. – N. S. Jun 25 '12 at 18:37
@N.S. No, it is fine since where you count $\,p^2,\,$ I count $\,0$, i.e. I'm choosing the reps mod $m\,$ as $0,1,\ldots,m\!-\!1,\:$ but you use $\:1,2,\ldots,m,\:$ where $\:\phi(m) =$ number of units (invertibles) mod $\,m.$ $\quad$ $\quad$ – Bill Dubuque Jun 25 '12 at 19:13