Problems & Puzzles: 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 A 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)   Examples:         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, Mauro Fiorentini

***

Alessandro wrote:

I attach the pdf-proof of the test.

***

Mauro wrote:

> In short, is the Test given by Rotondo, true or false?
>

It is (nearly) true, but it is uselessly complex; it is enough to look
at the period of 1/p.
"Nearly" because it is possible that the product + 1 is a multiple of
p, and the divisione terminates without digits after the decimal point.
So in the proposed form the test would not allow to determine whether
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 period
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.

Note:
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 - 1.
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) and
the lengths of the periods of 1 / r and 1 / s divide p - 1, the length
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 b^(p
- 1) - 1 and the procedure is equivalent to divide b^(p - 1) by p); add
p - 1 zeros again and repeat the process, getting a repetition of the
same digit.
So if p is a pseudoprime, the length of the period of 1 / p divides p -
1.

***