**
**

# 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 p

^{2}, then p is a

Wieferich prime. Proof: write n = p

^{e} · m, such that e ≥ 2 and p does not divide m. Let k be the order of 2 in G = (Z/p

^{e}Z)*. We have that k | n-1, and also k divides |G| = p

^{e-1}(p-1). This implies that p cannot divide k, hence k | p-1, giving 2

^{p-1} = 1 mod p

^{e}. 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 x

^{1/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(w

^{3}, rho(w

^{3})) = w for both Wieferich primes w.

### No cofactor

Both n = 1093

^{2} and n = 3511

^{2} 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 = w

^{2} · p with p prime, then the

category E search will find all of these n for p > w

^{2}. We need to search p < w

^{2} 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 = w

^{2} · q, q = q

_{1} · q

_{2} with q

_{1} > q

_{2} > 1 coprime. Note that q

_{1} < x

^{2/3} because q

_{2} · w

^{2} > x

^{1/3} for both Wieferich primes w.

- If q
_{1} > q_{2} · w^{2}, then n will be found in S(q_{1}).
- If q
_{1} < q_{2} · w^{2}, then n will be found in S(q_{2} · w^{2}).

With S(q) we denote the set of pseudoprimes found by the

category S algorithm at q.