So, a question in Elementary Number Theory by David M. Burton:
Problems 4.4
2(a) Using congruences, solve the diophantine equation 4x + 51y = 9
Hint: $4x \equiv 9(mod \ 51) $ gives $ x = 15 +51t$, whereas $ \ 51y \equiv 9 (mod \ 4)$ gives $y = 3+4s $. Find the relation between $s$ and $t$
From this hint, I substitute $ x = 15 +51t$ and $y = 3+4s$ in the given equation $4x + 51y = 9$ to get the relation $s = -t-1$ and using which I can get the solutions $ x = 15 + 51t, \ y =-1-4t$
But we know that the solutions of $ax \equiv b (mod \ n)$ is equivatent to the solutions of the diophantine equation $ax -ny = b$,
so, solutions of $4x \equiv 9(mod \ 51) $ is equivalent to solutions of the equation $4x-51y=9$
whereas, solutions of $51y \equiv 9(mod \ 4) $ is equivalent to solutions of the equation $-4x+51y=9$
Now, my question is:
as, the above equations $4x-51y=9$ and $-4x+51y=9$ are different, then what is the point of substituting $ x = 15 +51t$ (solution of $4x-51y=9$) and $y = 3+4s $ (solution of $-4x+51y=9$) in the given equation $4x+51y=9$ to find a relation between $t$ and $s$ ? Isn't it absurd as $ x = 15 +51t$ and $y = 3+4s $ are solutions of two different equations? Can anyone please explain this?
PS: I did it like this $4x \equiv 9(mod \ 51) $ gives $ x = 15 +51t$ and by substituting it in $4x+51y=9$ we get $y=-1-4t$
Best Answer
Here's the argument outlined in equational logic (vs. less precise English language). No use is made of $\,4x-51y = 9.\,$ The elimination steps use $E_z\!:\,z = c,\, az = b\iff z=c,\, ac = b,\,$ familiar as an elementary row operation in Gaussian elimination (triangularization) in linear algebra.
$$\begin{align} 4x+51y\, =\, 9\, \ \ \ \ \ \ \ \ \ \ \ \ \ & \\[.2em] \iff\ 4x+51y\, =\, 9\, \ \ \ \ \ \ \ \ \&\ \ &x = 15+51t\ \ \&\ \ y = 3+4s\\[.2em] \iff 204(t+s) = -204\ \ \&\ \ &x = 15+51t\ \ \&\ \ y = 3+4s,\ \ \ \ {\rm by}\ \ E_x,\,E_y\\[.2em] \iff\ \ \ \ \ \ \ \ \ t+s = -1\ \ \ \ \ \ \&\ \ &x = 15+51t\ \ \&\ \ y = 3+4s,\ \ \ \ {\rm by\ cancel}\ 204\\[.2em] \iff \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \phantom{t+s = -1\ \&}\ &x = 15+51t\ \ \&\ \ y = -1-4t,\ \ {\rm by}\ \ E_s \ \end{align}$$
What you did - solve one congruence first, then substitute - is generally simpler and the more common way to proceed, i.e. in equational language as above
$$\begin{align} 4x+51y\, =\, 9\, \ \ \ \ \ \ \ \ \ \ \ & \\[.2em] \iff\ 4x+51y\, =\, 9\, \ \ \ \ \ \ \&\ \ &x = 15+51t\\[.2em] \iff 51y = -51\!-\!204t\ \ \&\ \ &x = 15+51t,\ \ \ {\rm by}\ \ E_x\\[.2em] \iff\ \ \ \ \:\! y = -1-4t\ \ \ \ \ \ \&\ \ &x = 15+51t,\ \ \ {\rm by\ cancel}\ 51 \end{align}\qquad$$
Remark $ $ If instead of the above (bidirectional) equivalences we use only unidirectional arrows $(\Rightarrow)$ then we obtain only necessary conditions on the solutions. Then to verify sufficiency we have to check that the candidate solutions actually work (are not extraneous roots). See here for more on the insufficiency of unidirectional inferences.