Past exam of the mathematics course of the University of Cambridge / 2004 / ia / Paper 4 / 1E (Numbers and Sets)

The Euclidean algorithm givesBack substitution produces the Bézout's identityHence a positive integer solution is $\boxed{m=19,n=15}$. More generally, subtracting this identity from any other solution shows $79(m-19)=100(n-15)$. Since $79$ and $100$ are coprime, the integer solutions are $m=19+100k$, $n=15+79k$; both are positive precisely when $k\ge 0$.

Divide the linear congruence by the common factor $3$, also dividing its modulus:The Bézout's identity from part (a) makes $19$ the inverse of $79$ modulo $100$. Multiplication by $19$ therefore gives $x\equiv 133\equiv 33(\mathrm{mod}100)$. Thus all integer solutions are $\boxed{x=33+100k,k\in \mathbb{Z}}$. Equivalently, the three solution classes modulo $300$ are $33,133,233$; using modulus $300$ must not discard two of these classes.

Write $x=11+100t$. Reduction of the other integer congruence modulo $79$ gives $21t\equiv -3(\mathrm{mod}79)$. The Bézout's identity $19\cdot 79-15\cdot 100=1$ gives $-15\cdot 21\equiv 1(\mathrm{mod}79)$, so $t\equiv 45(\mathrm{mod}79)$. Consequently,Indeed, $4511=8+79\cdot 57=11+100\cdot 45$. The Chinese remainder theorem guarantees one class modulo $79\cdot 100$, since the two moduli are coprime.