home | index | units | counting | geometry | algebra | trigonometry & functions | calculus analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

# Pseudoprimes

Perhaps, posterity will thank me for having shown
that the ancients did not know everything.

Pierre de Fermat (1601-1665)

### Related Links (Outside this Site)

Pseudoprimes & Probable Primes  by Jon Grantham
Proving Primality in Polynomial Time by Chris Caldwell.
Pseudoprimes and Carmichael Numbers  by Richard G.E. Pinch
Sloane's On-Line Encyclopedia of Integer Sequences

## PseudoprimesRare 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 (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   FermatiansSarrus 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.

Carmichael numbers  are in  bold type.
aPseudoprimes to Base a Sloane's
2341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821 ... A001567
3 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465... A005935
415, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271... A020136
5 4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611... A005936
635, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465... A005937
7 6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277... A005938
89, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511... A020137
9 4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703... A020138
109, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729... A005939
11 10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330... A020139
1265, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105... A020140
13 4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785... A020141
14 15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541... A020142
15 14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821... A020143
16 15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105... A020144
(*) 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61... A000040
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341... A002997

Number of pseudoprimes to base a with n or fewer decimal digits:
a 1 2345 n = 6n = 7n = 8n = 9n=10Sloane's
2 0032278245750 2057559714884 A055550
3 0162378246760 21555804
4 039471534641347 380510173
5 1152073248745 19545239
6 01527104301 89523146204
7 1261673234 65917974950
8 152070218678 1993540714629
9 251751164478 1418384810170
10 14113190271 76620915599
11 03112989250 69519245077
12 02933127378 109129337781
13 25122891274 75019715157
14 03103296283 81721555848
15 0142070210 62817474719
16 041264200607 1749498413422
(*) 42516812299592 78498664579576145550847534 ... A006880
00171643105 2556461547 A055553

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

Paul Poulet (1887-1946)   |   Pierre Frédéric Sarrus (1798-1861)

(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 Lehmer in 1950.  See A006935.

2 3 a Composite values of  n  such that   n  |  an-a   and   gcd (a,n) ¹ 1 161038, 215326, 2568226, 3020626, 7866046, 9115426, 49699666, 143742226, 161292286, 196116194, 209665666, 213388066, ... A006935 6, 66, 561, 726, 7107, 8205, 8646, 62745, 100101, 140097, 166521, 237381, 237945, 566805, 656601, 876129, 1053426, 1095186, 1194285, 1234806, 1590513, 1598871, 1938021, 2381259, 2518041, 3426081, 4125441, 5398401, 5454681, 5489121, 5720331, 5961441, 6498426, 7107171, 7252521, 7876506, 7912311, 8078961, 8141001, 8873565, 8968065, 10367841, 11845761, 11921001, 12225585, 13297197, 14664729, 15358641, ... 4, 6, 12, 28, 66, 186, 276, 532, 946, 1068, 2044, 2046, 2926, 8196, 8614, 8646, 11476, 15996, 24564, 25156, 34716, 38836, 40132, 45676, 66788, 67166, 76798, 80476, 91636, 106926, 141526, 144886, 161038, 173482, 180246, 188508, 199606, 215326, 242506, 243156, 251252, 256026, 265826, 266476, 275466, 276396, 383846, 427636, 489958, 501796, 504274, 531586, 540606, 541486, 565516, 596926, 621754, 729444, 819996, 880716, 922006, 971836, 988012, 1005466, ... 10, 15, 20, 65, 190, 310, 435, 1105, 2465, 3565, 3820, 4495, 6735, 8290, 10585, 20345, 20710, 26335, 41665, 51490, 62745, 69595, 72010, 120205, 125420, 157510, 168545, 191890, 193285, 195315, 215605, 238855, 278545, 292965, 384865, 446755, 449065, 451905, 465310, 566805, 570865, 583185, 709435, 746785, 790210, 825265, 830705, 903610, 918205, 924265, 984385, 1050985, ... 6, 10, 15, 21, 30, 105, 190, 231, 430, 435, 561, 777, 1221, 1866, 2121, 2553, 2955, 3885, 5061, 5565, 5662, 6531, 15051, 20554, 23331, 24670, 26746, 28810, 30970, 32865, 34521, 42801, 56001, 62745, 71841, 72010, 76798, 85695, 86961, 88689, 98385, 101386, 106491, 123321, 135201, 136185, 142401, 147201, 227217, 245805, 265881, 294261, 302253, 323121, 360465, 369370, 435711, 468730, 511161, 583185, 656601, 659631, 697971, 744051, 839805, 987735, 1007769, ...

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

kNumbers that are pseudoprimes to one in k of their coprime bases:
1  561, 1105, 1729, 2465, 2821, 6601, 8911, 10585 ... [Carmichael numbers]
2  4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, 23001, 30889...
3  9, 21, 45, 65, 105, 133, 231, 341, 481, 645, 1541, 3201, 4033, 4371, 5461...
4  8, 10, 12, 28, 66, 85, 435, 451, 946, 1387, 2047, 3277, 3367, 5551, 8695...
5  25, 33, 165, 217, 325, 385, 793, 1045, 1065, 2665, 3565, 4123, 4681...
6  14, 18, 35, 39, 153, 247, 259, 671, 861, 949, 1035, 1247, 1649, 1785...
7  49, 145, 301, 637, 781, 1885, 1921, 2413, 3913, 5365, 5713, 6541, 7345...
8  16, 20, 24, 30, 51, 52, 70, 190, 276, 286, 532, 742, 1261, 2806, 2926...
9  27, 57, 63, 117, 185, 273, 285, 585, 651, 1001, 1221, 1281, 1365, 1417...
10  22, 55, 75, 175, 205, 403, 425, 427, 697, 1111, 2059, 3439, 4141, 6943...
11  69, 121, 345, 469, 805, 1771, 2737, 3751, 3781, 4961, 5785, 6097, 7381...
12  26, 36, 42, 76, 186, 195, 221, 357, 511, 765, 1271, 1581, 3281, 5963...
13  169, 265, 553, 1441, 2041, 3445, 4081, 7189, 11713, 13345, 15505...
14  87, 559, 4699, 4753, 6409, 8041, 12871, 13051, 14065, 16745, 32021...
15  77, 93, 99, 225, 305, 369, 429, 465, 525, 589, 925, 1661, 1825, 2121...
16  32, 34, 40, 48, 60, 112, 130, 176, 232, 246, 255, 364, 370, 496, 595, 616...
17  289, 721, 3585, 4521, 5833, 8905, 9373, 13699, 22351, 22681, 25345...
18  38, 54, 95, 111, 135, 315, 365, 763, 969, 1241, 1431, 1991, 3015, 3683...
19  361, 2101, 2977, 9637, 13357, 17701, 22645, 30457, 31201...
20  44, 50, 123, 124, 154, 715, 1309, 1834, 2035, 2275, 2425, 2805, 3133...

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. )
kNumbers n that are pseudoprimes to bases of k residue classes modulo n:
1  2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 30, 32, 34, 36, 38, 40, 42, 44...
2  3, 9, 27, 81, 243, 729, 2187, 6561, 19683...   [ 3m ]
3  28, 52, 70, 76, 112, 124, 130, 148, 154, 172, 196, 208, 238, 244, 268, 280...
4  5, 15, 21, 25, 33, 35, 39, 51, 55, 57, 63, 69, 75, 77, 87, 93, 95, 99, 111...
5  66, 176, 186, 246, 366, 396, 426, 506, 606, 656, 726, 786, 806, 836, 906...
6  7, 49, 343, 2401, 16807...   [ 7m ]
7  232, 344, 568, 638, 904, 1016, 1044, 1450, 1548, 1562, 1576, 1688, 1856...
8  45, 117, 195, 225, 245, 255, 261, 315, 333, 399, 405, 455, 477, 483, 495...
9  190, 364, 370, 730, 868, 874, 910, 988, 1090, 1204, 1216, 1270, 1330...
10  11, 121, 1331, 14641...   [ 11m ]
11  276, 782, 804, 1068, 1794, 2300, 2388, 3026, 3312, 3752, 3818, 3972...
12  13, 169, 175, 475, 775, 847, 1075, 1675, 1975, 2023, 2197, 2299, 2575...
13  1106, 2120, 2198, 3498, 4382, 4876, 5214, 5240, 6254, 7268, 7632, 7658...
14  none     [ 14  is a nontotient ]
15  286, 496, 616, 976, 1066, 1426, 1606, 1846, 2266, 2296, 2416, 2896...
16  17, 65, 85, 105, 145, 153, 165, 185, 205, 221, 265, 273, 285, 289, 305...
17  1854, 2466, 4302, 5526, 7124, 7362, 7974, 8858, 11034, 11646, 12360...
18  19, 361, 6859...   [ 19m ]
19  3820, 4580, 8380, 9140, 11078, 11420, 12940, 15220, 21984, 22060...
20  891, 2511, 3971, 5751, 9251, 9801, 10611, 12231, 15471, 17091, 20331...

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

(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 ontegers whose square is -1 = ...4444444444  namely:

...33314300301131300030330421304240422331102414131141421404340423140223032431212
...11130144143313144414114023140204022113342030313303023040104021304221412013233

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.

 1 2 3 4 5 6 7 n A000027 u + v 5 25 125 625 3125 15625 78125 A000351 u 2 7 57 182 2057 14557 45807 A034935 v 3 18 68 443 1068 1068 32318 A048899 min(u,v) 2 7 57 182 1068 1068 32318 A034939

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 0 3, 9, 15, 21, 27, 33, 35, 39, 45, 51, 55, 57, 63, 69, 75, 77, 81, 87, 93, 95, ... 1 5, 25, 125, 625, 3125, 15625, 78125, ... 5n ... 2 7, 49, 65, 85, 145, 175, 185, 205, 221, 265, 305, 343, 365, 377, 385, 425, ... 3 4 11, 121, 231, 561, 651, 861, 891, 1001, 1221, 1281, 1331, 1491, 1551, ... 5 13, 169, 2197, 28561, ... 13n ... 6 435, 645, 1065, 1653, 1695, 1905, 2451, 2955, 3165, 3585, 4047, 4089, ... 7 17, 289, 4913, 83521, ... 17n ... 8 19, 91, 133, 217, 247, 259, 301, 325, 361, 403, 427, 469, 511, 553, ... 9 10 23, 529, 697, 1035, 1241, 1513, 2329, 2553, 2993, 3015, 3059, 3649, ... 11 12 1431, 2133, 3537, 4239, 5565, 8295, 8451, 9699, 11961, 12455, 13755, ... 13 29, 841, 24389, 707281, ... 29n ... 14 31, 961, 1105, 1771, 1885, 2431, 2665, 3145, 3445, 4081, 5185, 5785, ... 15 16 3605, 9453, 10745, 14315, 16491, 17613, 21183, 21455, 23427, 28119, ... 17 37, 1369, 50653, 1874161, ... 37n ... 18 7449, 8931, 16341, 17633, 17823, 21965, 22269, 25233, 29223, 29679, ... 19 41, 1681, 68921, 2825761, ... 41n ... 20 43, 1849, 3655, 4495, 4901, 9367, 10795, 10879, 11005, 11803, 12685, ... 21

(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, p)  prove that, when the 3 numbers   p1p2, p1p3 and p2p3  are Poulet numbers, then  p1p2p3  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 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  p, p, p, pp, pp3,  pp3  are weak-pseudoprimes to base  a  (or primes)  then so is  ppp.

(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.  This shows that squares of Wieferich primes  (A001220)  are Poulet numbers.

Conversely, if the square p2 of a prime p is a  Poulet number,  then p2 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, 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 resultif  the 3 primes involved were allowed to be equal...

For  distinct  primes p and q, if  p2  and  pq  are Poulet numbers, so is   pq   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:

MaximalSuper-Poulet(236 Poulet divisors) 4733,   112901153,   556338525912325157 1093 2 ,   23140471537,   8861085190774909 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 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:

 Sloane a Primes  p  such that  p 2  divides   a p-1 - 1 2 1093, 3511 ...   (Wieferich primes) A001220 3 11, 1006003 ...   (Mirimanov primes) A014127 5 2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801 ... A123692 6 66161, 534851, 3152573 ... A212583 7 5, 491531 ... A123693 10 3, 487, 56598313 ... A045616 11 71 ... 12 2693, 123653 ... A111027 13 2, 863, 1747591 ... A128667

A Wieferich Prime Search  (up to 6.7 1015 )   by  François G. Dorais  and  Dominic Klyve  (2011).

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

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

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

2 102 - 1   =   3 2  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  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:

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

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

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  ap-1-1   is divisible by  p3  for two different prime values of p , namely:  5 and 113  (and, almost certainly, no other).

Two  maximal super-pseudoprimes  to base 68  are thus divisible by  cubes :

 4625    =    5 3 . 37 ( 1.0457974... 10106 )    =    113 3 . 10193 . 1145565031404704513 .  620712448371732926474772025689944913040651041015217889164158638163856301549281

By factoring  68 4 -1,  the first of those can be proved  maximal  with pencil and paper.  Such a proof for the second number involves a tougher factorization.

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

... / ...