Proth's Theorem

hbghlyj

math.stackexchange.com/a/2916522/1048081

hbghlyj

math.stackexchange.com/questions/946709/proof-concerning-specific-class-of-proth-numbers
math.stackexchange.com/questions/1410031/new-deterministic-prima ... the-form-p-cdot-2n-1
math.stackexchange.com/questions/3316626/confusing-thing-at-the-proof-of-proth-theorem
math.stackexchange.com/questions/993281/primality-criterion-for-specific-class-of-proth-numbers
math.stackexchange.com/questions/485655/prove-that-n-must-be-prime

hbghlyj

and $s$ must be the order of $a$ modulo $q$, otherwise $s$ would not be the order of $a$ modulo $N$.

Why is $s$ the order of $a$ modulo $q$ ?

$q$ is a prime factor of $N$,
$s$ is the order of $a$ modulo $N$ $\nRightarrow$ $s$ is the order of $a$ modulo $q$
For example,
The order of 2 modulo 35 is 12, whereas the order of 2 modulo 5 is 4


所以这步是不是錯了 发到了math.stackexchange.com/questions/4888079/a-question-about-a-proof-of-proths-theorem

hbghlyj

$a^s\equiv1\pmod N⇒a^s\equiv1\pmod q⇒s$ is a multiple of the order of $a$ modulo $q$
which doesn't imply that $s$ is the order of $a$ modulo $q$

hbghlyj

正确的证明见Corollary 6.6

hbghlyj

Theorem 6.1 (Rabin-Miller Theorem). Let $p$ be an odd prime and let $a$ be a positive integer such that $\gcd(a, p)=1$. Factor $p-1$ as $p-1=2^{e} q$ for some odd $q \in \mathbb{N}$. Then either
(1) $a^{q} \equiv 1\pmod p ;$ or
(2) there exists $i \in\{0, \ldots, e-1\}$ such that $a^{2^{i} q} \equiv-1\pmod p$.

Proof.

Since $p-1=2^{e} q$, we know
$$
a^{p-1}=a^{2^{e} q}=a^{2 \cdot 2^{e-1} q}=\left(a^{2^{e-1} q}\right)^{2} .
$$
Since $\gcd(a, p)=1$, we know $p \nmid a$, so we can apply Fermat's little theorem to obtain
$$
a^{p-1}=\left(a^{2^{e-1} q}\right)^{2} \equiv 1 \pmod p.
$$
By Exercise 5.11, we have
$$
a^{2^{e-1} q} \equiv \pm 1 \pmod p .
$$
If $a^{2^{e-1} q }\equiv-1\pmod p$, then we fulfill the second condition and are done. Otherwise, if $a^{2^{e-1} q} \equiv 1\pmod p$, then we can apply the process we applied above to obtain
$$
a^{2^{e-2} q} \equiv \pm 1 \pmod p.
$$
If we never obtain a congruence with $-1$ by repeating this process, then we eventually come to $a^{2^{0} q} \equiv 1\pmod p$ and thus $a^{q} \equiv 1\pmod p$, fulfilling the first condition.

Next we prove Wilson's theorem, which is itself a primality test.
Theorem 6.2 (Wilson's Theorem). A positive integer $p$ is prime if and only if $(p-1) ! \equiv-1\pmod p$

Proof.

If $p=2$, then we have $(2-1) !=1 \equiv-1\pmod 2$.
Now suppose $p$ is prime and $p>2$; then $p$ is odd. Because $p$ is prime, we know that for all $a \in \mathbb{N}$ such that $1 \leq a \leq p-1$, we have $\gcd(a, p)=1$. Hence $S_{p}=\{1, \ldots, p-1\}$ is a reduced residue system of $p$. By Lemma 5.3, each residue $a \in S_{p}$ has an inverse modulo $p$ that is also in $S_{p}$. We first desire to find all of the $a \in S_{p}$ such that $a \equiv a^{-1}\pmod p$. If $a \equiv a^{-1}\pmod p$, then $a^{2} \equiv 1\pmod p$. It follows from Exercise 5.11 that $a \equiv \pm 1\pmod p$. This means that if $a \equiv 1\pmod p$, then $a$ is in the same congruence class as 1 , and if $a \equiv-1\pmod p$, then $a$ is in the same congruence class as $p-1$. Hence, the only two values of $a$ that are their own inverses modulo $p$ are $1$ and $p-1$. Now we evaluate $(p-1)!$ modulo $p$, substituting based on the above results:
$$
\begin{aligned}
(p-1) ! & \equiv 1 \cdot 2 \cdots(p-2) \cdot(p-1) \pmod p \\
& \equiv 2 \cdots(p-2) \cdot(p-1) \pmod p \\
& \equiv-(2 \cdots(p-2)) \pmod p .
\end{aligned}
$$
As shown above, each least positive residue modulo $p$ is in $S_{p}$ and has an inverse in $S_{p}$. For each pair of a residue $a$ and its inverse $a^{-1}$, we have $a a^{-1} \equiv 1\pmod p$.
We can therefore simplify the above congruence to yield $(p-1) ! \equiv-1 \pmod p$.
Now suppose that $(p-1) ! \equiv-1\pmod p$ and assume that $p$ is composite. Then there exist $a, b \in \mathbb{N}$ such that $1<a, b<p$, and $p=a b$. It follows that $a \mid(p-1)!$ and $a \mid p$. Therefore, there exist $c, d \in \mathbb{N}$ such that $a c=(p-1)!$ and $a d=p$. By substitution into $(p-1) ! \equiv-1\pmod p$, we have $a c \equiv-1\pmod{ad}$, which implies $a \mid 1$ and thus contradicts the inequality $1<a<p$. We can form an identical contradiction with $b$, so $p$ is not composite; therefore, $p$ is prime.

Note that Wilson's theorem is not helpful if $p$ is sufficiently large, because for a large enough $p$, calculating $(p-1)!$ would be expensive.

There is also a primality test for integers of the form $2 p+1$, where $p$ is prime. It relies upon modular order.

Theorem 6.3. Let $p$ and $n$ be positive integers. Suppose $p$ is prime and let $n=$ $2 p+1$. If
$2^{n-1} \equiv 1 \pmod n$ and $3 \nmid n$,
then $n$ is prime.

Proof.

Let $q \in \mathbb{N}$ be prime and suppose $q \mid n$. The positive integer $n=2 p+1$ is odd, so $q$ must also be odd. By substitution, $2^{n-1}=4^{p} \equiv 1\pmod n$. We thus know that there exists $\alpha$ such that $4^p-1=\alpha n$. Since $q \mid n$,
$$
4^p \equiv 1 \pmod q.
$$
It follows that $\operatorname{ord}_{q} 4 \mid p$, and since $p$ is prime, $\operatorname{ord}_{q} 4$ is either 1 or $p$. If $\operatorname{ord}_{q} 4=1$, then $4^{1} \equiv 1\pmod q$, and this implies $q=3$. Since $q \mid n$ by assumption, we would thus have $3 \mid n$, which would contradict our hypothesis. Thus we deduce $\operatorname{ord}_{q} 4=p$. By Euler's totient theorem, since $\operatorname{ord}_{q} 4 \mid \varphi(q)$ and $q$ is prime, we have $p \mid q-1$, by substitution.

Since $p \mid q-1$, we know $p \leq q-1$ and thus $q \geq p+1$. Since $n=2 p+1$, we know $\frac{n}{2}=p+\frac{1}{2}$, so $p+1>\frac{n}{2}$. Since $p \geq 2$, we know $n \geq 5$, so it follows that $\frac{n}{2}>\sqrt{n}$. We thus have the inequality
$$
q \geq p+1>\frac{n}{2}>\sqrt{n}
$$
which is true for every prime factor $q$ of $n$. But this implies $q=n$ and $n$ is prime, because composite numbers have at least two factors $k_{1}$ and $k_{2}$ satisfying $k_{1} \leq \sqrt{n} \leq k_{2}$

The Lucas primality test theorem can also be proven using the concept of modular order.

Theorem 6.4 (Lucas Primality Test). Let $a$ and $n$ be positive integers. Suppose $a^{n-1} \equiv 1\pmod n$ and that for all primes $q \in \mathbb{N}$ such that $q \mid n-1$, we have $a^{\frac{n-1}{q}} \not \equiv 1\pmod n$. Then $n$ is prime.

Proof.

Let $r=\operatorname{ord}_{n} a$. By the first part of our hypothesis, and by Exercise 5.10, it follows that $r \mid n-1$. Hence there exists $k \in \mathbb{N}$ such that $k r=n-1$. Assume $k>1$, which implies $n-1>r$. Now let $q \in \mathbb{N}$ be prime and suppose $q \mid k$. Since $k r=n-1$ and $q \mid k$, there exists $\alpha \in \mathbb{N}$ such that $\alpha q=k$, and thus $(\alpha r) q=n-1$.
Hence $q \mid n-1$, fulfilling the second part of our hypothesis.
Now consider $a^{\frac{n-1}{q}}$. Since $k r=n-1$, we know $a^{\frac{n-1}{q}}=\left(a^{r}\right)^{\frac{k}{q}}$. Since $r=\operatorname{ord}_{n} a$, we know $a^{r} \equiv 1\pmod n$ by definition, so we have $\left(a^{r}\right)^{\frac{k}{q}} \equiv 1^{\frac{k}{q}}=1\pmod n$. Therefore, $a^{\frac{n-1}{q}} \equiv 1\pmod n$, but this contradicts the second part of our hypothesis, so we now know $k=1$ and thus $n-1=r=\operatorname{ord}_{n} a$.

Since $a^{n-1} \equiv 1\pmod n$, there exists $\beta$ such that $\beta n=a^{n-1}-1$ and therefore
$$
1=a^{n-1}-\beta n=\left(a^{n-2}\right) a+(-\beta) n .
$$
Hence 1 is a $\mathbb{Z}$-linear combination of $a$ and $n$, so by Bézout's identity, we know $\gcd(a, n)=1$. We can thus use Theorem 5.5 and the definition of $\operatorname{ord}$ to deduce $\operatorname{ord}_{n} a \mid \varphi(n)$, so $\operatorname{ord}_{n} a=n-1 \leq \varphi(n)$. But by the definition of $\varphi(n)$, we know $\varphi(n) \leq n-1$. Hence we have $n-1 \leq \varphi(n) \leq n-1$, so $\varphi(n)=n-1$. By Remark 4.2, it follows that $n$ is prime.

The Pocklington criterion is itself a primality test, but it is also used in the more general Pocklington-Lehmer primality test.

Theorem 6.5 (Pocklington Criterion). Let $n$ be a positive integer such that $n-1=$ $F R$, where $F$ and $R$ are positive integers and $\gcd(F, R)=1$. Suppose that there exists $a \in \mathbb{N}$ such that
$$
a^{n-1} \equiv 1\pmod n \quad \text { and } \quad \gcd\left(a^{\frac{n-1}{q}}-1, n\right)=1
$$
for all primes $q \mid F$. Then for each prime $p \in \mathbb{N}$ such that $p \mid n$, we have $p \equiv 1\pmod F$. Furthermore, if $F \geq \sqrt{n}$, then $n$ is prime.

Proof.

Let $p$ be a prime dividing $n$. By our hypothesis, $a^{n-1} \equiv 1\pmod p$, since $p \mid n$. Now let $q$ be a prime such that $q \mid F$ and $q^{\alpha}$ is the largest power of $q$ dividing $F$, and suppose that $a^{\frac{n-1}{q}} \equiv 1\pmod p$. This implies $p \mid a^{\frac{n-1}{q}}-1$. But since $p \mid n$, this would mean $\gcd\left(a^{\frac{n-1}{q}}-1, n\right)>1$, contradicting our hypothesis. Therefore $a^{\frac{n-1}{q}} \not\equiv 1\pmod p$.

Now let $r=\operatorname{ord}_{p} a$. By the above results and the definition of $\operatorname{ord}$, we know $r \mid n-1$ and $r \nmid\frac{n-1}{q}$. Since $n-1=F R$ and $q^{\alpha} \mid F$, we can write $n-1=q^{\alpha} t$ for some $t \in \mathbb{N}$, and thus $r \mid q^{\alpha} t$ and $r \nmid\frac{q^{\alpha} t}{q}=q^{\alpha-1} t$. From these, we can deduce $q^{\alpha} \mid r$. This is true for all prime factors $q$ of $F$, so it follows that $F \mid r$. Since $p$ is prime, $\varphi(p)=p-1$, and by the definition of $\operatorname{ord}$ and by Euler's totient theorem, we know $r \mid p-1$. Therefore, $F \mid p-1$. Thus $p \equiv 1\pmod F$, as required. This is true for all prime factors $p$ of $n$.

We lastly show that if $F \geq \sqrt{n}$, then $n$ is prime. Suppose $F \geq \sqrt{n}$. If $n$ were composite, then it would have at least one prime factor $p$ satisfying $p \leq \sqrt{n}$. However, we just showed that for all prime factors $p$ of $n$, we have $p \equiv 1\pmod F$. This implies that there exists $\gamma$ such that $\gamma F=p-1$ and thus $\gamma F+1=p$. The smallest positive value $p$ could have (when $\gamma=1$) is thus $F+1$, which is strictly greater than $\sqrt{n}$, since we assumed $F \geq \sqrt{n}$. Therefore, all prime factors $p$ of $n$ are greater than $\sqrt{n}$, so $n$ must be prime.

We finish by proving a specific case of the Pocklington criterion, which is given by Proth.
Corollary 6.6 (Proth's Theorem). Let $n, k$, and $m$ be positive integers such that $k$ is odd, $m \geq 2$, and $k<2^{m}$. Define $n$ as $n=k \cdot 2^{m}+1$ and suppose that there exists a positive integer $a$ such that $a^{\frac{n-1}{2}} \equiv-1\pmod n$. Then $n$ is prime.

Proof.

Let $F=2^{m}$ and $R=k$; then we have $n-1=F R$ and $\gcd(F, R)=1$ since the only prime factor of $F$ is 2 and $R$ is odd. Since we are given $a^{\frac{n-1}{2}} \equiv-1\pmod n$, we have $a^{\frac{n-1}{2}} \not \equiv 1$ $\pmod n$, and we can square the congruence to obtain $a^{n-1} \equiv 1\pmod n$. Hence $\gcd\left(a^{\frac{n-1}{q}}, n\right)=1$ for $q=2$, the only prime $q$ such that $q \mid F$. Since $k<2^{m}$, we know $R<F$, and since $n=F R+1$, it follows that $F \geq \sqrt{n}$. Hence the requirements of the Pocklington criterion are met, so $n$ is prime.

There are, of course, many other primality tests we could discuss, several of which are related to and build on the ones we have proven here (such as Pépin's test, which is an alteration of Proth's test). The background and methods provided in this paper are hopefully sufficient to further study primality tests, as well as number theory in general.

hbghlyj

A Pierpont prime is a prime number of the form $2^{u}\cdot 3^{v}+1$ for some nonnegative integers $u$ and $v$.

Primality testing
When $2^u > 3^v$, the primality of $2^u\cdot 3^v + 1$ can be tested by Proth's theorem. On the other hand, when $2^u < 3^v$ alternative primality tests for $M=2^u\cdot 3^v + 1$ are possible based on the factorization of $M-1$ as a small even number multiplied by a large power of 3.