Pseudoprimes Rare Composite Numbers with
Properties Typical of Primes
(2003-11-19) Pseudoprimes to Base a A composite number n is a pseudoprime to base a if it divides
(a n-1-1).
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
Fermat pseudoprimes,
Fermatians,
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).
There's also a weaker definition
of the term for which this need not be so.
(2003-11-19) Weak Pseudoprimes to Base a A weak pseudoprime to base a is a composite number n dividing
a n-a.
A pseudoprime to base a (under the
usual definition) satisfies this condition.
Conversely, a weak pseudoprime that's coprime
with the base is a pseudoprime in the usual sense,
otherwise this may or may not be the case.
There are no even pseudoprimes to base 2 in the usual sense,
but the lowest even "pseudoprime" in this weak sense is 161038,
which was discovered by D.H. Lehmer in 1950.
See A006935.
Weak
pseudoprimes to base a
not coprime with a
a
Composite values of n such that
n | an-a and
gcd (a,n) ¹ 1
(2004-01-24)
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
( HINT:
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:
k
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...
A039772.
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
integer):
14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122...
A005277.
( Prime numbers have been included in the table below. )
k
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
Euler pseudoprime
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.
Strong pseudoprimes to base 2 are called strong Fermat pseudoprimes.
(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
(n-a) is.
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
opposite 5-adic
integers whose square is -1 = ...4444444444
namely:
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...
k
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
(¼)k.
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.
'
fnPprime(N)
local Q,J,K,A,R
'
' 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
A=(N-3)\2:R=irnd:while R>=A:R\=2:wend:A=R+2
'
' 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)
A=modpow(A,2,N)
next J
return(A=N-1)
If the above test returns 0
for a composite number N and a base A
(between 2 and N-2) then A
is called a witness of N.
If A is a witness of N, so is N-A.
Karsten Meyer
(Germany. 2005-04-16; e-mail)
Related Pseudoprimes
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 )
Therefore,
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,
43´127 and
15´127 are Poulet numbers, but
15´43´127
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
Wieferich primes...
Generalization :
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,
namely:
Theorem :
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 .
(2020-09-14) Powers of a prime p which are pseudoprime to base a.
If pn, q and pq are pseudoprime, so is q pm for m ≤ n (if GCD(p,q)=1).
We have
pn - 1 = (p - 1) S
where S is congruent to 1 modulo p, viz.
If n = 1, then S = 1
If n = 2, then S = 1 + p
If n = 3, then S = 1 + p + p2
If n = 4, then S = 1 + p + p2 + p3
Etc.
By definition,
if pn is pseudoprime to base a, pn divides the following:
Because p is prime, every term in the square bracket is congruent to 1 modulo p.
There are S such terms, so the whole bracket is congruent to S, which is equal to 1 modulo p.
That bracket is thus coprime with pn. Since pn
divides the product of the two factors and is coprime with the second, it must divide the first. So;
pn divides ap-1 - 1
Therefore, pm divides
ap-1 - 1 for any m ≤ n
(in particular, for m = 1).
We may chain the following congruences modulo pm (every congruence is obtained by raising
the previous one to the power of p):
a =
a p =
a p2 = ... =
a pm (modulo pm )
This shows that pm is a weak pseudoprime to base a.
It's coprime with a (because p is) and so it is a pseudoprime to base a.
Because q is a pseudoprime:
a q
=
ap (mod q)
Raise to the power of q :
a qp
=
a p (mod q)
Since p1p2 is a Poulet number:
2 p1p2
=
2 (mod p1) [or modulo p1p2 ]
These two equalities imply:
2 p2
=
2 (mod p1)
What's true of p2 is true of p3 :
2 p3
=
2 (mod p1)
Chain the previous two results:
2 p2p3
=
2 p3 = 2 (mod p1)
Raise to the power of p1 :
2 p1p2p3
=
2 p1 = 2 (mod p1)
(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
(A050217)
as all
of its composite divisors are Poulet numbers.
(Such a set of 7 primes yields 120 Poulet numbers.)
The term
" super-pseudoprime to base a "
has not caught on (yet).
The above includes all examples with at least 7 prime factors
of 6 digits or less. Too bad
2053´90289
is not a Poulet number...
(2005-04-18) Maximal super-pseudoprimes :
A super-pseudoprime to base a is
maximal if it does not divide any other.
Let's show that the first (7-factor)
super-Poulet number listed above is maximal.
Since 103 is one of its factors, any additional prime factor would divide:
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
superpoulet:
We need only examine the factors of
2300-1,
the greatest common divisor of the 7 quantities
2(p-1)-1 (because of a nice property
proved elsewhere on this site).
2300 -1
=
(275 -1)
(275 +1)
(275 - 238 +1)
(275 + 238 +1)
275 -1
=
7 . 31 . 151 . 601 . 1801 . 100801 .
10567201
275 +1
=
3 2 . 11 . 251 . 331 . 4051 .
1133836730401
275 - 238 +1
=
5 3 . 1321 . 63901 . 268501 .
13334701
275 + 238 +1
=
13 . 41. 61 . 101 . 1201 . 8101 .
1182468601
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:
The relevant factorization
shows that the third of our 7-factor examples divides a
16-factor maximal super-Poulet number
(147 digits & 65519 Poulet divisors):
Similarly,
our first 8-factor example is seen to divide
a 269-digit maximal
super-Poulet number with 22 prime factors (4194281 composite Poulet divisors):
By factoring 68 4 -1,
the first of those can easily be proved to be maximal.
Using a tougher factorization
the same can be proved for the second one.
(2005-04-18) Wieferich primes
and some of their Poulet multiples
A Wieferich prime p is a prime whose square p2
divides 2p-1-1.
Wieferich primes are precisely the primes whose squares are
Poulet numbers.
Let's prove this equivalence:
For a Wieferich prime p: Modulo p2,
2 p = 2,
therefore 2 p2 = 2 p = 2.
Thus, squares of Wieferich primes
(A001220) are Poulet numbers.
Conversely, if the square p2 of a prime p is Poulet,
then p2 divides:
As p is prime,
each of the (p+1) terms in the square bracket is congruent to 1 modulo p,
and the whole sum is 1 modulo p.
Thus, p2 is coprime to the second
factor and divides the first, proving p to be a Wieferich prime.
The only known Wieferich primes are 1093 and 3511.
Their squares are Poulet numbers but their cubes are not, which goes to show
that the above result wouldn't hold if the three primes
were allowed to be equal.
On the other hand, for distinct primes p and q,
we found (for now) that if p2
and pq are Poulet numbers,
then p2 q is too.
We just checked all prime factors
q of 2p-1-1 for both known Wieferich primes (p).
This table
is complete until a third Wieferich prime (p) is found.
p
Primes q for which pq
(and/or p2q ) is a Poulet number :
There
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
computer search,
unless a brilliant shortcut is found.
A Brief History of Wieferich Primes :
Wieferich primes are named after the German number theorist
Arthur Wieferich
(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
Andrew
Wiles in 1994/1995).
The first Wieferich prime (1093) was found in 1912, by the German engineer
Waldemar Meissner (1852-1928) of Charlottenburg.
(Waldemar is the 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).
Other bases
followed:
A174422 gives
the least Wieferich prime to base a when a is prime.
71 is the only Wieferich prime to base 11 I could find.
Its size is just right, to exemplify how
all maximal pseudoprimes to base a which are multiples
of a prescribed prime p.
Let's do that for a = 11 and p = 71.
First, we factorize 1170-1 and underline 71 and every prime factor
q such that 11x-x is divisible by x = 71 q.
We obtain:
We may take one of the underlined factors and see what
other underlined factors it can multiply into it to obtain a product x
such that 11x-x is divisible by x.
We find that all of them can.
(This need not be so, as the example of 1093 in base 2 shows).
At this point, we may suspect that a super-pseudoprime to base 11 is
at hand and establish that much by checking that all
products of two factors are pseudoprimes to base 11.
It's maximal because all possible multiplicands have been ruled out in the first stage.
Thus, there's only one maximal pseudoprime to base 11 divisible by 71.
It has 60 digits and 768 divisors:
(2005-05-08) Any Odd Prime Divides a Poulet Number [?]
It seems that any prime which does not divide base a
has a multiple which is a pseudoprime to base a.
