Inductive proof for Euclid's algorithm

Question

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)

Answer 1

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.