Problem Statement

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.

Find Carmichael numbers of the form: where   (Prime1 < Prime2 < Prime3)   for all   Prime1   up to   61. (See page 7 of   Notes by G.J.O Jameson March 2010   for solutions.)

For a given

P r i m

e

1

{\displaystyle Prime_{1}}

Chernick's Carmichael numbers

Let's start with the solution:

func isprim num .
   i = 2
   while i <= sqrt num
      if num mod i = 0
         return 0
      .
      i += 1
   .
   return 1
.
proc carmichael3 p1 . .
   for h3 = 1 to p1 - 1
      for d = 1 to h3 + p1 - 1
         if (h3 + p1) * (p1 - 1) mod d = 0 and -p1 * p1 mod h3 = d mod h3
            p2 = 1 + (p1 - 1) * (h3 + p1) div d
            if isprim p2 = 1
               p3 = 1 + (p1 * p2 div h3)
               if isprim p3 = 1 and (p2 * p3) mod (p1 - 1) = 1
                  print p1 & " " & p2 & " " & p3
               .
            .
         .
      .
   .
.
for p1 = 2 to 61
   if isprim p1 = 1
      carmichael3 p1
   .
.