(2003-11-19) A composite number n is a pseudoprime to basea if it divides(a n11).
Fermat's Little Theorem states thatany prime number n has this property. Most authors callpseudoprime only the rarecompositenumbers that do.
The most studied pseudoprimes arepseudoprimes to base 2,which have been variously called Fermat pseudoprimes, Fermatians, Sarrus numbers (1819) and Poulet numbers (1926) ... The unqualified term "pseudoprime" normally meansa pseudoprime to base 2.
Under this definition, if n is a pseudoprime to basea, then n andaare necessarilycoprime (: un + va = 1, for some integers u and v).
There's also aweaker definitionof the term for which this need not be so.
() The next-to-last line of each table talliesprimes, whereas the last linetallies Carmichael numbers (which are pseudoprimes tomost bases).
(2003-11-19) A weak pseudoprime to basea is a composite number n dividing a na.
A pseudoprime to basea (under theusual definition) satisfies this condition.
Conversely, aweak pseudoprime that'scoprimewith the base is a pseudoprime in the usual sense,otherwise this may or may not be the case.
There are noeven 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. SeeA006935.
Weakpseudoprimes to base a not coprime with a
a
Composite values of n such that n | an-a and gcd (a,n) 1
(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 theresidue class of the basea modulo n.
For example,when n is 91 there are36 such residues classes. We may observe that 91 is thuscoprime totwice as many bases as it's a pseudoprime to (72 is theEuler totient of 91). In fact, it's easy to see that theEuler totient of an integer must alwaysbe amultipleof the number of residue classes of bases to which this integer is a pseudoprime (: The residues modulo n whose q-th power is unity formasubgroup of the residues coprime to n.)
The ratio (k) is 1 forCarmichael numbers. It's 2 for n = 91and other composite numbers listed on the second line of the following table:
k
Numbers that are pseudoprimes to one in k of their coprime bases:
When n1 and (n) are coprime,then n isonly a pseudoprime in thetrivialcase of a base congruent to 1 modulo n. This corresponds to theeven numbers appearing in thefirst line of the following table. Theother 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 linefor any k that's a nontotient (an even number which is not theEuler totient ofanyinteger): 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. )
k
Numbers n that are pseudoprimes to bases of k residue classes modulo n:
Anyodd composite n is a pseudoprime to bases of at leasttwo residueclasses (1 and n-1). Unless it's a power of 3,it is a pseudoprime to someother base.
The number of bases a, between 1 and n-1, for which n divides a n1 1 is:
gcd ( n-1 , p-1 )
p | n
(2005-04-19) Strong pseudoprimes are less common than pseudoprimes to basea.
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 1and (n-1)/2 is itself even,the idea may be iterated: For a prime n, raising the base to the powerof (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 compositeand 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) 75% to 100% of the bases of an odd composite are witnesses.
We may ask ofstrong pseudoprimes the same question as that investigatedabove for ordinary pseudoprimes: Given an odd composite number n, how many nontrivial bases is ita strong pseudoprime to?
It turns out that many odd composites have no nontrivialnonwitnesses (for such numbers, the stochastic Rabin-Miller test describedbelow will always produce the same result). Next in line are the numbers which have only one nontrivialpair of nonwitnesses... Those numbers are rare but theyare surprisingly easy to describe: They are powers of 5.
A nonwitness of a power of 5 can be elegantly characterized as equal to theresidue, modulo that power, of one of the following twoopposite5-adicintegers whose square is -1 = ...4444444444 namely:
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 ofthe 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, whichis the larger of the two nonwitnesses of the sixth power of 5.
More generally, if 2k+3 is prime, thenthe number (2k+3)n has exactly k nontrivial pairs of nonwitnesses. Furthermore, if that prime iscongruent to 1 modulo 4, then those powersare the only such numbers...
k
Odd numbers with exactly k nontrivial pairs of nonwitnesses
(2005-04-19) A given composite number fails it for over 75% of the choices fora.
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 efficientlyif 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 creaturewill ever see a composite number pass this test 50 times!
Here's a complete 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=-Nif 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:wendA=(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 Kif A=N-1 then cancel for:return(1)A=modpow(A,2,N)next Jreturn(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) For 3 distinct odd primes (p1, p2, p3 ) prove that, when the 3 numbers p1p2, p1p3 andp2p3 arePoulet numbers,then p1p2p3 is too.
The same argument proves2 p1p2p3 congruent to 2modulo p1, p2 or p3. As these 3 moduli are pairwise coprime, theChinese Remainder Theorem says:
2 p1p2p3 = 2(mod p1p2p3)
Therefore, p1p2p3 isindeed a Poulet number (a pseudoprime to base 2)
The above conclusion may not hold if the premises aren't all true. For example, 1543, 43127 and 15127 are Poulet numbers, but 1543127 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 invokedonly 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:
If p1, p2 and p3 are pairwise coprimeand if the six numbers p1 , p2 , p3 ,p1 p2 , p1 p3, p2 p3 areweak-pseudoprimes to base a (or primes) then so is p1 p2 p3 .
(2020-09-14) If pn, q and pq are pseudoprime, so is q pm 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, pn divides the following:
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 ap1 1
Therefore, pm divides ap1 1 for any m ≤ n (in particular, for m = 1). We may chain the following congruences modulo pm (every congruence is obtained by raisingthe 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
=
ap (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) The product of distinct primes is necessarily aweak pseudoprime to base a,if all thepairwise products are such pseudoprimes.
This is proved like theabove result with two simplegeneralizations: First, any basea can be used. Second, once we establish [for any pair of primes (p,q) involved] thata to the power of q isa modulo p, we may proceed tochain as many such results as needed to show thata to the power ofthe entire product is congruent toa moduloany prime p involved. TheChinese Remainder Theoremthen shows that the whole product must be a pseudoprime to basea.
For example, a product of several primes from each of the setsbelow is called a Super-Poulet,or superpoulet number (A050217) as all of its composite divisors arePoulet numbers. (Such a set of 7 primes yields 120 Poulet numbers.) The term " super-pseudoprime to base a " has not caught on (yet).
The above includesall examples with at least 7 prime factors of 6 digits or less. Too bad 90289 is not a Poulet number...
(2005-04-18)
A super-pseudoprime to basea is maximal if it does not divide any other.
Let's show that the first (7-factor)super-Poulet number listedabove ismaximal. Since 103 is one of its factors, any additional prime factor would divide:
3 and 7 are easily ruled out, so is 43691(10343691 is not aPoulet number). The other factors arealready 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, thegreatest common divisor of the 7 quantities 2(p-1)-1 (because of a nice propertyproved elsewhere on this site).
23001
=
(2751)(275+1)(275 238+1)(275+ 238+1)
2751
=
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 4new 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-digitnumber are thusPoulet numbers:
By factoring 68 41, 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) A Wieferich prime p is a prime whose square p2 divides 2p-11.
Wieferich primes are precisely the primes whose squares arePoulet 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:
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 iscoprime to the secondfactor 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 showthat theabove result wouldn't hold if the three primeswere 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 p2 q is too. We just checked all prime factors q of 2p-1-1 for both known Wieferich primes (p).
This tableis complete until a third Wieferich prime (p) is found.
p
Primes q for which pq (and/or p2q ) is a Poulet number :
Thereare (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 argumentsuggests 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 primewhen this residue in zero. This is one of p possibilities andwe may thus guess that any prime pends up being a Wieferich prime with probability 1/p. The expected number of Wieferich primes below n would then be fairly close to thesum of the reciprocal of all primes less than n. This is roughly ln(ln(n)), which grows without bound...
Taking this estimate at face value, we expect about0.0645 Wieferich primes with 16 digits,0.0606 Wieferich primes with 17 digits,0.0572 with 18 digits... Thethird Wieferich prime could easily have 41 digits or more,placing it well beyond the reach of anycomputer search,unless abrilliant shortcut is found.
A Brief History of Wieferich Primes :
Wieferich primes are named after the German number theoristArthur Wieferich(1884-1954) who established, in 1909, that any odd prime exponent in a counterexampletoFermat's Last Theorem would have to be such a prime. This was a strong result at the time, although it is now seen asvacuously true: There are no such counterexamples (Fermat's Last Theorem was proved byAndrewWiles 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 ofWalther Meissner (1882-1974) of superconductivity fame.)
The second Wieferich prime (3511) was discovered in 1922 by the Dutch mathematicianN.G.W.H. Beeger (1884-1965)who is also remembered for having coined theterm "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 basesfollowed:
A174422 givesthe 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 howall maximal pseudoprimes to base a which are multiplesof 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:
We may take one of the underlined factors and see whatother 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 isat hand and establish that much by checking that allproducts 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:
