Final Answers
© 2000-2005 Gérard P. Michon, Ph.D.

Pseudoprimes

• Pseudoprimes to base a.  Poulet numbers  are pseudoprimes to base 2.
• Weak pseudoprimes to base a :  Composite integers  n  which divide  (aⁿ-a).
• Strong pseudoprimes to base a  are less common than Euler pseudoprimes.
• Counting the bases  to which a composite number is a pseudoprime.
• Rabin-Miller Test:  An efficient and trustworthy  stochastic  primality test.
• The product of 3 primes  is a pseudoprime when all  pairwise  products are.
• Wieferich primes  are scarce but there are (probably) infinitely many of them.
• A product of distinct primes  is a pseudoprime when all pairwise products are.

Related articles on this site:

• Fermat's little theorem:   For any prime p, a^p-1 is 1 modulo p, unless p divides a.
• Carmichael Numbers:  An absolute pseudoprime  n divides  (aⁿ - a)  for any a.
• Prime factorizations:  Resolving composite integers into their prime factors.
• Modular arithmetic: The algebra of congruences, formally introduced by Gauss.
• Number Theory and Numeration.
  • Multiplicative functions and Dirichlet convolution.
• Least Carmichael Multiples of Small Primes:  For all odd primes below 10000.
• Carmichael Multiples of most odd numbers coprime to their totients, up to 3000.

---

(2003-11-19)   [Fermat] 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 which do too.

The most studied pseudoprimes are pseudoprimes to base 2, which have been variously called   Poulet numbers,  Fermatians,  or  Sarrus numbers...  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 to each other  ( HINT:   un + va  = 1,  for some integers u and v).  There's a rarely used weaker definition of the term for which this need not be so.

(*)   The next-to-last line of each table tallies primes, whereas the last line tallies Carmichael numbers  (which are pseudoprimes to most bases).

---

(2003-11-19)   Weak Pseudoprimes to Base  a
A weak pseudoprime to base a is a composite number n dividing  a ⁿ-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 Lehmer in 1950.  See A006935.

---

(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 ² = 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 2^k + 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.  A strong pseudoprime is a composite number for which the same thing holds.

---

(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:

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 14^th line in the table below is empty, as would be the k^th 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.

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)   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!

---

Karsten Meyer  (Germany. 2005-04-16; e-mail)   Related Pseudoprimes
For 3 distinct odd primes  (p₁, p₂, p₃ )  prove that, when the 3 numbers   p₁p₂, p₁p₃ and p₂p₃  are Poulet numbers, then  p₁p₂p₃  is too.

 

Because  p1 is a prime:		2 p1	=	2  (mod p1)
Raise to the power of p2 :		2 p1p2	=	2 p2 (mod p1)
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)

The same argument proves 2 ^p₁p₂p₃ congruent to 2 modulo p₁, p₂ or p₃.  As these 3 moduli are pairwise coprime, the Chinese Remainder Theorem implies:

2 ^p₁p₂p₃  =  2  (mod  p₁p₂p₃ )

Therefore,  p₁p₂p₃  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  (as 15 is not prime).  We also assumed that the three primes were distinct (see last part of the proof).  The case where two of them are equal is discussed next; the primes involved turn out to be what are called  Wieferich primes...

---

(2005-04-18)   Wieferich primes and some of their Poulet multiples
A Wieferich prime p is a prime whose  square  p²  divides  2^p-1-1.

Wieferich primes are precisely the primes whose squares are Poulet numbers.  Let's prove this equivalence: 
For a Wieferich prime p:  Modulo  p²,   2 ^p  = 2,  therefore  2 ^p2  = 2 ^p  = 2.  This shows that squares of Wieferich primes  (A001220)  are Poulet numbers.

Conversely, if the square p² of a prime p is a  Poulet number,  then p² divides:

2 ^p2-1 -1   =   2 ^(p-1)(p+1) -1   =   ( 2 ^(p-1) -1 )  [ 1 + 2 ^(p-1) + ... + 2 ^p(p-1) ]

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, p² 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  p²  and  pq  are Poulet numbers, so is   p² q   in all the examples we have found so far, namely:

The tabulated list is complete only for the Wieferich prime  p = 1093

p	Primes  q  for which  pq  (and/or  p2q )  is a Poulet number :
1093	4733, 21841, 503413, 1948129, 112901153, 23140471537, 467811806281,  4093204977277417,  8861085190774909, 556338525912325157,   86977595801949844993, 275700717951546566946854497, 3194753987813988499397428643895659569
3511	10531,  1024921,  1969111,  4633201,  409251961,  21497866557571 ... 194900834792501371 ... 4242734772486358591 ... 85488365519409100951 ... 255375215316698521591 ... 1439538040790707946401 ... 5302306226370307681801 ... 2728334536034592865339299805712535332071 ...

This table is based on the relevant factorizations  (incomplete for  p = 3511 ).  So far, the above factors for 3511 form a  single  superpoulet.  Not so for 1093:

Two intersecting maximal super-Poulet numbers are multiples of 1093 :

Maximal Super-Poulet (236 Poulet divisors)	4733,   112901153,   556338525912325157
	1093 2 ,   23140471537,   8861085190774909	Maximal Super-Poulet (3060 Poulet divisors)
21841,   503413,   1948129, 467811806281, 4093204977277417,  86977595801949844993, 275700717951546566946854497, 3194753987813988499397428643895659569

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 p² of  2^p-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 p²,  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 pⁿ of a prime p, the probability is exactly  p^1-n  that we obtain a number congruent to  1 modulo  pⁿ  by raising a random base to the power of p-1  ("random" bases being chosen so that every invertible class modulo pⁿ 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.

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 by W. Meissner in 1912, the second (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.

Similar studies started with base 3 (Mirimanov, 1910): 11, 1006003 ...A014127

---

(2005-04-18)   Superpseudoprimes 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  " superpseudoprime  to base  a "  has not caught on  (yet). 

{ 103, 307, 2143, 2857, 6529, 11119, 131071 }
{ 601, 1201, 1801, 8101, 63901, 100801, 268501, ... }
{ 709, 2833, 3541, 12037, 31153, 174877, 184081, ... }
{ 2161, 15121, 21601, 30241, 49681, 54001, 246241 }
{ 3037, 6073, 9109, 85009, 109297, 176089, 312709 }
( 2833, 11329, 31153, 84961, 96289, 184081, 339841 }
( 883, 3529, 22051, 126127, 309583, 311347, 748819 }
{ 6421, 12841, 51361, 57781, 115561, 192601, 205441 }
{ 7297, 14593, 32833, 43777, 299137, 525313, 671233 }
{ 7841, 35281, 78401, 101921, 141121, 258721, 736961 }
{ 7841, 78401, 101921, 141121, 258721, 689921, 736961 }

Here are some 8-factor  superpoulets  (each has 247 Poulet divisors).

{ 1861, 5581, 11161, 26041, 37201, 87421, 102301, 316201, ... }
{ 2383, 6353, 13499, 50023, 53993, 202471, 321571, 476401 }
{ 2053, 8209, 16417, 57457, 246241, 262657, 279073, 525313 }
{ 1801, 8101, 54001, 63901, 100801, 115201, 617401, 695701 }
{ 8209, 16417, 57457, 90289, 246241, 262657, 279073, 525313 }
{ 30781, 61561, 123121, 215461, 246241, 430921, 523261, 954181 }

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... 

Maximal Superpseudoprimes :

A superpseudoprime 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:

2 ¹⁰² - 1   =   3 ²  7  103  307  2143  2857  6529  11119  43691  131071

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  2³⁰⁰-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:

601 . 1201 . 1801 . 8101 . 63901 . 100801 . 268501 . 10567201 . 13334701 . 1182468601 . 1133836730401

The proper factorization shows that the third of our 7-factor examples divides a 16-factor maximal super-Poulet number (147 digits & 65519 Poulet divisors):

709 . 2833 . 3541 . 12037 . 31153 . 174877 . 184081 . 5397793 . 5521693 . 94789873 . 27989941729 . 104399276341 . 4453762543897 . 20847858316750657 . 1898685496465999273 . 2995240087117909078735942093

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):

1861 . 5581 . 11161 . 26041 . 37201 . 87421 . 102301 . 316201 . 4242661 . 52597081 . 364831561 . 2903110321 . 8973817381 . 11292210661 . 76712902561 . 103410510721501 . 29126056043168521 . 3843336736934094661 . 24865899693834809641 . 57805828745692758010628581 . 9767813704995838737083111101 . 934679543354395459765322784642019625339542212601

(2005-04-30)   Base  68 :

When  a = 68,  the integer  a^p-1-1   is divisible by  p³  for two different prime values of p , namely:  5 and 113  (and, almost certainly, no other).

Two  maximal superpseudoprimes  to base 68  are thus divisible by  cubes :

4625    =    5 3 . 37

( 1.0457974... 10106 )    =    113 3 . 10193 . 1145565031404704513 .  620712448371732926474772025689944913040651041015217889164158638163856301549281

The first of these can be proved to be  maximal  using only pencil and paper.  ( HINT:  Factoring into primes the number  68 ⁴ -1  is comparatively easy.)

---

(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.

... / ...