Conjecture 109. Another test of Primality

On Jan 1, 2026 Sebastián Martín Ruiz sent the following Conjecture.

Conjecture:
p>3,  p=3 (mod 4) p is prime
if and only if
(1+i)^p=1-i (mod p) and (1+2i)^p=1-2i (mod p).

Q1. Prove this conjecture or find a counterexample.

Q2. This conjecture has been tested up to p<10^9. Can you test it far beyond?

Q3. Send the largest prime (original of you or not) that you can prove using this test, reporting the time spent in your computer.

Additional notes by SMR:

a) The test of Lucas-Lehmer for Mersenne primes Mp has a complexity O(p^2 log p log log p)
and the conjecture test has a complexity O(p^3), but the conjecture test is for all type of primes

b) Congruences modulo p are also defined for Gaussian integers, which are complex numbers
of the form a+bi with a and b being integers. It should be noted that this Conjecture is an equivalence; that is, it is enough to prove both congruences and the number will be prime. Two other complex numbers other than 1+i and 1+2i could also be used, but the larger the modulus, the slower the calculation.

c) With my PC computer, I have verified this well-known prime
p=2996863034895*2^1290000-1 of approximately
360,000 digits and it took 17 hours and 11 minutes of CPU time.

d) The MATHEMATICA program has a function that performs these PowerMod congruences,
and when applied twice:
PowerMod(1+i,p,p)=1-i
PowerMod(1+2i,p,p)=1-2i
checks if p is prime.

This is a polynomial-time algorithm, and with a good computer, it would be possible to check
the largest known primes, that is, the Mersenne primes, the largest of which has 41 million digits.

e) Curiously, for very large primes, the vast majority already tested & reported are congruent to 3 (mod 4). Those congruent to 1 (mod 4) are very rare.

f) Comparative times table, running both tests in SMR PC:

Mersenne prime, Test Lucas Lehmer time, SMR Conjecture Time

M86243, 36.7 sec, 106.4 sec

M132049, 77.7 sec, 291.2 sec

M216091, 246.4 sec, 781.9 sec

During January 10 to 16, 2025, contributions came from Emmanuel Vantieghem

***

Emmanuel wrote:

However, it is easy to prove that the first congruence always holds for such numbers:

***

On Jan 20, 2026, Alessandro Casini wrote:

Here are some observations about the conjecture. 
It's easy to check that both conditions are satisfied by every prime p ≡ 3 (mod 4). Indeed, if p is prime then (1+x)^p ≡ 1+x^p (mod p), since all the intermediate binomial coefficients are divisible by p. In particular, (1+i)^p ≡ 1+i^p ≡ 1−i (mod p), and similarly (1+2i)^p ≡ 1+2^p i^p ≡ 1−2i (mod p), where Fermat’s little theorem is used. A more conceptual way to say this is that, in Z[i]/(p), the Frobenius map acts as complex conjugation. Using the same argument, one sees that for p ≡ 1 (mod 4) the congruences are conjugated instead.
The real interest of the conjecture obviously is the converse direction.

For the first condition, one can explicitly compute the real and imaginary parts of (1+i)^p; these turn out to be alternating sums of binomial coefficients with even and odd indices. Somewhat unexpectedly, this shows that the first condition is exactly equivalent to p being an Euler–Jacobi pseudoprime to base 2. Therefore, any possible counterexample must lie among these numbers (OEIS A047713). From a computational point of view, the test has cubic time complexity.

For the second condition, an explicit expansion doesn't seem to be available, so I can't translate it into a clean equivalent statement. Still, by comparing the norms modulo p on both sides, one finds that this condition forces p to be a Fermat pseudoprime to base 5 (OEIS A005936), which further narrows the list of potential counterexamples.
It seems likely that some additional input is needed, either from the theory of Gaussian integers (where primes congruent to 3 (mod 4) play a special role) or by Algebra's tricks. In the end, the conjecture can be summarized rather neatly as saying that if the Frobenius automorphism acts like complex conjugation on two independent Gaussian integers modulo p, then p must be prime.
In any case, I bet the conjecture is true.

After I (CR) asked Alessandro the following: "What do you think about the claim by Sebastian that this test can compete in speed with the alternative primality tests for Non-Mersenne candidates to be primes?", he responded:

• Deterministic Miller-Rabin: O(n^4) assuming unproven GRH
• ECCP: heuristically n^4/n^5, but produce a certificate
• APR-CL: actually asymptotically between polynomial and exponential
• AKS: n^6. Lowers to n^3 if Agrawal's conjecture were true

Regarding the same questions Mr. Emmanuel Vantieghem, responded: "Frankly, I still think there are counterexamples"

So, in order to decide this Conjecture we need a complete demonstration or a simple counterexample.

***