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

(de modulo (X Y)
   (% (+ Y (% X Y)) Y) )
 
(de prime? (N)
   (let D 0
      (or
         (= N 2)
         (and
            (> N 1)
            (bit? 1 N)
            (for (D 3  T  (+ D 2))
               (T (> D (sqrt N)) T)
               (T (=0 (% N D)) NIL) ) ) ) ) )
 
(for P1 61
   (when (prime? P1)
      (for (H3 2 (> P1 H3) (inc H3))
         (let G (+ H3 P1)
            (for (D 1 (> G D) (inc D))
               (when
                  (and
                     (=0
                        (% (* G (dec P1)) D) )
                     (=
                        (modulo (* (- P1) P1) H3)
                        (% D H3)) )
                  (let
                     (P2
                        (inc
                           (/ (* (dec P1) G) D) )
                        P3 (inc (/ (* P1 P2) H3)) )
                     (when
                        (and
                           (prime? P2)
                           (prime? P3)
                           (= 1 (modulo (* P2 P3) (dec P1))) )
                        (print (list P1 P2 P3)) ) ) ) ) ) ) ) )
(prinl)
 
(bye)