1
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 27 '20 at 17:41
  • $\begingroup$ I added the proof.It is possible to prove the algorithm Inductively this way but it is not necessary.Thanks $\endgroup$ – kasra Nov 27 '20 at 18:25
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 27 '20 at 18:31
  • $\begingroup$ 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 :-) $\endgroup$ – kasra Nov 27 '20 at 19:37
  • 1
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Nov 27 '20 at 19:47
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.