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
    Thank you, Matt for editing my writing!2011-03-05
  • 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
    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!2011-03-06
  • 1
    @kira: For composite $\rm\:n\:,\:$ show that there are at least $2$ naturals $\rm k < n\:$ with $\rm\ gcd(k,n) > 1\:.$2011-03-06
  • 0
    Aha! Thanks for clarification!2011-03-06
  • 0
    @BillDubuque You mean at least 2 naturals $ k \leq n$ :) Otherwise your statement fails for $n=p^2$.2012-06-25
  • 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