Exercises - Linear Combinations

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

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$  

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$

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.