Exercise 2.8.24* (Primality certificate (another result of Edouard Lucas))

Question

Let $a$ and $n>1$ be any integers such that $a^{n-1} \equiv 1 \pmod n$ but $a^d 
ot \equiv 1 \pmod n$ for every proper divisor $d$ of $n-1$. Prove that $n$ is a prime.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

Note: we must add the hypothesis $a 
ot \equiv 1 \pmod n$, otherwise $a = 9, n = 8$, for instance, satisfy the hypothesis, because $n-1 = 7$ has no proper divisor, so the second condition is empty, but $8$ is not a prime!

\begin{proof}

We know that $a\wedge n = 1$, because $a^{m-1} \equiv 1 \pmod m$. So we can consider the order $h$ of $a$ modulo $m$.

Note that $h 
e 1$, otherwise $a\equiv 1 \pmod p$.

If $h 
e n-1$, by Lemma 2.31,  $h\in ]\!]1,n-1[\![$ is a proper divisor of $n-1$, and $h^{n-1} \equiv 1 \pmod n$, in contradiction with the hypothesis. Hence $h = n-1$.
 
 \bigskip
 By problem 7, no two elements of $a,a^2,\ldots,a^h$ are congruent modulo $n$, and these elements are relatively prime to $n$. Therefore there are at least $h = n-1$ elements in a reduced system of residues modulo $n$, so $\phi(n) \geq n-1$. If $n$ was composite, $\phi(n) < n-1$. Therefore $n$ is a prime.
 
 \bigskip
 (Alternatively, if we use $\Z/n\Z$, then $\overline{1},\overline{a}, \cdots, \overline{a}^{n-2}$ are distincts elements of $(\Z/n\Z)^	imes$, thus $|(\Z/n\Z)^	imes| \geq n-1$, and $|(\Z/n\Z)^	imes| \leq n-1$ is always true, so $|(\Z/n\Z)^	imes| = n-1$. This shows that every element of $(\Z/n\Z)\setminus\{0\}$ is invertible, hence $\Z/n\Z$ is a field. This implies that $n$ is a prime.)
\end{proof}

Note: We can give a less strong hypothesis. Let $n >2$ and $p_1,\ldots,p_k$ be the prime factors of $n-1 >1$.

If $a
ot \equiv 1 \pmod n$, $a^{n-1} \equiv 1 \pmod n$ and
$$a^{(n-1)/p_i} 
ot \equiv 1 \pmod n, \qquad i = 1,2,\ldots,k,$$
then the order of $a$ modulo $n$ is $n-1$, and the same reasoning shows that $n$ is a prime.

\bigskip
Example:
\begin{verbatim}
sage: n = 1234567891234567891234567891
sage: a = Mod(2,n); a^(n-1)
1
sage: factor(n-1)
2 * 3^3 * 5 * 757 * 3607 * 3803 * 440334654777631
sage: for p,_ in factor(n-1):
....:     print('p =',p,'a^((n-1)/p) =', a^((n-1)//p))
....:     
('p =', 2, 'a^((n-1)/p) =', 1234567891234567891234567890)
('p =', 3, 'a^((n-1)/p) =', 530866758173318629029019298)
('p =', 5, 'a^((n-1)/p) =', 854954600399764194910596932)
('p =', 757, 'a^((n-1)/p) =', 1086212966233513514618043309)
('p =', 3607, 'a^((n-1)/p) =', 660467933836326895622483799)
('p =', 3803, 'a^((n-1)/p) =', 1094010502560723949804893285)
('p =', 440334654777631, 'a^((n-1)/p) =', 1113291225028075564965212267)
\end{verbatim}
This proves that $n = 1234567891234567891234567891$ is a prime (easy to remember). But we must prove recursively that the factors such $440334654777631$ are prime with the same method, to obtain a complete primality certificate for $n$.

Exercise 2.8.24* (Primality certificate (another result of Edouard Lucas))

Answers

Comments

Exercise 2.8.24* (Primality certificate (another result of Edouard Lucas))

Answers

Comments

Add answer