Let $\displaystyle n = (6t+1)(12t+1)(18t+1)$ with $\displaystyle t \in \{1,2,3...\}$ such that $\displaystyle (6t+1),(12t+1)$ and $\displaystyle (18t+1)$ are all prime numbers.

Show that $\displaystyle a^{n-1} = 1$ (mod n) whenever hcf (a,n) = 1.

Printable View

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

Show that $\displaystyle a^{n-1} = 1$ (mod n) whenever hcf (a,n) = 1. - Apr 30th 2009, 12:02 PMMedia_ManCarmichael Numbers
Carmichael Number -- from Wolfram MathWorld

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

$\displaystyle (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 $\displaystyle p-1|n-1$ for all $\displaystyle 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.