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$  
    2. $12345x + 67890y = \textrm{gcd}(12345,67890)$  
    3. $54321x + 9876y = \textrm{gcd}(54321,9876)$  
  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$  
    2. $a=31875$, $b=8387$  
    3. $a=22241739$, $b=19848039$  
  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$
  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.  

◆ ◆ ◆