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

proc carmichael {limit {rounds 10}} {
    set carmichaels {}
    for {set p1 2} {$p1 <= $limit} {incr p1} {
	if {![miller_rabin $p1 $rounds]} continue
	for {set h3 2} {$h3 < $p1} {incr h3} {
	    set g [expr {$h3 + $p1}]
	    for {set d 1} {$d < $h3+$p1} {incr d} {
		if {(($h3+$p1)*($p1-1))%$d != 0} continue
		if {(-($p1**2))%$h3 != $d%$h3} continue
 
		set p2 [expr {1 + ($p1-1)*$g/$d}]
		if {![miller_rabin $p2 $rounds]} continue
 
		set p3 [expr {1 + $p1*$p2/$h3}]
		if {![miller_rabin $p3 $rounds]} continue
 
		if {($p2*$p3)%($p1-1) != 1} continue
		lappend carmichaels $p1 $p2 $p3 [expr {$p1*$p2*$p3}]
	    }
	}
    }
    return $carmichaels
}