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