# proof with carmichael numbers

• Dec 15th 2009, 01:34 PM
comssa
proof with carmichael numbers
Let k be a positive integer such that $\displaystyle 6k + 1 = p_1, 12k + 1 = p_2, \mbox { and } 18k + 1 = p_3$ are all prime numbers, and put $\displaystyle m = p_1p_2p_3$
Show that $\displaystyle (p_i - 1) \mid (m - 1) \mbox{ for }i = 1,2,3$
Deduce that if $\displaystyle (a, p_i) = 1$ then $\displaystyle a^{m - 1} \equiv 1 (mod \mbox{ }p_i), i = 1,2,3$.
Conclude that if $\displaystyle (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, 05:06 PM
iknowwhatyoudidlastsummer
Maybe you should have gone to Norin's office hours?
• Dec 15th 2009, 05:31 PM
Bruno J.
(Rofl)

That's pretty funny. Now stop stalking each other, guys.
• Dec 15th 2009, 07:28 PM
chiph588@
$\displaystyle m=1296k^3+396k^2+36k+1$

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

$\displaystyle m-1=k_i(p_i-1)$
$\displaystyle 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 $\displaystyle a^{m-1}-1 = n_ip_i$.
Therefore $\displaystyle (a^{m-1}-1)^3 = n_1n_2n_3m \Longrightarrow (a^{m-1}-1)^3 \equiv 0 \mod{m}$.

$\displaystyle 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 $\displaystyle m^3 \mid (a^{m-1}-1)^3 \Longrightarrow m\mid (a^{m-1}-1)$.
i.e. $\displaystyle a^{m-1}-1 \equiv 0 \mod{m} \Longrightarrow a^{m-1}\equiv 1 \mod{m}$.