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 &gt; 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 &gt;= 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 &gt;= m.
B is true
Q is true
B ^ Q → m = n is also true.
therefore, m = n
gcd(pr+q,p) = gcd(p,q)
Here is Euclid's algorithm.
The input is two integers $x \geq y \geq 1$.
While $x &gt; 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 &quot;deductive proof&quot; 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.