Exercise 750Number theory › CongruencesL1Added 2 Nov 2026

An incompatible congruence system

#Chinese remainder#compatibility condition

Statement

Show that the system
$\begin{cases}x\equiv5\pmod{35}\\x\equiv8\pmod{133}\end{cases}$
has no solution.

Hint

The system is compatible iff $\divisibility(35,133)\mid(8-5)$ .

Show solutionHide solution

divisibility.
$133=3\cdot35+28,\quad 35=1\cdot28+7,\quad 28=4\cdot7.$
So $\divisibility(35,133)=7$ .

Compatibility. For solutions to exist, we need $7\mid(8-5)=3$ . This is false, so there is no solution.