Number theory › Congruences and modular arithmetic

Chinese remainder theorem

Solve the first problem 12 problems

These are 5 of the 12 problems. Sign in for free to see them all. Sign in

1. Congruences with non-coprime moduli ●○○○○ 10 ptsFind the smallest positive integer $x$ such that $x \equiv 3 \pmod{4}$ and $x \equiv 1 \pmod{6}$.
2. Simultaneous congruences modulo 15 and 21 ●●○○○ 20 ptsFind the smallest positive integer $x$ such that $x \equiv 5 \pmod{15}$ and $x \equiv 8 \pmod{21}$.
3. CRT with non-coprime moduli ●●○○○ 20 ptsFind the smallest positive integer $x$ such that $x\equiv 1 \pmod 8$ and $x\equiv 5 \pmod{12}$.
4. Smallest solution of a linear congruence ●●○○○ 20 ptsWhat is the smallest positive integer $x$ that satisfies the congruence $30x \equiv 42 \pmod{47}$?
5. Solving a four-congruence CRT system ●●●○○ 50 ptsFind the least nonnegative integer $x$ satisfying $x \equiv 4 \pmod{5}$, $x \equiv 2 \pmod{7}$, $x \equiv 2 \pmod{11}$ and $x \equiv 12 \pmod{13}$.

More in Congruences and modular arithmetic

Ciphers and RSAEuler's totientLinear congruencesModular inversesPolynomial congruencesQuadratic residues and primitive rootsResidues of powers and factorials