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:

link "factors"

procedure main(A)
    n := integer(!A) | 61
    every write(carmichael3(!n))
end

procedure carmichael3(p1)
    every (isprime(p1), (h := 1+!(p1-1)), (d := !(h+p1-1))) do
        if (mod(((h+p1)*(p1-1)),d) = 0, mod((-p1*p1),h) = mod(d,h)) then {
            p2 := 1 + (p1-1)*(h+p1)/d
            p3 := 1 + p1*p2/h
            if (isprime(p2), isprime(p3), mod((p2*p3),(p1-1)) = 1) then
                suspend format(p1,p2,p3)
            }
end

procedure mod(n,d)
   return (d+n%d)%d
end

procedure format(p1,p2,p3)
    return left(p1||" * "||p2||" * "||p3,20)||" = "||(p1*p2*p3)
end