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

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

Pseudoprimes

 Pierre de Fermat 
 (1601-1665)
Perhaps, posterity will thank me for having shown  
that the ancients did not know everything.  

Pierre de Fermat (1601-1665)   

Related articles on this site:

Related Links (Outside this Site)

Pseudoprimes & Probable Primes  by Jon Grantham
Pseudoprimes and Carmichael Numbers  by Richard G.E. Pinch
Baillie-PSW primality test  by  Thomas R. Nicely

Wikipedia : Baillie-PSW pseudoprime (1980)   |   Robert Baillie (c.1950-)
Carl Pomerance (1944-)   |   John Selfridge (1927-2010)   |   Samuel Wagstaff (1945-)

 
border
border

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 pseudoprimesFermatiansSarrus 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 D.H. Lehmer in 1950.  See A006935.

Weak pseudoprimes to base  a  not coprime with  a
aComposite values of  n  such that   n  |  an-a   and   gcd (a,n) ¹ 1
2 161038, 215326, 2568226, 3020626, 7866046, 9115426, 49699666, 143742226, 161292286, 196116194, 209665666, 213388066, ... A006935
3 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 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, ...
5 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 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.

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:

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

((((( 4 ) 5 + 3 ) 5 + 1 ) 5 + 2 ) 5 + 1 ) 5 + 2   =   14557
n 1234567 A000027
u + v   5    25    125     625    3125     15625    78125   A000351
u 27571822057 1455745807 A034935
v 318684431068106832318 A048899
  min(u,v)   27571821068106832318 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  

 Come back later, we're
 still working on this one...


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

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.


(2020-09-14)   Powers of a prime  p  which are pseudoprime to base  a.
If pn, q and pq are pseudoprime,  so is  q p 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,  p divides the following:

apn-1 - 1   =   (ap-1)S - 1   =   (ap-1 - 1) [1 + ap-1 + ... + a(S-1)(p-1) ]

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  p  (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    =  a (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)

 Come back later, we're
 still working on this one...


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

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).   Just a joke!

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

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

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

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  pq  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 :
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,  1514527568177848809210967221069334182785475908756709327091,  559791068131697034376217936561708451475280017605178661418575551, P126P146   [list completed on 2020-09-02]

With its 17 cofactors,  35112  just forms a  602-digit  maximal  superpoulet,  with  393216  divisors.  The situation is more complicated for  1093:

Two intersecting maximal super-Poulet numbers are multiples of 1093 :
1st  Maximal
Super-Poulet
(96 divisors)
4733,   112901153,   556338525912325157
1093 2 ,   23140471537,   8861085190774909 2nd  Maximal
Super-Poulet
(1536 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 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:

Some Wieferich primes to base  a :
 a    Primes  p  such that  p 2  divides   a p-1 - 1  Sloane
21093, 3511 ...   (Wieferich primes)A001220
311, 1006003 ...   (Mirimanov primes)A014127
52, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801 ...A123692
666161, 534851, 3152573 ...A212583
75, 491531 ...A123693
 10 3, 487, 56598313 ...A045616
1171 ... 
122693, 123653 ...A111027
132, 863, 1747591 ...A128667

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:

23 × 3 × 52 × 43 × 712 × 211 × 3221 × 7561 × 13421 × 17011 × 45319 × 1623931 × 1649341 × 10047871 × 42437717969530394595211

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:

503272338159270582872376462269361001830032321771592057468791
=   712 × 211 × 3221 × 7561 × 17011 × 1623931
× 1649341 × 10047871 × 42437717969530394595211

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


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

 Come back later, we're
 still working on this one...

  Edouard
Edouard Lucas
 

(2018-07-08)   Lucas Numbers  &  Lucas Pseudoprimes

The  Lucas numbers  (tabulated below)  form a special case of a  Lucas sequence  (namely a  constant-recursive sequence of order 2, of which  my favorite integer sequence is another example).

The Lucas Numbers   (A000032)
n 012345 67891011...n+2
 Ln  2134711 18294776123199...Ln+2 = Ln+Ln+1

 Come back later, we're
 still working on this one...

Lucas Number (5:21)  by  Matt Parker  (Numberphile, 2014-09-22).
How they found the World's Biggest Prime Number (12:31)  by  Matt Parker  (Numberphile, 2016-01-21).

border
border
visits since April 18, 2005
 (c) Copyright 2000-2020, Gerard P. Michon, Ph.D.