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.



Task

Find Carmichael numbers of the form:

  Prime1 × Prime2 × Prime3 
where    (Prime1 < Prime2 < Prime3)    for all    Prime1    up to   61.

(See page 7 of   Notes by G.J.O Jameson March 2010   for solutions.)



Pseudocode

For a given   



P
r
i
m

e

1




{\displaystyle Prime_{1}}



for 1 < h3 < Prime1
    for 0 < d < h3+Prime1
         if (h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3
         then
               Prime2 = 1 + ((Prime1-1) * (h3+Prime1)/d)
               next d if Prime2 is not prime
               Prime3 = 1 + (Prime1*Prime2/h3)
               next d if Prime3 is not prime
               next d if (Prime2*Prime3) mod (Prime1-1) not equal 1
               Prime1 * Prime2 * Prime3 is a Carmichael Number



related task
Chernick's Carmichael numbers

with javascript_semantics
integer count = 0
for p1=1 to 61 do
    if is_prime(p1) then
        for h3=1 to p1 do
            atom h3p1 = h3 + p1
            for d=1 to h3p1-1 do
                if mod(h3p1*(p1-1),d)=0
                and mod(-(p1*p1),h3) = mod(d,h3) then
                    atom p2 := 1 + floor(((p1-1)*h3p1)/d),
                         p3 := 1 +floor(p1*p2/h3)
                    if is_prime(p2) 
                    and is_prime(p3)
                    and mod(p2*p3,p1-1)=1 then
                        if count<5 or count>65 then
                            printf(1,"%d * %d * %d = %d\n",{p1,p2,p3,p1*p2*p3})
                        elsif count=35 then puts(1,"...\n") end if
                        count += 1
                    end if
                end if
            end for
        end for
    end if
end for
printf(1,"%d Carmichael numbers found\n",count)
