{"id":603,"date":"2013-11-23T08:39:41","date_gmt":"2013-11-23T13:39:41","guid":{"rendered":"http:\/\/www.curtisbright.com\/bln\/?p=603"},"modified":"2013-11-23T08:39:41","modified_gmt":"2013-11-23T13:39:41","slug":"a-variant-n1-primality-test","status":"publish","type":"post","link":"http:\/\/localhost\/blog\/index.php\/2013\/11\/23\/a-variant-n1-primality-test\/","title":{"rendered":"A variant $n+1$ primality test"},"content":{"rendered":"

Last time<\/a>\u00a0I discussed the $n-1$ and $n+1$ primality tests. Recall that the $n-1$ test says that $n$ is prime if there exists an $\\newcommand{\\Z}{\\mathbb{Z}}a\\in\\Z^*_n$ such that<\/p>\n

\\begin{align}
\na^{n-1} &\\equiv 1 \\pmod{n} \\\\
\na^{(n-1)\/p} &\\not\\equiv 1 \\pmod{n}
\n\\end{align}<\/p>\n

for all primes $p$ which divide $n-1$.<\/p>\n

The $n+1$ can be stated in a similar form, and says that $n$ is prime if it is odd and there exists an $a\\in(\\Z[\\sqrt{d}])^*$ with $(\\frac{d}{n})=-1$ such that<\/p>\n

\\begin{align}
\na^{n+1} &\\equiv 1 \\pmod{n} \\\\
\na^{(n+1)\/p} &\\not\\equiv 1 \\pmod{n}
\n\\end{align}<\/p>\n

for all primes $p$ which divide $n+1$.<\/p>\n

I state it in this form to make the connection with the $n-1$ test, but I’ve done a little sleight-of-hand in the presentation. In the first test $a$ is a unit of $\\Z_n$, while in the second test $a$ is a unit of $\\Z[\\sqrt{d}]$ (not<\/em>\u00a0$\\Z_n[\\sqrt{d}]$). That is, the norm<\/a> of $a$ in $\\mathbb{Q}(\\sqrt{d})$ is $1$; this is a rather restrictive condition. In fact, when $d<-3$ the only units of $\\Z[\\sqrt{d}]$\u00a0are $\\pm1$, and both of these will fail the second condition since $(n+1)\/p$ will be even for some $p$.<\/p>\n

When $d$ is positive and squarefree the situation is a little better in that there are an infinite number of units in $\\Z[\\sqrt{d}]$. However, these units are all of the form $\\pm\\epsilon^k$ for some fundamental unit<\/em> $\\epsilon:=x+y\\sqrt{d}$ (this may be found by solving Pell’s equation<\/a>\u00a0$x^2-dy^2=1$). If the fundamental unit doesn’t satisfy the conditions then any power of it will also necessarily\u00a0fail, so for any given value of $d$ there is essentially only one possible choice of $a$ which could work. On the upside, one could simply look up this choice in a table\u00a0when $d$ is small; e.g., for $d:=3$ one should use $a:=2+\\sqrt{3}$.<\/p>\n

So that’s an unfortunate condition which isn’t present in the $n-1$ test, but it’s necessary to be able to use Fermat’s theorem in $\\Z[\\sqrt{d}]$, which implies that if $p$ is prime and $a$ has norm $1$ then<\/p>\n

\\[ a^{p-(d\/p)} \\equiv 1 \\pmod{p} , \\]<\/p>\n

and more generally<\/p>\n

\\[ a^{p^{e-1}(p-(d\/p))} \\equiv 1 \\pmod{p^e} .\u00a0\\]<\/p>\n

Now we’re ready to prove that the primality test works as stated. Let $\\newcommand{\\ord}{\\mathop{\\mathrm{ord}}\\nolimits}\\ord_{n,d}(a)$ denote the order of $a$ in $(\\Z_n[\\sqrt{d}])^*$, so the two conditions of the primality test tell us that $\\ord_{n,d}(a)=n+1$.<\/p>\n

Say $n$ has prime factorization $\\prod_{i=1}^k p_i^{e_i}$. By the Chinese remainder theorem<\/a>, we have<\/p>\n

\\[ \\Z_n[\\sqrt{d}] \\cong \\prod_{i=1}^k \\Z_{p_i^{e_i}}[\\sqrt{d}] , \\]<\/p>\n

so<\/p>\n

\\[ n+1 = \\ord_{n,d}(a) = \\DeclareMathOperator{\\lcm}{lcm}\\lcm(\\ord_{p_1^{e_1},d}(a),\\dotsc,\\ord_{p_k^{e_k},d}(a)) \\]<\/p>\n

and by Fermat’s theorem this divides<\/p>\n

\\[ \\lcm(p_1^{e_1-1}(p_1-(d\/p_1)),\\dotsc,p_k^{e_k-1}(p_k-(d\/p_k))) . \\]<\/p>\n

Since each $p_i$ is odd, this equals<\/p>\n

\\begin{align}
\n&\\mathrel{\\phantom{=}}2\\lcm\\Bigl(p_1^{e_1-1}\\frac{p_1-(d\/p_1)}{2},\\dotsc,p_k^{e_k-1}\\frac{p_k-(d\/p_k)}{2}\\Bigr) \\\\
\n&\\leq 2\\prod_{i=1}^k p_i^{e_i-1}\\frac{p_i-(d\/p_i)}{2} \\\\
\n&\\leq 2n\\prod_{i=1}^k\\frac{p_i+1}{2p_i} .
\n\\end{align}<\/p>\n

Now, if $n$ has at least two distinct prime factors then this is at most<\/p>\n

\\[ 2n\\cdot\\frac{3+1}{2\\cdot3}\\cdot\\frac{5+1}{2\\cdot5} = \\frac{4}{5}n . \\]<\/p>\n

Thus we conclude that $n+1\\leq4n\/5$, a contradiction since $n$ is positive. Thus $n$ must have just one prime factor; say $n:=p^e$. Using Fermat’s theorem and the fact that $(\\frac{d}{p})=-1$ (otherwise $(\\frac{d}{n})\\neq-1$), we have<\/p>\n

\\[ n+1 = \\ord_{n,d}(a) \\mid p^{e-1}(p+1) = n+p^{e-1} . \\]<\/p>\n

It follows that $n+1\\mid p^{e-1}-1\\leq n\/3$, again a contradiction, unless $p^{e-1}=1$, i.e., $e=1$ and $n=p$ is prime.<\/p>\n

I found this kind of argument in\u00a0Prime Numbers and Computer Methods for Factorization<\/a><\/em>\u00a0(page 116). In that book it is applied to Lucas sequences, which simplifies some things, although can also obscure the group $\\mathbb{F}_{n^2}^*$ working in the background.<\/p>\n","protected":false},"excerpt":{"rendered":"

Last time\u00a0I discussed the $n-1$ and $n+1$ primality tests. Recall that the $n-1$ test says that $n$ is prime if there exists an $\\newcommand{\\Z}{\\mathbb{Z}}a\\in\\Z^*_n$ such that \\begin{align} a^{n-1} &\\equiv 1 \\pmod{n} \\\\ a^{(n-1)\/p} &\\not\\equiv 1 \\pmod{n} \\end{align} for all primes … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"_links":{"self":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/603"}],"collection":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=603"}],"version-history":[{"count":0,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/603\/revisions"}],"wp:attachment":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=603"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=603"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=603"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}