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

Carmichael: procedure options (main, reorder);  /* 24 January 2014 */
   declare (Prime1, Prime2, Prime3, h3, d) fixed binary (31);
 
   put ('Carmichael numbers are:');
 
   do Prime1 = 1 to 61;
 
      do h3 = 2 to Prime1;
 
d_loop:  do d = 1 to h3+Prime1-1;
            if (mod((h3+Prime1)*(Prime1-1), d) = 0) &
               (mod(-Prime1*Prime1, h3) = mod(d, h3)) then
               do;
                  Prime2 = (Prime1-1) * (h3+Prime1)/d; Prime2 = Prime2 + 1;
                  if ^is_prime(Prime2) then iterate d_loop;
                  Prime3 = Prime1*Prime2/h3; Prime3 = Prime3 + 1;
                  if ^is_prime(Prime3) then iterate d_loop;
                  if mod(Prime2*Prime3, Prime1-1) ^= 1 then iterate d_loop;
                  put skip edit (trim(Prime1), ' x ', trim(Prime2), ' x ', trim(Prime3)) (A);
               end;
         end;
      end;
   end;
 
   /* Uses is_prime from Rosetta Code PL/I. */
 
end Carmichael;