# Inductive proof for Euclid's algorithm

I'm studying The Algorithm Design Manual and the proof exercises of the first chapter are really hard(at least for a first-timer). I asked a question on here about the previous question in the exercises two days ago and I still haven't been able to go through the whole page.

Anyway, I'm trying to inductively prove Euclid's algorithm(I'm think the deductive proof is simpler but I want to familiarize myself with Inductive proofs). No matter how I approach the problem, I just prove the algorithm in a deductive way that doesn't require induction in any way.

I would really appreciate if you could give an inductive proof of Euclid's algorithm or provide me with a resource that does so.Thanks in advance.

The greatest common divisor of positive integers x and y is the largest integer
d such that d divides x and d divides y. Euclid’s algorithm to compute gcd(x, y)
where x > y reduces the task to a smaller problem:

gcd(x, y) = gcd(y, x mod y)

Prove that Euclid’s algorithm is correct.


Edit:

The deductive proof that I know of is as follows:

A. given that a,b,c,y,x are all integers we can prove: a|b ^ a|c → a|(xb + yc)

B. p,q,r and t = (pr + q) are all integers.we want to prove gcd(pr+q,p)=gcd(p,q) let m = gcd(pr+q,p) and n = gcd(p,q) since A, n|p ^ n|q → n|pr + q n is a common divisor of (pr+q,p) and m is the greatest common divisor of (pr+q,p) therefore, m >= n.

C. P: m|p which we know is true Q: m|(pr + q) which is also true R: m|q we know that m|p ^ m|q → m|pr + q is true, so based on this and P,Q and R we can deduce that R is true.

m is a common divisor of (p,q) and n is the greatest common divisor of (p,q) therefore, n >= m.

B is true Q is true B ^ Q → m = n is also true.

therefore, m = n

gcd(pr+q,p) = gcd(p,q)

• What deductive proof do you know, and why do you think that it is not inductive? Given that the Euclidean algorithm is basically a while loop, it's hard to think of a proof which is not by induction. – Yuval Filmus Nov 27 '20 at 17:41
• I added the proof.It is possible to prove the algorithm Inductively this way but it is not necessary.Thanks – kasra Nov 27 '20 at 18:25
• Your proof shows that $\mathit{gcd}(x,y) = \mathit{gcd}(y, x \bmod y)$. It doesn't show that the Euclidean algorithm is valid. For that you need induction. – Yuval Filmus Nov 27 '20 at 18:31
• I don't really understand.Isn't that the only thing that are trying to prove?If not,what is it that we are trying to prove here?I might be mistakenly assuming that gcd(x,y)=gcd(y,x % y) is the Euclid's algorithm and if I am, please tell me what Euclid's algorithm is.Thanks for the response :-) – kasra Nov 27 '20 at 19:37
• Euclid’s algorithm is an algorithm for computing the GCD of two positive integers. It’s not a single equation. Are you familiar with partial correctness? Termination proofs? – Yuval Filmus Nov 27 '20 at 19:47

Here is Euclid's algorithm.

The input is two integers $$x \geq y \geq 1$$.

While $$x > y$$, the algorithm replaces $$x,y$$ with $$y, x\bmod y$$.

The final output is $$x$$.

In order to prove that this algorithm correctly computed the GCD of $$x$$ and $$y$$, you have to prove two things:

• The algorithm always terminates.
• If the algorithm terminates, then it outputs the GCD (partial correctness).

The first part is proved by showing that $$x + y$$ always decreases throughout the loop. The second part is proved by induction, using the equation $$\mathit{gcd}(x,y) = \mathit{gcd}(y,x\bmod y).$$ Both parts also use the loop invariant $$x \geq y \geq 1$$.

What you call the "deductive proof" is only part of the proof of partial correctness. It forms the main technical part inside a proof by induction on the number of iterations.