Related Links (Outside this Site)

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

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

(*) � 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 ⁿ-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.

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

More generally, if� 2k+3� is prime, then the number� (2k+3)ⁿ� 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...

(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� (p₁, p₂, p_3�)� 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 says:

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� (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� p₁, p₂ and p₃ are pairwise coprime and if the six numbers� p_1�, p_2�, p_3�, p_1�p_2�, p_1�p₃,� p_2�p₃� are weak-pseudoprimes to base� a� (or primes)� then so is� p_1�p_2�p_3�.

(2020-09-14) _� Powers of a prime� p� which are pseudoprime to base� a.
If pⁿ, q and pq are pseudoprime,� so is� q p^m� for m ≤ n� (if GCD(p,q)=1).

We have � pⁿ - 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 + p²
• If� n = 4,� then � S �=� 1 + p + p² + p³
• Etc.

By� definition,� if� pⁿ� is pseudoprime to base� a,� p^n� divides the following:

a^pn-1 - 1 � = � (a^p-1)^S - 1 � = � (a^p-1 - 1) [1 + a^p-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� pⁿ.� Since� pⁿ� divides the product of the two factors and is coprime with the second, it must divide the first.� So;

pⁿ � divides � a^p-1 - 1

Therefore,� p^m � divides� a^p-1 - 1� for any� m�≤�n� (in particular, for� m�=�1).� We may chain the following congruences modulo� p^m�� (every congruence is obtained by raising the previous one to the power of p^�):

a �=� a ^p �=� a ^p2 �=� ... �=� a ^pm � (modulo� p^m )

This shows that� p^m� 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 p�(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).�

{ 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 ¹⁰² - 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 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� 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 super-pseudoprimes� to base 68� are thus divisible by��cubes�:

By factoring� 68 ⁴ -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� 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.� Thus,� squares of Wieferich primes� (A001220)� are Poulet numbers.

Conversely, if the square p² of a prime p is� Poulet,� 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) ]

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,� p² 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��p²� and� pq� are Poulet numbers, then� p^2�q� is too.� We just checked� all�prime factors� q� of� 2^p-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, P126,� P146 � [list completed on 2020-09-02]

With its 17 cofactors,� 3511²� 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 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.

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

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� 11⁷⁰-1� and underline 71 and every prime factor� q� such that� 11^x-x� is divisible by� x�=�71�q.� We obtain:

2³ � 3 � 5² � 43 � 71² � 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� 11^x-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
= � 71² � 211 � 3221 � 7561 � 17011 � 1623931
� 1649341 � 10047871 � 42437717969530394595211

A Wieferich Prime Search� (up to 6.7 10¹⁵ ) � 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.

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

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