# Thread: proof with carmichael numbers

1. ## proof with carmichael numbers

Let k be a positive integer such that $6k + 1 = p_1, 12k + 1 = p_2, \mbox { and } 18k + 1 = p_3$ are all prime numbers, and put $m = p_1p_2p_3$
Show that $(p_i - 1) \mid (m - 1) \mbox{ for }i = 1,2,3$
Deduce that if $(a, p_i) = 1$ then $a^{m - 1} \equiv 1 (mod \mbox{ }p_i), i = 1,2,3$.
Conclude that if $(a,m) = 1 \mbox{ then } a^{m-1} \equiv 1 \mbox{ (mod m)}$ that is, that m is a Carmichael number.

I am stumped...

2. Maybe you should have gone to Norin's office hours?

3. That's pretty funny. Now stop stalking each other, guys.

4. $m=1296k^3+396k^2+36k+1$

It's easy to see that $6k\mid m-1$, $12k\mid m-1$, $18k\mid m-1$.

$m-1=k_i(p_i-1)$
$a^{m-1} = (a^{p_i-1})^{k_i} \equiv 1^{k_i} =1 \mod{p_i}$ by Fermat's Little Theorem.

From above we now know $a^{m-1}-1 = n_ip_i$.
Therefore $(a^{m-1}-1)^3 = n_1n_2n_3m \Longrightarrow (a^{m-1}-1)^3 \equiv 0 \mod{m}$.

$m\mid(a^{m-1}-1)^3 \Longrightarrow (a^{m-1}-1)^3 = km = kp_1p_2p_3 = (k')^3p_1^3p_2^3p_3^3$ since we have an integer cubed.

Therefore $m^3 \mid (a^{m-1}-1)^3 \Longrightarrow m\mid (a^{m-1}-1)$.
i.e. $a^{m-1}-1 \equiv 0 \mod{m} \Longrightarrow a^{m-1}\equiv 1 \mod{m}$.