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

F mod_(n, m)
   R ((n % m) + m) % m
 
F is_prime(n)
   I n C (2, 3)
      R 1B
   E I n < 2 | n % 2 == 0 | n % 3 == 0
      R 0B
   V div = 5
   V inc = 2
   L div ^ 2 <= n
      I n % div == 0
         R 0B
      div += inc
      inc = 6 - inc
   R 1B
 
L(p) 2 .< 62
   I !is_prime(p)
      L.continue
   L(h3) 2 .< p
      V g = h3 + p
      L(d) 1 .< g
         I (g * (p - 1)) % d != 0 | mod_(-p * p, h3) != d % h3
            L.continue;
         V q = 1 + (p - 1) * g I/ d;
         I !is_prime(q)
            L.continue
         V r = 1 + (p * q I/ h3)
         I !is_prime(r) | (q * r) % (p - 1) != 1
            L.continue
         print(p‘ x ’q‘ x ’r)