OlympiadHardNumber Theory7–9

Chinese Remainder Theorem

Teorema Chinês do Resto

Find the smallest positive integer $n$ such that $n \equiv 2 \pmod{3}$ , $n \equiv 3 \pmod{5}$ , and $n \equiv 2 \pmod{7}$ .

Use the Chinese Remainder Theorem or systematic search.

Solution

Step 1 of 13

1.The moduli $3, 5, 7$ are pairwise coprime, so by the Chinese Remainder Theorem a solution exists and is unique modulo $3 \times 5 \times 7 = 105$ .