## Exercises - Linear Combinations

1. Find all solutions in integers to the following. (Hint: First find one solution in integers by successively writing each remainder seen in Euclid's Algorithm as an appropriate linear combination. Then, consider how you can alter together the values of $x$ and $y$, without adding anything to the left side of each equation.)

1. $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.

2. $12345x + 67890y = \textrm{gcd}(12345,67890)$
First, we must compute the greatest common divisor (gcd) of 12345 and 67890. We can use Euclid's Algorithm to do this: \begin{align} 67890 &= 5 \cdot 12345 + 6165\\ 12345 &= 2 \cdot 6165 + \fbox{15} \leftarrow \textrm{gcd}\\ 6165 &= 411 \cdot 15 + 0 \end{align} Now, we write the gcd as various linear combinations, working our way backwards through Euclid's Algorithm, until we get the linear combination desired: \begin{align} 15 &= 1 \cdot 12345 - 2 \cdot 6165\\ 15 &= 1 \cdot 12345 - 2 \cdot (67890 - 5 \cdot 12345)\\ 15 &= 11 \cdot 12345 - 2 \cdot 67890\\ \end{align}

The last line gives us the solution we seek: $x=11, y=-2$.

Now that we have one solution, and given that the $\textrm{gcd}(12345,67890)=15$, the rest of the solutions can be characterized by the following, where $k$ is an integer:

$$x = 11 + \dfrac{67890}{15} k \quad, \quad y=-2 - \dfrac{12345}{15} k$$

Written more briefly, we have:

$$x = 11 + 4526k \quad , \quad y=-2-823k \quad \textrm{ with } k \in \mathbb{Z}$$
3. $54321x + 9876y = \textrm{gcd}(54321,9876)$
First, we must compute the greatest common divisor (gcd) of 54321 and 9876. We can use Euclid's Algorithm to do this: \begin{align*} 54321 &= 5 \cdot 9876 + 4941\\ 9876 &= 1 \cdot 4941 + 4935\\ 4941 &= 1 \cdot 4935 + 6\\ 4935 &= 822 \cdot 6 + \fbox{3} \leftarrow \textrm{gcd}\\ 6 &= 2 \cdot 3 + 0 \end{align*} Now, we write the gcd as various linear combinations, working our way backwards through Euclid's Algorithm, until we get the linear combination desired: \begin{align*} 3 &= 1 \cdot 4935 - 822 \cdot 6\\ 3 &= 1 \cdot 4935 - 822 \cdot (4941 - 1 \cdot 4935)\\ 3 &= 823 \cdot 4935 - 822 \cdot 4941\\ 3 &= 823 \cdot (9876 - 1 \cdot 4941) - 822 \cdot 4941\\ 3 &= 823 \cdot 9876 - 1645 \cdot 4941\\ 3 &= 823 \cdot 9876 - 1645 \cdot (54321 - 5 \cdot 9876)\\ 3 &= 9048 \cdot 9876 - 1645 \cdot 54321\\ \end{align*}

The last line gives us the solution we seek: $x=-1645$, $y=9048$.

Now that we have one solution, and given that the $\textrm{gcd}(54321,9876)=3$, the rest of the solutions can be characterized by the following where $k$ is an integer:

$$x = -1645 + \dfrac{9876}{3} k \quad , \quad y=9048 - \dfrac{54321}{3} k$$

Written more briefly, we have:

$$x = -1645 + 3292k \quad , \quad y=9048-18107k \quad \textrm{ with } k \in \mathbb{Z}$$

2. What follows is a modified version of the Euclidean Algorithm:

1. Set $x=1$, $g=a$, $v=0$, $w=b$, $s=0$, and $t=0$.
2. If $w=0$, let $y=(g-ax)/b$ and stop.
3. Find $q$ and $t$ so that $g = qw + t$, with $0 \le t \lt w$.
4. Set $s=x-qv$
5. Set $(x,g) = (v,w)$
6. Set $(v,w) = (s,t)$
7. Go to step ii.

Use this algorithm to determine the greatest common divisor, $g$, of $a$ and $b$, as well as the solutions to $ax+by=g$ for the following values of $a$ and $b$:

1. $a=19789$, $b=23548$

The values of the variables after each pass through the algorithm is given in the table below:

$x$$g$$v$$w$$s$$t$$q$
119789023548000
0235481197891197890
119789-13759-137591
-13759699469945
6994-19777-197773
-1977725217252171
25217-94126-941263
-9412611991119911
11991-21335-213351
-2133554521545212
54521-75814-758141
-7581413037130371
13037-33640-336402

Appealing to the final pass above, and solving for $y$ in the original equation ($19789x+23548y=7$) then yields:

$$g=7 \quad , \quad x=1303 \quad , \textrm{ and } y=-1095$$

2. $a=31875$, $b=8387$

The values of the variables after each pass through the algorithm is given in the table below:

$x$$g$$v$$w$$s$$t$$q$
13187508387000
0838716714167143
16714-11673-116731
-116735225224
522-3811-381176
-3811838708387022

Appealing to the final pass above, and solving for $y$ in the original equation ($31875x+8387y=1$) then yields:

$$g=1 \quad , \quad x=-381 \quad , \textrm{ and } y=1448$$

3. $a=22241739$, $b=19848039$

The values of the variables after each pass through the algorithm is given in the table below:

$x$$g$$v$$w$$s$$t$$q$
122241739019848039000
01984803912393700123937001
12393700-8698439-86984398
-869843925298383252983833
25298383-58101673-581016732
-5810167314195037141950372
14195037-1996636-19966361
-1996636292721332927213314
29272133-8980237-89802373
-89302378374708374709

Appealing to the final pass above, and solving for $y$ in the original equation $$22241739x+19848039y=237$$ then yields:

$$g=237 \quad , \quad x=-8980 \quad , \textrm{ and } y=10063$$

3. The following questions concern linear combinations of three values:

1. Find a solution in integers to $6x + 15y + 20z = 1$.
2. Under what conditions are their integers $x,y,$ and $z$ where $ax + by + cz = 1$? Describe a method to find such a solution, when it exists.
3. Use your method from (b) to find a solution in integers to $15x+341y+385z=1$

1. Note that $6x + 15y$ must always be a multiple of $\gcd (6,15) = 3$. As such, we first solve $3k+20z=1$. By inspection, $3 \cdot 7 + 20 \cdot (-1) = 1$. So we can characterize all solutions by $k=7+20n$ and $z=-1-3n$.

Now solving $6x+15y=3$, we find $x = 3 + 5m$ and $y = -1 - 2m$.

This means that for $6x+15y=3w$, we have $x=3w + 5mw$ and $y=-w -2mw$ as solutions.

By our first calculation, we need $w=7 + 20n$. Substituting this into our forms for $x$ and $y$, we find:

\begin{align} x&=21 + 60n + 35m + 100mn\\ y&=-7 - 20n -14m - 40mn\\ z&=-1-3n \end{align}
2. We need $\gcd(a,b,c)=1$ in order to have a solution. As suggested in part (a), to find a solution, we can first find a solution to $ax+by=\gcd(a,b)$; then find a solution to $\gcd(a,b)\cdot k + cz = 1$; and finally, multiply the first solutions for $x$ and $y$ by the solution for $k$.

3. $x = 298, y=-149, z=12$ is a solution.

4. Given that $\gcd(a,b)=1$, we know that $ax+by=1$ has integer solutions $x=x_0$ and $y=y_0$ that can be found using the Euclidean Algorithm. Now consider $x=cx_0$ and $y=cy_0$. Notice that

\begin{align} ax+by&=cax_0+cby_0\\ &=c(ax_0+by_0)\\ &=c \cdot 1\\ &= c \end{align}

Hence, $ax+by=c$ always has a solution for every integer $c$.

As for $37x+47y=103$, $x=-15$ and $y=14$ gives the smallest sum $x+y$.