It is not always necessary to use the Proth Theorem to prove a Proth number prime.
What follows is a proof that is possible because the base we have chosen is a quadratic residue.
Next we include a flowchart of a decision process regarding use of Proth theorem or not
If the above has got you interested in quadratic residues, then here are some resources to consider:
- Second chapter of Number Theory and Algebraic Equations
- MIT: Theory of Numbers – Lecture 9
What follows is an introduction and proof of the Conjecture provided by Natalia Skirrow
Let N = N(k) = (2^k-1)*2^(k+3)+1, and M = A000225(k+1) = 2^(k+1)-1.
17 divides N if k == 1,4 (mod 8).
As a Proth number, N is prime iff there exists an integer c such that c^((N-1)/2) == -1 (mod N).
The conjecture can be strengthened to the statement that 2^((N-1)/4) == -1 (mod N) iff N is prime.
Proof of conjecture:
Suppose that 2^((N-1)/4) == -1 (mod N) but N is composite, i.e. there exists a nontrivial prime divisor p | N, and let o be the multiplicative order of 2 (mod p).
The supposition implies 2^((N-1)/4) == -1 (mod p), so o is a divisor of (N-1)/2 but not of (N-1)/4.
Thus val_2(o) = k+2, so (by Fermat’s little theorem) 2^(k+2) | p-1, and p >= 2^(k+2)+1. N < 2^(2*k+3), so this implies p > sqrt(N).
However, dividing N by p would produce a divisor of N that is < sqrt(N), a contradiction.
Proof of conjecture’s converse:
N = 2*M^2 – 1, and since N == -1 (mod M), the Jacobi symbol (N|M) = (-1|M) = -1. If N is prime, then since N == 1 (mod 4), quadratic reciprocity gives (M|N) = (N|M) = -1.
Thus Euler’s criterion for quadratic residuehood gives that M^((N-1)/2) == -1 (mod N).
However, 2*M^2 == 1 (mod N), so M^((N-1)/2) == (M^2)^((N-1)/4) == 2^(-(N-1)/4) (mod N).
Thus, if N is prime, 2^((N-1)/4) == -1 (mod N).
Note that 2^((N-1)/4) == -1 => 2^((N-1)/2) == 1, which by Euler’s criterion means 2 is a quadratic residue, so the conjecture is equivalent to the statement that if any numbers exist as primality witnesses for Proth’s test, sqrt(2) (mod N) always exists and is among them.
Proofs that are a page or two and involve classic theorems including Euler criterion are I believe possible.
Do verify any proofs given on this page.
There may be several AI proofs, the first by looking at the 2-adic valuation involved has been completed [but not verified] by Opus 5.5 Claude
Although AI can spot the potential for generalising a proof, it does not offer to do that, instead observing “statement hold for far more general N”