# proof with carmichael numbers

Printable View

• Dec 15th 2009, 02:34 PM
comssa
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...
• Dec 15th 2009, 06:06 PM
iknowwhatyoudidlastsummer
Maybe you should have gone to Norin's office hours?
• Dec 15th 2009, 06:31 PM
Bruno J.
(Rofl)

That's pretty funny. Now stop stalking each other, guys.
• Dec 15th 2009, 08:28 PM
chiph588@
$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}$.