Solution

Find all solutions in integers to the following. $$153x + 28y = 1$$


First, we observe by inspection that the greatest common divisor (gcd) of 153 and 28 is 1. We will need to go through the calculuations required by Euclid's Algorithm to demonstrate this, however, as these calculations are the key to expressing the gcd as a linear combination of the numbers in question: $$\begin{align} 153 &= 5 \cdot 28 + 13\\ 28 &= 2 \cdot 13 + 2\\ 13 &= 6 \cdot 2 + \fbox{1} \leftarrow \textrm{gcd}\\ 2 &= 2 \cdot 1 + 0 \end{align}$$ Now, we write $1$ as linear combinations of the various pairs of numbers seen above, working our way backwards through Euclid's Algorithm, until we get $1$ as a linear combination of $153$ and $28$ $$\begin{align} 1 &= 13 - 6 \cdot 2\\ &= 13 - 6(28 - 2 \cdot 13)\\ &= 13 \cdot 13 - 6 \cdot 28\\ &= 13 (153 - 5 \cdot 28) - 6 \cdot 28\\ &= 13 \cdot 153 - 71 \cdot 28 \end{align}$$ The last line gives us the solution we seek:

$$x=13 \quad , \quad y=-71$$

Now that we have one solution, and given that the $\textrm{gcd}(153,28)=1$, the rest of the solutions can be characterized by:

$$x = 13 + 28k \quad , \quad y=-71 - 153k$$

where $k$ is an integer.