Processing math: 67%
     

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 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=1105+16105=616+916=19+79=17+27=32+1gcd2=21+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=1211059=105616=1056(121105)=710561217=169=(121105)(71056121)=712181052=97=(71056121)(71218105)=15105131211=732=(71218105)3(1510513121)=4612153105 The last line gives us the solution we seek:

      x=53,y=46

      Now 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=46105k

      where k is an integer.

    2. 12345x+67890y=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: 67890=512345+616512345=26165+15gcd6165=41115+0 Now, we write the gcd as various linear combinations, working our way backwards through Euclid's Algorithm, until we get the linear combination desired: 15=1123452616515=1123452(67890512345)15=1112345267890

      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=21234515k

      Written more briefly, we have:

      x=11+4526k,y=2823k with kZ
    3. 54321x+9876y=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: 54321=59876+49419876=14941+49354941=14935+64935=8226+3gcd6=23+0 Now, we write the gcd as various linear combinations, working our way backwards through Euclid's Algorithm, until we get the linear combination desired: 3=1493582263=14935822(494114935)3=823493582249413=823(987614941)82249413=8239876164549413=82398761645(5432159876)3=90489876164554321

      The 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=9048543213k

      Written more briefly, we have:

      x=1645+3292k,y=904818107k with kZ

  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=(gax)/b and stop.
    3. Find q and t so that g=qw+t, with 0t<w.
    4. Set s=xqv
    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:

      xgvwstq
      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,x=1303, 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:

      xgvwstq
      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,x=381, 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:

      xgvwstq
      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,x=8980, 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. 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.