| | |
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.)
First, we observe by inspection that the greatest common divisor (gcd) of 105 and 121 is 1. We will need to go through the calculations 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.
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}$$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}$$What follows is a modified version of the Euclidean Algorithm:
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$:
The values of the variables after each pass through the algorithm is given in the table below:
| $x$ | $g$ | $v$ | $w$ | $s$ | $t$ | $q$ |
|---|---|---|---|---|---|---|
| 1 | 19789 | 0 | 23548 | 0 | 0 | 0 |
| 0 | 23548 | 1 | 19789 | 1 | 19789 | 0 |
| 1 | 19789 | -1 | 3759 | -1 | 3759 | 1 |
| -1 | 3759 | 6 | 994 | 6 | 994 | 5 |
| 6 | 994 | -19 | 777 | -19 | 777 | 3 |
| -19 | 777 | 25 | 217 | 25 | 217 | 1 |
| 25 | 217 | -94 | 126 | -94 | 126 | 3 |
| -94 | 126 | 119 | 91 | 119 | 91 | 1 |
| 119 | 91 | -213 | 35 | -213 | 35 | 1 |
| -213 | 35 | 545 | 21 | 545 | 21 | 2 |
| 545 | 21 | -758 | 14 | -758 | 14 | 1 |
| -758 | 14 | 1303 | 7 | 1303 | 7 | 1 |
| 1303 | 7 | -3364 | 0 | -3364 | 0 | 2 |
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$$The values of the variables after each pass through the algorithm is given in the table below:
| $x$ | $g$ | $v$ | $w$ | $s$ | $t$ | $q$ |
|---|---|---|---|---|---|---|
| 1 | 31875 | 0 | 8387 | 0 | 0 | 0 |
| 0 | 8387 | 1 | 6714 | 1 | 6714 | 3 |
| 1 | 6714 | -1 | 1673 | -1 | 1673 | 1 |
| -1 | 1673 | 5 | 22 | 5 | 22 | 4 |
| 5 | 22 | -381 | 1 | -381 | 1 | 76 |
| -381 | 1 | 8387 | 0 | 8387 | 0 | 22 |
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$$The values of the variables after each pass through the algorithm is given in the table below:
| $x$ | $g$ | $v$ | $w$ | $s$ | $t$ | $q$ |
|---|---|---|---|---|---|---|
| 1 | 22241739 | 0 | 19848039 | 0 | 0 | 0 |
| 0 | 19848039 | 1 | 2393700 | 1 | 2393700 | 1 |
| 1 | 2393700 | -8 | 698439 | -8 | 698439 | 8 |
| -8 | 698439 | 25 | 298383 | 25 | 298383 | 3 |
| 25 | 298383 | -58 | 101673 | -58 | 101673 | 2 |
| -58 | 101673 | 141 | 95037 | 141 | 95037 | 2 |
| 141 | 95037 | -199 | 6636 | -199 | 6636 | 1 |
| -199 | 6636 | 2927 | 2133 | 2927 | 2133 | 14 |
| 2927 | 2133 | -8980 | 237 | -8980 | 237 | 3 |
| -8930 | 237 | 83747 | 0 | 83747 | 0 | 9 |
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$$The following questions concern linear combinations of three values:
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}$$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$.
$x = 298, y=-149, z=12$ is a solution.
Suppose $\gcd(a,b)=1$. Prove that $ax+by=c$ has integer solutions $x$ and $y$ for every integer $c$, then find a solution to $37x+47y=103$ where $x$ and $y$ are as small as possible.
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$.