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

 
;; charmichaël numbers up to N-th prime ; 61 is 18-th prime
(define (charms (N 18) local: (h31 0) (Prime2 0) (Prime3 0))
(for* ((Prime1 (primes N))
       (h3 (in-range 1 Prime1))
       (d  (+ h3 Prime1)))
      (set! h31 (+ h3 Prime1))
      #:continue (!zero? (modulo (* h31 (1- Prime1)) d))
      #:continue (!= (modulo d h3) (modulo (- (* Prime1 Prime1)) h3))
      (set! Prime2 (1+ ( * (1- Prime1) (quotient h31 d))))
      #:when (prime? Prime2)
      (set! Prime3 (1+ (quotient (*  Prime1  Prime2)  h3)))
      #:when (prime? Prime3)
      #:when (= 1 (modulo (* Prime2 Prime3) (1- Prime1)))
      (printf " 💥 %12d = %d x %d x %d"  (* Prime1 Prime2 Prime3) Prime1 Prime2 Prime3)))
 