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

package main
 
import "fmt"
 
// Use this rather than % for negative integers
func mod(n, m int) int {
    return ((n % m) + m) % m
}
 
func isPrime(n int) bool {
    if n < 2 { return false }
    if n % 2 == 0 { return n == 2 }
    if n % 3 == 0 { return n == 3 }
    d := 5
    for d * d <= n {
        if n % d == 0 { return false }
        d += 2
        if n % d == 0 { return false }
        d += 4
    }
    return true
}
 
func carmichael(p1 int) {
    for h3 := 2; h3 < p1; h3++ {
        for d := 1; d < h3 + p1; d++ {
            if (h3 + p1) * (p1 - 1) % d == 0 && mod(-p1 * p1, h3) == d % h3 {
                p2 := 1 + (p1 - 1) * (h3 + p1) / d
                if !isPrime(p2) { continue }
                p3 := 1 + p1 * p2 / h3
                if !isPrime(p3) { continue }
                if p2 * p3 % (p1 - 1) != 1 { continue }
                c := p1 * p2 * p3
                fmt.Printf("%2d   %4d   %5d     %d\n", p1, p2, p3, c)
            }
        }
    }
}
 
func main() {
    fmt.Println("The following are Carmichael munbers for p1 <= 61:\n")
    fmt.Println("p1     p2      p3     product")
    fmt.Println("==     ==      ==     =======")
 
    for p1 := 2; p1 <= 61; p1++ {
        if isPrime(p1) { carmichael(p1) }
    }
}