Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :)

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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$.

share|improve this answer
    
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}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.