TAOCP 4.5.2 Exercise 19
For part (a), consider the system 3x + 7y + 11z = 1, \quad 5x - 7y - 3z = 3.
Section 4.5.2: The Greatest Common Divisor
Exercise 19. [**] [21] Use the text's method to find a general solution in integers to the following sets of equations:
a) $3x + 7y + 11z = 1$ b) $3x + 7y + 11z = 1$ $5x - 7y - 3z = 3$ $5x + 7y - 3z = -3$
Verified: yes
Solve time: 1m11s
For part (a), consider the system
$$ 3x + 7y + 11z = 1, \quad 5x - 7y - 3z = 3. $$
Adding the two equations eliminates $y$:
$$ (3x + 5x) + (7y - 7y) + (11z - 3z) = 1 + 3 \implies 8x + 8z = 4 \implies x + z = \frac{1}{2}. $$
Since $x$ and $z$ must be integers, set $z = t$, $x = \frac{1}{2} - t$, which is impossible. Therefore, there is no integer solution for part (a).
For part (b), the system is
$$ 3x + 7y + 11z = 1, \quad 5x + 7y - 3z = -3. $$
Subtract the first equation from the second:
$$ (5x - 3x) + (7y - 7y) + (-3z - 11z) = -3 - 1 \implies 2x - 14z = -4 \implies x - 7z = -2 \implies x = 7z - 2. $$
Substitute $x = 7z - 2$ into the first equation:
$$ 3(7z - 2) + 7y + 11z = 1 \implies 21z - 6 + 7y + 11z = 1 \implies 32z + 7y = 7 \implies 7y = 7 - 32z \implies y = 1 - \frac{32}{7} z. $$
For $y$ to be an integer, $z$ must be a multiple of $7$: set $z = 7t$, then
$$ x = 7(7t) - 2 = 49t - 2, \quad y = 1 - \frac{32}{7} \cdot 7t = 1 - 32t, \quad z = 7t, \quad t \in \mathbb{Z}. $$
Hence the general integer solution is
\boxed{(x, y, z) = (49t - 2, 1 - 32t, 7t), \ t \in \mathbb{Z}}. ] This completes the proof. ∎