# 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

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
• @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