1
$\begingroup$

I'm currently working on this problem:


Use the definition of congruence and Fermat's Little Theorem to show that if gcd$(b,561) = 1$, then $$b^{560} \equiv \begin{equation} \begin{cases} 1 &\text{ mod } 3,\\ 1 &\text{ mod } 11,\\ 1 &\text{ mod } 17.\\ \end{cases} \end{equation}$$

Conclude that, if gcd$(b,561)=1$, then $b^{560}\equiv1\text{ mod }561$ and so $561$ is a Carmichael number. Hint: What does it mean that $b^{561}\equiv 1\text{ mod }561?$


So I'm guessing that it's significant that 3,11, and 17 all divide 561. Fermat's little theorem doesn't, by itself, provide for something like $b^{p-1} \equiv 1\text{ mod }q$ where q and p are different, so I'm guessing this is where I need to use congruence to prove that 561 is congruent to 3, 11, and 17?

$\endgroup$
  • 2
    $\begingroup$ Yes, 561= 3(11)(17). It follows from that that if gcd(b, 561)= 1 then gcd(b, 3)= 1, gcd(b, 11)= 1, and gcd(b, 17)= 1. $\endgroup$ – user247327 Sep 15 '16 at 20:01
  • $\begingroup$ Hint, because $561=3\cdot 11 \cdot 17$, where $3,11,17$ all are primes, you will have things like $$b^2 \equiv 1 \pmod{3} \rightarrow (b^2)^{280} \equiv 1^{280} \pmod{3}$$ $$b^{10} \equiv 1 \pmod{11} \rightarrow (b^{10})^{56} \equiv 1^{56} \pmod{11}$$ $$b^{16} \equiv 1 \pmod{17} \rightarrow (b^{16})^{35} \equiv 1^{35} \pmod{17}$$ or $$b^{560} \equiv 1 \pmod{3}$$ $$b^{560} \equiv 1 \pmod{11}$$ $$b^{560} \equiv 1 \pmod{17}$$ $\endgroup$ – rtybase Sep 15 '16 at 20:56
1
$\begingroup$

Because $561=3\cdot 11 \cdot 17$, where $3,11,17$ all are primes, you will have things like $$b^2 \equiv 1 \pmod{3} \rightarrow (b^2)^{280} \equiv 1^{280} \pmod{3}$$ $$b^{10} \equiv 1 \pmod{11} \rightarrow (b^{10})^{56} \equiv 1^{56} \pmod{11}$$ $$b^{16} \equiv 1 \pmod{17} \rightarrow (b^{16})^{35} \equiv 1^{35} \pmod{17}$$ or $$b^{560} \equiv 1 \pmod{3}$$ $$b^{560} \equiv 1 \pmod{11}$$ $$b^{560} \equiv 1 \pmod{17}$$ or $$b^{560} - 1 =3q_1$$ $$b^{560} - 1 =11q_2$$ $$b^{560} - 1 =17q_3$$ and applying Euclid's lemma two times for $3q_1=11q_2=17q_3$ $$b^{560} - 1 =561q$$ or $$b^{560} \equiv 1 \pmod{561}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.