# Pseudoprimes

main page    database    statistics    verification

## W search: non-squarefree pseudoprimes

In the category S search algorithm, we used coprime factors for easy rho computations. However, this causes some pseudoprimes to be missed. On this page we will investigate how to correct the problem.

### Wieferich primes

If a pseudoprime n is divisible by a square p2, then p is a Wieferich prime. Proof: write n = pe · m, such that e ≥ 2 and p does not divide m. Let k be the order of 2 in G = (Z/peZ)*. We have that k | n-1, and also k divides |G| = pe-1(p-1). This implies that p cannot divide k, hence k | p-1, giving 2p-1 = 1 mod pe. We conclude that p is a Wieferich prime.

The only known Wieferich primes are 1093 and 3511. There may be larger Wieferich primes, but not below x1/2, which is the range that concerns this project. We can now list the non-squarefree pseudoprimes.

### Only squares, no cubes

There exist no 64-bit pseudoprimes which are divisible by a cube, because gcd(w3, rho(w3)) = w for both Wieferich primes w.

### No cofactor

Both n = 10932 and n = 35112 are pseudoprimes. Because they are not found by both search algorithms, we need to add them to the result list ourselves.

### Prime cofactor

If n = w2 · p with p prime, then the category E search will find all of these n for p > w2. We need to search p < w2 separately. This gives the following pseudoprimes:
• w = 1093: 5654273717, 26092328809, 31310555641, 237865367741, 333967711897, 601401837037
• w = 3511: 129816911251, 259621495381, 346157884801, 12634325182441, 24273469559431, 57114029344321

### Composite cofactor

Because the category E search does not miss any of these pseudoprimes, we only need to look at n in S.
Write n = w2 · q, q = q1 · q2 with q1 > q2 > 1 coprime. Note that q1 < x2/3 because q2 · w2 > x1/3 for both Wieferich primes w.
• If q1 > q2 · w2, then n will be found in S(q1).
• If q1 < q2 · w2, then n will be found in S(q2 · w2).
With S(q) we denote the set of pseudoprimes found by the category S algorithm at q.