Pseudoprimes Rare Composite Numbers with
Properties Typical of Primes
(2003-11-19) [Fermat] Pseudoprimes to Base a A composite number n is a pseudoprime to base a if it divides
Fermat's Little Theorem states that
any prime number n has this property.
Most authors call pseudoprime only the rare composite
numbers that do.
The most studied pseudoprimes are pseudoprimes to base 2,
which have been variously called
Sarrus numbers (1819) and
Poulet numbers (1926) ...
The unqualified term "pseudoprime" normally means
a pseudoprime to base 2.
Under this definition, if n is a pseudoprime to base a, then n and a
are necessarily coprime ( HINT:
un + va = 1, for some integers u and v).
How many bases is a composite number a pseudoprime to?
n is a pseudoprime to base a if and only if
a n-1 is congruent to 1, modulo n.
This depends only on the the residue class of the base a modulo n.
For example, when n is 91 there are
36 such residues classes.
We may observe that 91 is thus coprime to twice as many
bases as it's a pseudoprime to
(72 is the Euler totient of 91).
In fact, it's easy to see that the Euler totient of an integer must always
be a multiple
of the number of residue classes of bases to which this integer is a pseudoprime
The residues modulo n whose q-th power is unity form
a subgroup of the residues coprime to n.)
The ratio (k) is 1 for
Carmichael numbers. It's 2 for n = 91
and other composite numbers listed on the second line of the following table:
Numbers that are pseudoprimes to one in k of their coprime bases:
When n-1 and
f(n) are coprime,
then n is only a pseudoprime in the trivial
case of a base congruent to 1 modulo n.
This corresponds to the even numbers appearing in the
first line of the following table.
The other even numbers are:
28, 52, 66, 70, 76, 112, 124, 130, 148, 154, 172, 176, 186, 190...
The 14th line in the table below is empty, as would be the kth line
for any k that's a nontotient
(an even number which is not the Euler totient of any
14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122...
( Prime numbers have been included in the table below. )
Numbers n that are pseudoprimes to bases of k residue classes modulo n:
Any odd composite n is a pseudoprime to bases of at least two residue
classes (1 and n-1). Unless it's a power of 3,
it is a pseudoprime to some other base.
The number of bases a, between 1 and n-1, for which n divides
a n-1 -1 is:
gcd ( n-1 , p-1 )
p | n
(2005-04-19) Strong Pseudoprimes to Base a Strong pseudoprimes are less common than pseudoprimes to base a.
If n is prime, the residues modulo n form a field
in which the quadratic equation x 2 = 1
may only have 2 solutions (congruent to +1 or -1).
If n is an odd prime,
a(n-1)/2 is thus congruent to either 1 or -1
(unless n | a).
When this is true of a composite number n,
it's called an
to base a (if the base is not specified, base 2 is understood).
In the case where a(n-1)/2 is congruent to 1
and (n-1)/2 is itself even,
the idea may be iterated: For a prime n, raising the base to the power
of (n-1)/4 would thus always yield
+1 or -1 as a residue modulo n. And so forth...
In other words, let's put n in the form n = q 2k + 1
(where q is an odd number) and consider, modulo n,
the following sequence of length k+1 :
a q , a 2q ,
a 4q , ... a n-1
Each term in this sequence is the square of the previous one, modulo n.
For a prime number n, the residue 1 appears preceeded by -1, unless it appears first.
If this pattern does not hold, the odd number n is hereby proven composite
and the number a is called a witness of n.
If the pattern does hold for an odd composite
number n, then n is said to be a strong pseudoprime
to base a
(and a is called a nonwitness of n).
The trivial nonwitnesses a = 1
and a = n-1 are normally excluded.
(2009-07-15) Witnesses and Nonwitnesses of Strong Pseudoprimes
75% to 100% of the bases of an odd composite are witnesses.
We may ask of strong pseudoprimes the same
question as that investigated
above for ordinary pseudoprimes:
Given an odd composite number n, how many nontrivial bases is it
a strong pseudoprime to?
A given base (a) is a witness of n if and only if
Witnesses come in pairs whose lesser member
is between 2 and (n-1)/2.
It turns out that many odd composites have no nontrivial
nonwitnesses (for such numbers, the stochastic Rabin-Miller test described
below will always produce the same result).
Next in line are the numbers which have only one nontrivial
pair of nonwitnesses... Those numbers are rare but they
are surprisingly easy to describe: They are powers of 5.
A nonwitness of a power of 5 can be elegantly characterized as equal to the
residue, modulo that power, of one of the following two
ontegers whose square is -1 = ...4444444444
The above is expressed using radix 5 (do check that those two numbers add up to zero,
as the propagation of the "carry" from right to left makes every digit of
the sum vanish).
The following table merely presents the same results less compactly.
For example, the last six figures of the first pentadic above
(431212) yield 14557, which
is the larger of the two nonwitnesses of the sixth power of 5.
More generally, if 2k+3 is prime, then
the number (2k+3)n
has exactly k nontrivial pairs of nonwitnesses.
Furthermore, if that prime is
congruent to 1 modulo 4, then those powers
are the only such numbers...
Odd numbers with exactly k nontrivial pairs of nonwitnesses
(2005-04-19) Rabin-Miller Stochastic Primality Test
A given composite number fails it for over 75% of the choices for a.
An integer n may not be a
strong pseudoprime to more than ¼ of the possible bases.
Choosing a base (a) at random, we may determine very efficiently
if a given number n is a strong pseudoprime to that base.
This is a stochastic test that n always passes if it's prime,
but fails at least 75% of the time if it's not.
A composite n passes the test k times with a probability less than
No living creature
will ever see a composite number pass this test 50 times!
Here's a complete
UBASIC implementation of the Rabin-Miller test:
' Pprime always returns 1 when its argument is prime.
' Otherwise, it returns 0 more than 75% of the time.
' Deal with trivialities:
if N<0 then N=-N
if N=2 then return(1)
if even(N) or N<=1 then return(0)
if N<=7 then return(1)
' Initialization: N = Q*2^K+1 (with Q odd). A is random.
Q=N\2:K=1:while even(Q):Q\=2:inc K:wend
' Return 1 iff N is a strong pseudoprime to base A.
A=modpow(A,Q,N):if A=1 then return(1)
for J=2 to K
if A=N-1 then cancel for:return(1)
For a composite number N, a base A
(between 2 and N-2) which makes the above test
return 0 is called a witness of N.
If A is a
(Germany. 2005-04-16; e-mail)
For 3 distinct odd primes (p1, p2, p3 )
prove that, when the 3 numbers
p1p2, p1p3 and
p2p3 are Poulet numbers,
then p1p2p3 is too.
The same argument proves
2 p1p2p3 congruent to 2
modulo p1, p2 or p3.
As these 3 moduli are pairwise coprime, the
Chinese Remainder Theorem says:
2 p1p2p3 =
2 (mod p1p2p3 )
p1p2p3 is indeed a Poulet number
(a pseudoprime to base 2)
The above conclusion may not hold if the premises aren't all true.
For example, 15´43,
15´127 are Poulet numbers, but
is not (15 is not prime).
We also assumed that the three primes were distinct (see last part of the proof).
The very special case where two of them are equal is discussed in the next section about
In the above, it's not strictly necessary for the three factors to be prime, as primality is invoked
only in the first line of the above proof, which also holds (by definition)
for any weak pseudoprime.
Also, there's nothing special about base 2, as the proof would hold in any base.
Thus, the result is best stated as a theorem about weak pseudoprimes to base a,
If p1, p2 and p3 are pairwise coprime
and if the six numbers
p1 , p2 , p3 ,
p1 p2 , p1 p3,
p2 p3 are
weak-pseudoprimes to base a (or primes) then so is
p1 p2 p3 .
(2005-04-18) Wieferich primes
and some of their Poulet multiples
A Wieferich prime p is a prime whose square p2
Wieferich primes are precisely the primes whose squares are
Let's prove this equivalence:
For a Wieferich prime p: Modulo p2,
2 p = 2,
therefore 2 p2 = 2 p = 2.
This shows that squares of Wieferich primes
are Poulet numbers.
Conversely, if the square p2 of a prime p is a Poulet number,
then p2 divides:
Since p is prime,
each of the (p+1) terms of the square bracket is congruent to 1 modulo p,
and the whole sum is congruent to 1 modulo p.
So, p2 is coprime to the second
factor and it must divide the first; p is thus a Wieferich prime.
The only known Wieferich primes are 1093 and 3511.
Their squares are Poulet numbers but their cubes are not,
so we would have two "counterexamples" to the above result,
if the 3 primes involved were allowed to be equal...
For distinct primes p and q, if
p2 and pq are Poulet numbers,
so is p2 q
in all the examples we have found so far, namely:
The tabulated list
is complete only for the Wieferich prime p = 1093
Primes q for which pq
(and/or p2q ) is a Poulet number :
are (most probably) infinitely many Wieferich primes :
1093 and 3511 are the only Wieferich primes with 15 digits or less.
However, there are probably
infinitely many Wieferich primes...
The following heuristic argument
suggests that there are about ln(ln(n))
Wieferich primes below n :
For any prime p, the residue modulo p2 of
2p-1-1 is a multiple of p
(0, p, 2p, 3p ... (p-1)p). The prime p is a Wieferich prime
when this residue in zero. This is one of p possibilities and
we may thus guess that any prime p
ends up being a Wieferich prime with probability 1/p.
The expected number of Wieferich primes below n would then be fairly close to the
sum of the reciprocal of all primes less than n.
This is roughly ln(ln(n)), which grows without bound...
The above assumption of "equiprobability" is reasonable for the following reason:
For a given prime p, there are p(p-1)
invertible classes (a) modulo p2,
and a(p-1) -1 is congruent to kp for (p-1)
of these, regardless of the choice of k (in particular, k=0).
More generally, for any power pn of a prime p,
the probability is exactly p1-n that we obtain a number
congruent to 1 modulo pn
by raising a random base to the power
of p-1 ("random" bases being chosen so that every invertible
class modulo pn is equiprobable).
Taking this estimate at face value, we expect about
0.0645 Wieferich primes with 16 digits,
0.0606 Wieferich primes with 17 digits,
0.0572 with 18 digits...
The third Wieferich prime could easily have 41 digits or more,
placing it well beyond the reach of any
unless a brilliant shortcut is found.
A Brief History of Wieferich Primes :
Wieferich primes are named after the German number theorist
(1884-1954) who established, in 1909, that any odd prime exponent in a counterexample
to Fermat's Last Theorem would have to be such a prime.
This was a strong result at the time, although it is now seen as
vacuously true: There are no such counterexamples
(Fermat's Last Theorem was proved by
Wiles in 1994/1995).
The first Wieferich prime (1093) was found in 1912, by the German engineer
Waldemar Meissner, of Charlottenburg, father of
Walther Meissner (1882-1974)
of superconductivity fame.
The second Wieferich prime (3511) was discovered in 1922 by the Dutch mathematician
N.G.W.H. Beeger (1884-1965)
who is also remembered for having coined the term
"Carmichael number" in 1950.
In 1910, Dmitri Mirimanov (1861-1945)
put forth base 3
(a Wieferich prime to base 3 may be called a Mirimanov prime).
(2005-04-18) Super-pseudoprimes to Base a The product of distinct primes is necessarily a
weak pseudoprime to base a,
if all the pairwise products are such pseudoprimes.
This is proved like the above result with two simple
generalizations: First, any base a can be used.
Second, once we establish [for any pair of primes (p,q) involved]
that a to the power of q is a modulo p, we may proceed to
chain as many such results as needed to show that a to the power of
the entire product is congruent to a modulo any prime p involved.
The Chinese Remainder Theorem
then shows that the whole product must be a pseudoprime to base a.
For example, a product of several primes from each of the sets
below is called a Super-Poulet,
or superpoulet number
of its composite divisors are Poulet numbers.
(Such a set of 7 primes yields 120 Poulet numbers.)
" super-pseudoprime to base a "
has not caught on (yet).
3 and 7 are easily ruled out, so is 43691
(103´43691 is not a Poulet number).
The other factors are already there, so no further extension is possible...
By contrast, we hit pay dirt with our second 7-factor
We need only examine the factors of
the greatest common divisor of the 7 quantities
2(p-1)-1 (because of a nice property
proved elsewhere on this site).
(275 - 238 +1)
(275 + 238 +1)
7 . 31 . 151 . 601 . 1801 . 100801 .
3 2 . 11 . 251 . 331 . 4051 .
275 - 238 +1
5 3 . 1321 . 63901 . 268501 .
275 + 238 +1
13 . 41. 61 . 101 . 1201 . 8101 .
The 4 new boldfaced prime factors are found to be compatible with underlined factors
(and with each other) resulting in an 11-factor maximal superpoulet
(i.e., a superpoulet number which does not divide any other).
All 2036 (!) composite divisors of the following 64-digit
number are thus Poulet numbers: