Euclid's Algorithm

if $gcd(a,b)|̸c$ There exists no solution to (1).

Proof:

Suppose for a contradiction there does exist a solution, and let $p=gcd(a,b)$

$$\Rightarrow \mathrm{\exists }\lambda ,\delta \in \mathbb{Z}s.t.a=\lambda p,b=\delta p$$

Factoring (1):

$$\Rightarrow (\lambda x+\delta y)p=c$$

Which shows $p$ must divide $c$ and hence is a contradiction.

There exists a solution to (1) if $c=gcd(a,b)$

Proof:

We have

$$gcd(a,b)\equiv p\mathrm{mod}b$$

Then a solution exists to (1) iff there exists some $x$ s.t.

$$\begin{array}{}\text{(2)}& ax\equiv p\mathrm{mod}b\end{array}$$

First, note that $\lambda$ and $\delta$ are coprime, proof: consider

$$gcd(\lambda p,\delta p)$$

If $gcd(\lambda ,\delta )>1\Rightarrow gcd(a,b)\ne p$ and hence is a contradiction.

It's commonly known that since $\lambda$ and $\delta$ are coprime, there exists an integer $x$ s.t.

$$\lambda x\equiv 1\mathrm{mod}\delta$$

And hence this x is a solution to:

$$p(\lambda x-1)\equiv 0\mathrm{mod}b$$

Rearranging:

$$ax\equiv p\mathrm{mod}b$$

And therefore:

$$ax+by=gcd(a,b)$$

Where y is $-\lfloor \frac{ax}{b}\rfloor$. Hence trivially there also exists a solution for any integer multiple of gcd(a, b).

If there exists one solution to $ax+by=c$ then there exists infinite solutions.

Proof:

Consider solutions to:

$$\begin{array}{}\text{(3)}& k_{a}a+k_{b}b=0\end{array}$$

Setting $k_a=\frac{lcm(a,b)}{a}$ and $k_b=-\frac{lcm(a,b)}{b}$ gives a solution to (3). Also note that:

$$(x+k_a)a+(y+k_b)b=c$$

Is also a solution given $x,y$ are the solutions found above, and furthermore:

$$(x+M{k}_a)a+(y+M{k}_b)b=c$$

Where $M$ is any integer, is a solution.

Express gcd(1442, 980) as a linear combination of 1442 and 980.

First we obtain gcd(1442, 980) using Euclid's algorithm:

$$\begin{array}{}\text{(4)}& 1442& =1\ast 980+462\text{(5)}& 980& =2\ast 462+56\text{(6)}& 462& =8\ast 56+14\text{(7)}& 56& =4\ast 14\end{array}$$

Hence gcd(1442, 980) = 14. Now we take the penultimate equation and rearrange to make 14 the subject:

$$\begin{array}{}\text{(8)}& 14& =462-8\ast 56\text{(9)}& 14& =(1442-980)-8(980-2\ast 462)\text{(10)}& 14& =1\ast 1442-9\ast 980+16\ast (1442-980)\text{(11)}& 14& =17\ast 1442-25\ast 980\end{array}$$

And thus we arrive at the linear combination.