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: 121=1⋅105+16105=6⋅16+916=1⋅9+79=1⋅7+27=3⋅2+1←gcd2=2⋅1+0 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. 16=121−1059=105−6⋅16=105−6⋅(121−105)=7⋅105−6⋅1217=16−9=(121−105)−(7⋅105−6⋅121)=7⋅121−8⋅1052=9−7=(7⋅105−6⋅121)−(7⋅121−8⋅105)=15⋅105−13⋅1211=7−3⋅2=(7⋅121−8⋅105)−3⋅(15⋅105−13⋅121)=46⋅121−53⋅105 The last line gives us the solution we seek:
x=−53,y=46Now that we have one solution, and given that the gcd(105,121)=1, the rest of the solutions can be characterized by:
x=−53+121k,y=46−105kwhere 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 gcd(12345,67890)=15, the rest of the solutions can be characterized by the following, where k is an integer:
x=11+6789015k,y=−2−1234515kWritten more briefly, we have:
x=11+4526k,y=−2−823k with k∈ZThe last line gives us the solution we seek: x=−1645, y=9048.
Now that we have one solution, and given that the gcd(54321,9876)=3, the rest of the solutions can be characterized by the following where k is an integer:
x=−1645+98763k,y=9048−543213kWritten more briefly, we have:
x=−1645+3292k,y=9048−18107k with k∈ZWhat 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,x=1303, and y=−1095The 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,x=−381, and y=1448The 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,x=−8980, and y=10063The following questions concern linear combinations of three values:
Note that 6x+15y must always be a multiple of gcd. 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.
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.