A lot of composite numbers can be separated from primes by Fermat's Little Theorem, but there are some that completely confound it.

The &nbsp; [[Miller-Rabin primality test|Miller Rabin Test]] &nbsp; 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 &nbsp; [[wp:Carmichael number|Carmichael numbers]], &nbsp; as suggested in &nbsp; [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010].


;Task:
Find Carmichael numbers of the form:
:::: <big> <i>Prime</i><sub>1</sub> &times; <i>Prime</i><sub>2</sub> &times; <i>Prime</i><sub>3</sub> </big>

where &nbsp; <big> (<i>Prime</i><sub>1</sub>   <   <i>Prime</i><sub>2</sub>   <   <i>Prime</i><sub>3</sub>) </big> &nbsp; for all &nbsp;   <big> <i>Prime</i><sub>1</sub> </big>   &nbsp;  up to &nbsp; '''61'''.
<br>(See page 7 of &nbsp; [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010] &nbsp; for solutions.)


;Pseudocode:
For a given &nbsp; <math>Prime_1</math>

 <tt>for 1 < h3 < Prime<sub>1</sub></tt>
     <tt>for 0 < d < h3+Prime<sub>1</sub></tt>
          <tt>if (h3+Prime<sub>1</sub>)*(Prime<sub>1</sub>-1) mod d == 0 and -Prime<sub>1</sub> squared mod h3 == d mod h3</tt>
          <tt>then</tt>
                <tt>Prime<sub>2</sub> = 1 + ((Prime<sub>1</sub>-1) * (h3+Prime<sub>1</sub>)/d)</tt>
                <tt>next d if Prime<sub>2</sub> is not prime</tt>
                <tt>Prime<sub>3</sub> = 1 + (Prime<sub>1</sub>*Prime<sub>2</sub>/h3)</tt>
                <tt>next d if Prime<sub>3</sub> is not prime</tt>
                <tt>next d if (Prime<sub>2</sub>*Prime<sub>3</sub>) mod (Prime<sub>1</sub>-1) not equal 1</tt>
                <tt>Prime<sub>1</sub> * Prime<sub>2</sub> * Prime<sub>3</sub> is a Carmichael Number</tt>
<br><br>
;related task
[[Chernick's Carmichael numbers]]
<br><br>
