# Solution

Find all solutions in integers to the following. $$105x + 121y = 1$$

First, we observe by inspection that the greatest common divisor (gcd) of 105 and 121 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} 121 &= 1 \cdot 105 + 16\\ 105 &= 6 \cdot 16 + 9\\ 16 &= 1 \cdot 9 + 7\\ 9 &= 1 \cdot 7 + 2\\ 7 &= 3 \cdot 2 + \fbox{1} \leftarrow \textrm{gcd}\\ 2 &= 2 \cdot 1 + 0 \end{align} Now, we write the remainders seen as linear combinations of 105 and 121, working our way forwards through Euclid's Algorithm, until we get the linear combination representing the gcd. \begin{align} 16 &= 121 - 105\\ 9 &= 105 - 6 \cdot 16\\ &= 105 - 6 \cdot (121 - 105)\\ &= 7 \cdot 105 - 6 \cdot 121\\ 7 &= 16 - 9\\ &= (121 - 105) - (7 \cdot 105 - 6 \cdot 121)\\ &= 7 \cdot 121 - 8 \cdot 105\\ 2 &= 9 - 7\\ &= (7 \cdot 105 - 6 \cdot 121) - (7 \cdot 121 - 8 \cdot 105)\\ &= 15 \cdot 105 - 13 \cdot 121\\ 1 &= 7 - 3 \cdot 2\\ &= (7 \cdot 121 - 8 \cdot 105) - 3 \cdot (15 \cdot 105 - 13 \cdot 121)\\ &= 46 \cdot 121 - 53 \cdot 105\\ \end{align} The last line gives us the solution we seek:

$$x=-53 \quad , \quad y=46$$

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

$$x = -53 + 121k \quad , \quad y=46 - 105k$$

where $k$ is an integer.