Problems & Puzzles:
Puzzle 1131 TEST
FOR FERMAT'S PSEUDOPRIMES TO BASE 10
Davide Rotondo sent the following puzzle:
TEST FOR FERMAT'S PSEUDOPRIMES TO BASE 10 USING PASCAL'S TRIANGLE
number n > 4 is Fermat's pseudoprime in base 10 if the number of
digits of the period of the product of the numbers not divisible by n on
the line of n, +1 the whole divided by n, divides n-1. (understood
that along the lines of prime numbers there are no indivisible numbers
and therefore are excluded)
n=6 15, 20, 15 ; (15*20*15 + 1)/6 = 750.16666… does not divide BECAUSE
".16666... " THERE IS THE PRE-PERIOD 1
n=8 28, 70, 28 ; (28*70*28 + 1)/8 = 6860.125 does not divide BECAUSE
".125" IT'S FINITE DECIMAL NUMBER
n=9 84, 84 ; (84*84 + 1)/9 = 784.111111… the period OF ".1111...." is
1 digit long and 1 divides 8 so 9 is A FERMAT PSEUDOPRIME TO BASE 10
n=10 45, 252, 45 ; (45*252*45 + 1)/10 = 510301.1 does not divide BECAUSE
".1" IT'S FINITE DECIMAL NUMBER
Q1: Can you prove this Test or find a counterexample?
During the week 13-19 May, 2023, contributions came from Alessandro Casini,
I attach the pdf-proof of the test.
> In short, is the Test given by Rotondo, true or false?
It is (nearly) true, but it is uselessly complex; it is enough to
at the period of 1/p.
"Nearly" because it is possible that the product + 1 is a multiple
p, and the divisione terminates without digits after the decimal
So in the proposed form the test would not allow to determine
some numbers are pseudoprimes or not.
I do not know whether there are numbers with this property.
> In any case could you rewrite your proof?
Let's fix a base b and take p such that GCD(p, b) = 1 (otherwise p
cannot be a pseudoprime); we need the following facts:
- the base b expansions of all fractions of the form k / p have a
period of the same length;
- if p = a^e1 * b^e2 * c^e3... is composite, the length of the
is the lcm of the lengths of the periods of a^e, b^e2, c^e3...;
- if b^n ≡ 1 mod p, the length of the period of 1 / p divides n,
therefore if p is prime, the length of the period divides p - 1;
- if the length of the period of 1 / p divides n, b^n ≡ 1 mod p.
From the last point it follows that if the length of the period of 1
p divides p - 1, b^(p - 1) ≡ 1 mod p and p is a pseudoprime.
For this to happen a necessary and sufficient condition is that the
lengths of the periods of all prime powers divisors of p divide p -
Now we need another lemma: a and b divide c, lcm(a, b) divides c.
If p = rs (r and s may be composite, but without a common divisor)
the lengths of the periods of 1 / r and 1 / s divide p - 1, the
o the period of 1 / rs, which is their lcm, also divide p - 1.
If p is a pseudoprime, imagine to divide 1 by p; add p - 1 zeros and
compute p - 1 digits: you get a remainder equal to 1 (as p divides
- 1) - 1 and the procedure is equivalent to divide b^(p - 1) by p);
p - 1 zeros again and repeat the process, getting a repetition of
So if p is a pseudoprime, the length of the period of 1 / p divides