4
$\begingroup$

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!

  • 0
    I changed "\ (\text{mod}\ n)" to "\pmod n". That is standard usage. $\LaTeX$ is sophisticated.2012-03-17

1 Answers 1

5

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.

  • 0
    @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$2012-06-25