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 :)
 A: 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$.
A: 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}
