Solving for $x, y$ in $\gcd(a,b) = ax + by$

Question

I want to solve for $x$ and $y$ in terms of $a$, $b$, and previous $x$ and $y$ values. In other words, since it is a recursive function, I want to use $x'$, $y'$, $a$, $b$ to solve for $x$ and $y$, where

$$d = \gcd(b,a\mathbin{\%} b)$$

$$d = a x + b y$$

$$d = b x' + (a\mathbin{\%}b) y'$$

I've been looking at this for hours and can't seem to make sense of it.

(Note that $x'$ and $y'$ are not derivatives)

Answer 1

Perhaps an example will help. Lets look at, say, $\gcd(110,45)$.

The way I like to do it, I write numbers in three columns. Start out with $a~~~~1~~~~0$ and $b~~~~~0~~~~~1$ as your first two rows.

$\begin{array}{l|l|l} 110&1&0\\45&0&1\end{array}$

From here, to find the next row, ask yourself how many times the left entry of the current bottom row fits into the left entry of the row previous without going over. Subtract the last row times that amount from the previous row to create the next row.

$\begin{array}{l|l|lr} 110&1&0\\45&0&1&~~45~\text{fits into}~110~\text{twice, so subtract twice this row from previous}\\ 20&1&-2\end{array}$

Repeat this process until your next row would have begun with a zero.

$\begin{array}{l|l|lr} 110&1&0\\45&0&1\\ 20&1&-2\\ 5&-2&5&~~~20~\text{fits into 45 twice}\\ 0&&&\text{stop here}\end{array}$

The entries in the second column correspond to the coefficient of your $a$ while the third column corresponds to the coefficient of $b$. Here, we have $110 = 1\cdot 110+0\cdot 45$, we have $20 = 110\cdot 1 + (-2)\cdot 45$, and more importantly, we have $5=(-2)\cdot 110+5\cdot 45$.

The final nonzero entry in the left column is also the gcd of the two numbers.

Here is one more example already worked out:

$\begin{array}{c|c|c}95&1&0\\ 84&0&1\\ 11&1&-1\\ 7&-7&8\\ 4&8&-9\\ 3&-15&17\\ 1&23&-26\\ 0\end{array}$

This implies $\gcd(95,84)=1=23\cdot 95-26\cdot 84$

---

In more detail, if we are midway through and are at the following rows:

$\begin{array}{c|c|c} A_1&A_2&A_3\\ B_1&B_2&B_3\end{array}$

then the next row is calculated as:

$\begin{array}{c|c|c} A_1 - B_1\lfloor \frac{A_1}{B_1}\rfloor&A_2-B_2\lfloor \frac{A_1}{B_1}\rfloor& A_3-B_3\lfloor \frac{A_1}{B_1}\rfloor\end{array}$

In the above second example, jumping to the middle lines, suppose we have $\begin{array}{c|c|c}11&1&-1\\ 7&-7&8\end{array}$

The next line is $\begin{array}{c|c|c}11-7\lfloor\frac{11}{7}\rfloor&1-(-7)\lfloor\frac{11}{7}\rfloor & -1-8\lfloor\frac{11}{7}\rfloor\end{array}$

which simplifies as $\begin{array}{c|c|c}11-7&1-(-7)&-1-8\end{array}$

which simplifies as $\begin{array}{c|c|c}4&8&-9\end{array}$

Answer 2

After some help, I have solved it algebraically. We have

d = ax + by = bx' + (a%b)y'

(a%b) = a - a/b * b 

(this is integer division)

so we can set it up to match the form of ax + by, filling in a(...)+b(...) :

bx' + a%b y'
bx' + (a - a/b b) y'
bx' + ay' - a/b by'
ay' + bx' - a/b * by' 
ay' + b(x' - a/b y')

so we can write the new values of x and y as:

x = y'

y = x' - a/b y'