Related Links (Outside this Site)

---

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

---

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

---

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

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). Let A be 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)

For a composite number N, a base A  (between 2 and N-2)  which makes the above test return 0 is called a  witness  of N.  If A is a

---

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

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

4625    =    5 3 . 37

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

By factoring  68 ⁴ -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.

... / ...