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