Problem Statement

A lot of composite numbers can be separated from primes by Fermat's Little Theorem, but there are some that completely confound it. The   Miller Rabin Test   uses a combination of Fermat's Little Theorem and Chinese Division Theorem to overcome this. The purpose of this task is to investigate such numbers using a method based on   Carmichael numbers,   as suggested in   Notes by G.J.O Jameson March 2010.

Find Carmichael numbers of the form: where   (Prime1 < Prime2 < Prime3)   for all   Prime1   up to   61. (See page 7 of   Notes by G.J.O Jameson March 2010   for solutions.)

For a given

P r i m

e

1

{\displaystyle Prime_{1}}

Chernick's Carmichael numbers

Let's start with the solution:

for (2..67).grep: *.is-prime -> \Prime1 {
    for 1 ^..^ Prime1 -> \h3 {
        my \g = h3 + Prime1;
        for 0 ^..^ h3 + Prime1 -> \d {
            if (h3 + Prime1) * (Prime1 - 1) %% d and -Prime1**2 % h3 == d % h3  {
                my \Prime2 = floor 1 + (Prime1 - 1) * g / d;
                next unless Prime2.is-prime;
                my \Prime3 = floor 1 + Prime1 * Prime2 / h3;
                next unless Prime3.is-prime;
                next unless (Prime2 * Prime3) % (Prime1 - 1) == 1;
                say "{Prime1} × {Prime2} × {Prime3} == {Prime1 * Prime2 * Prime3}";
            }
        }
    }
}