Saturday, 22 November 2025

Exercise (3.3).20

Use an equivalent congruence to find the general solution of the following Diophantine equations:

(a) $6x + 7y= 100$

(b) $1998x + 100y= 5192$


(a) The equivalent congruence is

$$ 6x \equiv 100 \pmod 7 $$

Here $g = \gcd(7,6)=1$ and so there is a unique solution.

$$ \begin{align} 6x & \equiv 100 \pmod 7 \\ \\  -x &  \equiv 2 \pmod 7 \\ \\ x & \equiv 5 /pmod 7 \end{align}$$

So $x=5 + 7t$ for some integer $t$. 

Substituting into $6x + 7y = 100$ gives us $y=10-6t$. So the general solution is

$$ x = 5 + 7t, \quad y = 10-6t $$

for some integer $t$.


(b) The equivalent congruence is 

$$ 1998x \equiv 5192 \pmod {100} $$

Here $g = \gcd(100, 1998) = 2$, and $g\mid 5192$ and so there are two incongruent solutions.

$$ \begin{align} 1998x & \equiv 5192 \pmod {100} \\ \\ -2x & \equiv -8 \pmod {100} \\ \\ 2x & \equiv 8 \pmod {100}  \\ \\ x & \equiv 4 \pmod {50} \end{align}$$

So $x= 4 + 50t$ for some integer $t$. 

Substitution into $1998x + 100y= 5192$ gives us $y = -28 -999t$.

So the general solution is

$$ x = 4 + 50t , \quad y=-28 -999t $$

for some integer $t$.


Note: The two solutions are $x \equiv 4 \pmod {100}$ and $x \equiv 54 \pmod {100}$, but in modulo 50, we reduce the number of solutions to one.