Given that $gcd(1,4) = 1$, how can I apply the Euclidean algorithm to find values for $x$ and $y$ such that $1x + 4y = 1$?

Question

An intermediate step in a problem I'm trying to solve is to find $gcd(1, 4)$. Using the Euclidean algorithm, this is $1$:

$$ 1 = 0\times4 + 1 \\ 4 = 4\times1 + 0 $$

Bezout's identity tells us that the $gcd$ of two numbers $a$ and $b$ can be written as a linear combination of some integers $x$ and $y$:

$$ ax + by = d $$

In our case:

$$ 1x + 4y = 1 $$

To find values of $x$ and $y$, I learned that we can use the Euclidean algorithm and back-substitution. But while I'm able to perform this successfully for other types of problems, I'm stuck on this particular one.

If we have these steps:

$$ 1 = 0\times4 + 1 \\ 4 = 4\times1 + 0 $$

Then working backwards to solve for $1$:

$$ 1 = 1 - 0\times4 = 1 - (4-4\times1)\times4 $$

And I feel like I'm not really making any meaningful progress. My book claims that the answer is $x = -3$ and $y = 1$ but does not clarify how it arrived at this solution. I understand that this solution works, but I don't understand how to derive it using the Euclidean algorithm. What am I missing?

Answer 1

The algorithm doesn't really work for cases like this because you start with $$4=4(1)+0$$ and then you usually work backwards but there is nothing to cancel. We can just guess $-3(1) + 1(4)=1$ in this case.

For example, if we $\text{gcd(15,22)}$ we would start by getting the gcd with a series of divisions. $$22=1(15)+7$$ $$15=2(7)+1$$ $$7=7(1)=0$$ and this gives us $\text{gcd}(15,22)=1$

Then we would work backward to get $$15-2(7)=1$$ $$15-2(22-15)=1$$ $$3(15)-2(22)=1$$

Since we start with with the gcd on the first line there is nothing to work backward with so we must end up guessing.

But for any $n$, $\text{gcd}(n,1)=1$ and we can use $(1-n)1+1(n)=1$.

Answer 2

There are infinitely many solutions to this problem. The "extended" Euclidean algorithm would say to go backwards using the divisions done with nonzero remainders.

In your case, the only one is: $1=4\cdot 0+1$. Solve for the remainder: $1-4\cdot 0=1$ and you have a solution: $1(1)+4(0)=1$. You can let $x=1$ and $y=0$.

Your books essentially gives a (different) solution by examination.

Given any $n$, you have $\mathrm{gcd}(n,1)=1$. In such a case, an "obvious" solution to the linear combination problem is $1(1)+n(0)=1$ (ie $x=1$ and $y=0$). Another "obvious" solution is $1(1-n)+n(1)=1$ (ie $x=1-n$ and $y=1$).

Answer 3

A particular solution is $x = 1$ and $y=0$. Now in general you can consider for $n\in \mathbb{Z}$: $$x_{n} = 1 + 4n\quad \text{and} \quad y_{n}=-n$$ and these are indeed solutions.

Note in the general case that if $x_{0}$ and $y_{0}$ satisfies $$ax_{0}+by_{0}=c$$

then $$x_{n}=x_{0}+\frac{b}{(a,b)}n\quad \text{and} \quad y_{n}=y_{0}-\frac{a}{(a,b)}n$$ are also solutions: $$ax_{n}+by_{n}=ax_{0}+by_{0}+\frac{ab}{(a,b)}n-\frac{ab}{(a,b)}n=c.$$