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

 
# Project : Carmichael 3 strong pseudoprimes
 
see "The following are Carmichael munbers for p1 <= 61:" + nl
see "p1     p2      p3     product" + nl
 
for p = 2 to 61
    carmichael3(p)
next
 
func carmichael3(p1) 
       if isprime(p1) = 0  return ok
       for h3 = 1 to p1 -1
            t1 = (h3 + p1) * (p1 -1)
            t2 = (-p1 * p1) % h3
            if t2 < 0
               t2 = t2 + h3
            ok
            for d = 1 to h3 + p1 -1
                 if t1 % d = 0 and t2 = (d % h3) 
                   p2 = 1 + (t1 / d)
                   if isprime(p2) = 0
                      loop
                   ok
                   p3 = 1 + floor((p1 * p2 / h3))
                   if isprime(p3) = 0 or ((p2 * p3) % (p1 -1)) != 1 
                      loop
                   ok
                   see "" + p1 + "       " + p2 + "      " + p3 + "    " + p1*p2*p3 + nl
                ok
            next 
     next 
 
func isprime(num)
       if (num <= 1) return 0 ok
       if (num % 2 = 0) and num != 2
          return 0
       ok
       for i = 3 to floor(num / 2) -1 step 2
           if (num % i = 0) 
              return 0
           ok
       next
       return 1
 