# Explanation of a proof of the Extended Euclidean Algorithm?

I understand how and why the algorithm works, but I am confused by a specific proof of it. I know I have asked a similar question before, but that question was regarding proof of the algorithm. This question is asking for an explanation of a specific proof.

If d divides both a and b, and d = ax + by for some integers x and y, then necessarily d = gcd(a,b)

Proof: By the first two conditions, d is a common divisor of a and b so that it cannot exceed the greatest common divisor; that is, d ≤ gcd (a,b). On the other hand, since gcd(a,b) is a common factor of a and b, it must also divide ax + by = d, which implies gcd (a,b) ≤ d. Putting these together, d = gcd (a,b)

I understand the first part of the proof (d cannot exceed gcd (a,b)), however I am confused by the second part. It states d cannot be less than gcd (a,b), however to me it seems it can. Won't any common divisor (not just the greatest one) divide ax + by? For example, let a be 4, b be 12, x be -2, and y by 1.

Therefore you get: (4)(-2) + (12)(1) = (-8) + (12) = 4.

4 (the greatest common divisor) is not the only one can divide it. Other common divisor such as 2 can also divide ax + by.

Therefore the greatest common divisor is not the only one that fulfills the second part of the proof (so d does not have to be greater than gcd (a,b) to divide ax + by). What am I misunderstanding here?

• Before I answer your question - are you aware that every time you have written 'greatest common denominator' you mean 'greatest common divisor'? We can create arbitrarily large common denominators of $a$ and $b$ just by multiplying $ab$ by some very large integer. – John Gowers Mar 31 '12 at 20:34
• Thank You, I changed it. Aren't divisors and denominators the same thing though? – user26649 Mar 31 '12 at 20:36
• A divisor of a number $a$ is a number which goes into $a$. The denominator of a fraction $\frac{a}{b}$ is $b$. You're probably getting confused with the phrase lowest common denominator of a set $S$ of fractions, which is the largest number that can be a denominator for all of them. For example, the lowest common denominator for $\{\frac{1}{4},\frac{1}{5},\frac{1}{6}\}$ is $60$; i.e., the lowest common multiple of the denominators when the fractions are written in their lowest terms. Please ignore my comment about arbitrarily high denominators - I was confusing the lcd and the lcm. – John Gowers Mar 31 '12 at 20:59
• Understood, thank you :) – user26649 Mar 31 '12 at 21:26

## 3 Answers

Here is where you come unstuck:

$d$ - which is the same thing as $ax+by$ - can indeed not be less than $\gcd (a,b)$. The fact that any other common divisor of $a$ and $b$ also divides $ax+by$ - which is the same thing as $d$ - is immaterial: it just means that $d$ can also not be less than any of the other common divisors of $a$ and $b$.

In the example you give, $d$ is $4$, which is exactly the $\gcd$ of $4$ and $12$ - so there is no contradiction here. You are obviously getting confused, so I'll try to break it down for you.

We want to show that $d=\gcd (a,b)$. We do this by showing that $d\le\gcd(a,b)$ and also that $d\ge\gcd(a,b)$.

The first part uses the fact that $d$ divides both $a$ and $b$ to show that $d\le\gcd(a,b)$. You say you understand this, so I won't dwell on it.

The second part uses the fact that $d=ax+yb$ to show that $d\ge\gcd(a,b)$. This is also easy - we can easily see that $\gcd(a,b)$ divides $d$, so $\gcd(a,b)\le d$.

My guess is that you got confused between $d$ and $\gcd(a,b)$. Don't do that - until you've proved they are equal, just think of $d$ as some number which is a common divisor of $a$ and $b$ and which is also equal to $xa+yb$ for some $x,y$.

Let me know if there's anything else you want me to clear up.

• Awesome, thanks :) – user26649 Mar 31 '12 at 22:24

Yes, any common divisor of $a$ and $b$ will divide all $ax+by$; but your parenthetical comment, "(so $d$ does not have to be greater than $\gcd(a,b)$ to divide $ax+by$)" is confusing the issue: $d$ is $ax+by$, and we are showing that any common divisor of $a$ and $b$ will divide any linear combination of $a$ and $b$.

So, in particular, any common divisor of $a$ and $b$ will divide $d$ (because $d=ax+by$ is a linear combination of $a$ and $b$). And so, applying this to the gcd we conclude that the greatest common divisor of $a$ and $b$ will divide $d$, and so $\gcd(a,b)\leq |d|$.

Your example does not contradict this, since $2$ also divides $4(-2)+12(1) = 4$.

On the other hand, since $\gcd(a,b)$ is a common factor of $a$ and $b,$ it must also divide $ax + by = d$

Both $\gcd(a,b)\ |\ a,$ and $\gcd(a,b)\ |\ b,$ implies that: $\gcd(a,b)\ |\ (ax + by),$ which implies that: $\gcd(a,b)\ |\ d.$

which implies $\gcd (a,b) ≤ d.$

$\gcd(a,b)\ |\ d$ implies that: $\gcd(a,b) \le d.$ (Recall: $n\ |\ m$ means that $n$ could be less than or equal to $m$).

Putting these together, $d = \gcd (a,b)$

We've just shown that $d ≤ \gcd (a,b),$ and $\gcd (a,b) ≤ d,$ i.e. $$\gcd (a,b) ≤ d ≤ \gcd (a,b)$$ which actually means that $d = \gcd(a,b)$ (Recall: $3 \le d \le 3 \implies d = 3$)