Contributions came from Carlos Rivera, Emmanuel Vantieghem & Jan van
It is not difficult to show that, if n is a product of two
relatively prime odd numbers A, B (> 1), then n is a composite
Indeed, let b be a positive integer such that b === 1 (mod
A) and b === -1 (mod B) (the existence of b is ensured by the
Chinese Remainder theorem). Clearly, b is
not 1 or n-1 modulo n. Further, b^2 === 1 (mod AB) and hence
b^(n-1) = (b^2)^((n-1)/2) === 1 (mod n).
Thus, n is Fermat pseudoprime to the base b.
If n = p^a (p > 3, a > 1), then the multiplicative group of the
integers modulo n is cyclic of order (Euler)phi(n) =
(p-1)*(p^(a-1)) and thus, there exist numbers b with the property
b^(p-1) === 1 (mod n) (that not all of these numbers
are 1 or -1 (mod n) is due to the fact that p > 3). It is
clear that for such numbers we also have b^(p^a - 1) === 1 (mod
n). Thus, those b are basis for the pseudoprimality of n.
It is easy to show that no pseudoprime of the form 3^a (a > 1)
To find an even pseudoprime of the form 8k , table at https://oeis.org/A039772 gives n
= 112 as smallest pseudoprime (basis = 65 or 81).
If the basis must be 2, then we can prove the following :
If n is a base 2 pseudoprime of the form y*(x^3), then x is
divisible by a Wieferich
Proof : Let n
= y*(x^3) be a base 2 pseudoprime.
Let p be a prime dividing x. Let r be the multiplicative order
of 2 (mod p^3). This means that r is the smallest positive
number such that 2^r === 1 (mod p^3) and hence that every m with
the property 2^m === 1 (mod p^3) is a multiple of r.
From 2^((p-1)*p^2) === 1 (mod p^3) (Little Fermat), it follows
that r divides (p-1)*p^2.
From 2^(n-1) ===1 (mod n), it follows 2^(n-1) ===1 (mod p^3), and
hence r divides n-1.
That means that r cannot be divisible by p and thus must be a
divisor of p-1.
Thus, 2^(p-1) === 1 (mod p^3) and hence
2^(p-1) === 1 (mod p^2),
which means that p is a Wieferich prime, QED.
So, there is an infinitesimal chance that some puzzler ever will
find an example of such n. The only two known Wieferich primes
are p= 1093 and p = 3511 and in both cases we have 2^(p-1)
!=== 1 (mod p^3).
If p^r|n, p
prime, and n is psp(a) then a^(p-1)=1 mod (p^r). [Necessary
condition, not sufficient!]
If a=2 only a
few solutions are known if r>1, all have r=2, for instance
n=1093^2, 3511^2, 4733.1093^2.
If a>2 there
are an infinite number of solutions if no further restrictions
are imposed on a.
if a=n+1 we always have a solution. If a=n-1 and n is odd we
always have a solution.
So I would
suggest to impose 1<a<n-1, in accordance with Pomerance,
Selfridge and Wagstaff.
If we apply the condition to n=p^r.q^s we search one value of a
for which a^(p-1)=1 mod(p^r) and a^(q-1)=1 mod (q^s).
first has solution a1 then a=a1 mod(p^r) is also a solution.
Similarly a=a2 mod(q^s) for the second equation.
With the Chinese Remainder Theorem we can find the minimal
solutions a mod(n), these might very well be smaller than n-1:
If we have
n=3^3.5 we could use a=+/-1 mod 27 and a=+/-1,2 mod 5, leading
to a equal to either 26 or 109 mod(n).
n=3^r.5 gives solutions r=2 mod 4 and r=3 mod 4 of the form
Here r=2 corresponds to,a=3 mod 5 the second to a=1 mod 5. And
since 3^4=1 mod 5 the others are solutions too.
So more generally: if n=p^r.q and p and q are odd we (at least)
could try a=p^r-1. The corresponding modulus seems to be
determined by the order of p mod q.
a=5^r-1 with r=1 mod 2.
a=3^r-1 with r=2 mod 6
solutions of the form a=7^r-1
a=5^r-1 with r=2 mod 6 or r=4 mod 6
a=7^r-1 with r=1 mod 4 or r=2 mod 4
a=3^r-1 with r=4 mod 4 and 4 is not a divisor of 10! So there is
a mistake in my reasoning.