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

' version 17-10-2016
' compile with: fbc -s console
 
' using a sieve for finding primes
 
#Define max_sieve 10000000 ' 10^7
ReDim Shared As Byte isprime(max_sieve)
 
' translated the pseudo code to FreeBASIC 
Sub carmichael3(p1 As Integer) 
 
  If isprime(p1) = 0 Then Exit Sub
 
  Dim As Integer h3, d, p2, p3, t1, t2
 
  For h3 = 1 To p1 -1
    t1 = (h3 + p1) * (p1 -1)
    t2 = (-p1 * p1) Mod h3
    If t2 < 0 Then t2 = t2 + h3
    For d = 1 To h3 + p1 -1
      If t1 Mod d = 0 And t2 = (d Mod h3) Then
        p2 = 1 + (t1 \ d)
        If isprime(p2) = 0 Then Continue For
        p3 = 1 + (p1 * p2 \ h3)
        If isprime(p3) = 0 Or ((p2 * p3) Mod (p1 -1)) <> 1 Then Continue For
        Print Using "### * #### * #####"; p1; p2; p3
      End If
    Next d
  Next h3
End Sub
 
 
' ------=< MAIN >=------
 
Dim As UInteger i, j
 
'set up sieve
For i = 3 To max_sieve Step 2
  isprime(i) = 1
Next i
 
isprime(2) = 1
For i = 3 To Sqr(max_sieve) Step 2
  If isprime(i) = 1 Then
    For j = i * i To max_sieve Step i * 2
      isprime(j) = 0
    Next j
  End If
Next i
 
For i = 2 To 61
  carmichael3(i)
Next i
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End