# Thread: proof with carmichael numbers

1. ## 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...

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

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

4. $\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}$.