# proving the formula for x and y in the extended euclidean algorithm

I found this on the wikipedia page of the Extended Euclidean Algorithm:

It states:

"Suppose $d_i = d_{i-2} - k_{i-1} \cdot d_{i-1}$.
Then it must be that
$x_i = x_{i-2} - k_{i-1} \cdot x_{i-1}$ and
$y_i = y_{i-2} - k_{i-1} \cdot y_{i-1}$
This is easy to verify algebraically with a simple substitution."

Furthermore, what I know is that:
$d_i = ax_i + b y_i$

For my paper on RSA-Encryption I have proven the first equation to be true,
but I don't see how they have verified, or even come up with both formula's for x and y.
I do see that it works, but I find myself stuck trying to verify them by substitution.

Could anybody help me out? Thanks :)

-

At each stage $i$ you want the numbers $x_i,y_i$, and $d_i$ to satisfy the equation $$d_i=x_ia+y_ib\;,\tag{1}$$ You start with $x_1=1,y_1=0,x_2=0,y_2=1,d_1=a$, and $d_2=b$, so that $(1)$ is satisfied for $i=1$ and $i=2$. Then for $i>2$ you define

$$d_i=\operatorname{rem}(d_{i-2},d_{i-1})\;,$$ the remainder when $d_{i-2}$ is divided by $d_{i-1}$. Let $k_{i-1}$ be the quotient in this division, so that

$$d_{i-2}=k_{i-1}d_{i-1}+d_i\;;$$

then $$d_i=d_{i-2}-k_{i-1}d_{i-1}\;,\tag{2}$$ and we want to know what $x_i$ and $y_i$ should be in order to make $(1)$ hold for $i$. Since $(i)$ is assumed to hold for $i-1$ and $i-2$, we know that

$$d_{i-1}=x_{i-1}a+y_{i-1}b\quad\text{and}\quad d_{i-2}=x_{i-2}a+y_{i-2}b\;.$$

Substitute these into $(2)$:

\begin{align*} d_i&=(x_{i-2}a+y_{i-2}b)-k_{i-1}(x_{i-1}a+y_{i-1}b)\\ &=(x_{i-2}-k_{i-1}x_{i-1})a+(y_{i-2}-k_{i-1}y_{i-1})b\;, \end{align*}

and it’s clear that we need to set

$$x_i=x_{i-2}-k_{i-1}x_{i-1}\quad\text{and}\quad y_i=y_{i-2}-k_{i-1}y_{i-1}$$

in order to make $(1)$ hold for $i$.

-
are we allowed to do that? since when $d = ax + by$ and $d = va + wb$ we can't say x = v and w = y – Wampie Driessen Jan 8 '13 at 19:53
@Wampie: Allowed to do what? I did nothing but ordinary algebra. – Brian M. Scott Jan 8 '13 at 19:55
in your last three sentences, you set $x_i = x_{i-2} - k_{i-1} * x_{i-1}$, and you do that based on the fact that $d = {x_{i-2} - k_{i-1} * x_{i-1}}a + {y_{i-2} - k_{i-1} * y_{i-1}}b$ – Wampie Driessen Jan 8 '13 at 19:58
@Wampie: Of course: once we know that $$(x_{i-2}-k_{i-1}x_{i-1})a+(y_{i-2}-k_{i-1}y_{i-1})b\;,$$ we know that setting $$x_i=x_{i-2}-k_{i-1}x_{i-1}\quad\text{and}\quad y_i=y_{i-2}-k_{i-1}y_{i-1}$$ makes $(1)$ true. This shows how to calculate acceptable values of $x_i$ and $y_i$ from $x_{i-1},x_{i-2},y_{i-1}$, and $y_{i-2}$, which is exactly what we want to be able to do. – Brian M. Scott Jan 8 '13 at 20:01
Well thank you :) – Wampie Driessen Jan 8 '13 at 20:10

Your equation $d_i = ax_i + b y_i$ is called the invariant. It is true for every step of the algorithm, for every index $i$. The algorithm starts with two actually, $i=0$ and $i=1$, so that the two equations may be combined to obtain the next. If they are combined, they remain true. The $k$ values may be any value desired as far as retaining the validity of the equations, but a specific $k$ is chosen so as to reach the minimum $d$

For example, if $k=1$ we have the truth of the two equations implies the next: \begin{align} & d_0 &=& ax_0 &+ b y_0\\ & d_1 &=& ax_1 &+ b y_1\\ \Rightarrow & d_1 - d_0 &=& a(x_1 - x_0) &+ b (y_1 - y_0) \\ \end{align}

-