Maths WorkshopMaths problems with full solutions
Exercise 1483Number theory › CongruencesL1Added 2 Nov 2026

A Chinese remainder system

#Chinese remainder theorem#congruences#Bézout

Statement

Solve the system
{x≡2(mod17)x≡3(mod33)\begin{cases}x\equiv2\pmod{17}\\x\equiv3\pmod{33}\end{cases}

Hint

Write x=2+17h=3+33kx=2+17h=3+33k and solve 17h−33k=117h-33k=1.

Show solutionHide solution

Solution

Reformulation. We need 17h−33k=117h-33k=1 for some integers h,kh,k.

Bézout. \divisibility(17,33)=1\divisibility(17,33)=1, and 2⋅17−33=12\cdot17-33=1. So h=2h=2, k=1k=1 works.

Particular solution.
x0=2+17⋅2=36.x_0=2+17\cdot2=36.

General solution. By the Chinese remainder theorem,
x≡36(mod17⋅33=561).x\equiv36\pmod{17\cdot33=561}.
So x=36+561mx=36+561m, m∈Zm\in\mathbb{Z}.