Converse of Fermat's Little Theorem (particular case)

• April 30th 2009, 09:16 AM
Amanda1990
Converse of Fermat's Little Theorem (particular case)
Let $n = (6t+1)(12t+1)(18t+1)$ with $t \in \{1,2,3...\}$ such that $(6t+1),(12t+1)$ and $(18t+1)$ are all prime numbers.

Show that $a^{n-1} = 1$ (mod n) whenever hcf (a,n) = 1.
• April 30th 2009, 12:02 PM
Media_Man
Carmichael Numbers
Carmichael Number -- from Wolfram MathWorld

Let $n=p_1p_2p_3$ be of the following form:

$(6t+1)(12t+1)(18t+1)=1296t^3+396t^2+36t+1=36(36t^3 +11t^2+t)+1$

If each factor is prime, then $p-1|n-1$ for all $p|n$. By Korselt's criteria, this property makes n a Carmichael Number, which by definition, is any composite number that passes Fermat's test.