Maths WorkshopMaths problems with full solutions
Exercise 2108Number theory › CongruencesOlympiadAdded 3 Nov 2026

A Carmichael number check

#Carmichael#Fermat#pseudoprime

Statement

Show that 1105=5⋅13⋅171105=5\cdot13\cdot17 is a Carmichael number.

Hint

Check a1104≡1(mod1105)a^{1104}\equiv1\pmod{1105} for all aa coprime to 11051105, using CRT.

Show solutionHide solution

Solution

Check primes. For aa coprime to 11051105:
- mod 55: a4≡1a^4\equiv1, 1104=276⋅41104=276\cdot4, so a1104≡1(mod5)a^{1104}\equiv1\pmod5.
- mod 1313: a12≡1a^{12}\equiv1, 1104=92⋅121104=92\cdot12, so a1104≡1(mod13)a^{1104}\equiv1\pmod{13}.
- mod 1717: a16≡1a^{16}\equiv1, 1104=69⋅161104=69\cdot16, so a1104≡1(mod17)a^{1104}\equiv1\pmod{17}.

CRT. Since 5,13,175,13,17 are coprime, a1104≡1(mod1105)a^{1104}\equiv1\pmod{1105}.

Conclusion. 11051105 is a Carmichael number (like 561561).