5
$\begingroup$

I've been struggling with a basic exercise involving Euclid's algorithm and mathematical induction. Given the following definition of the Euclid's algorithm (in Java):

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b); // '%' denotes the modulo operator
}

the task is formulated as follows:

Use mathematical induction to prove that Euclid's algorithm computes the greatest common divisor of any pair of nonnegative integers $a$ and $b$.

Now, I'm not sure how should I interpret this phrase. Am I supposed to prove that the algorithm is actually calculating the greatest common divisor, or is it more like "assuming that the algorithm calculates the greatest common divisor, show that it works for an arbitrary pair of nonnegative integers $a$ and $b$"? So far I tried to use induction to show that $\gcd(a, b) = \gcd(b, a \bmod b)$ but I have a feeling that it may not really be the point... :S

Please do not provide a complete proof in the answer, but only help me to get started (my proving math skills are close to zero but I'm trying to learn).

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ Yes, you are supposed to prove that the algorithm is actually calculating the greatest common divisor. The statement "assuming that the algorithm calculates the greatest common divisor, show that it works for an arbitrary pair of nonnegative integers" does not make sense to me. $\endgroup$ – Martin R May 9 '15 at 18:32
  • $\begingroup$ Ok, thank you. Does the gcd(a,b)=gcd(b,a mod b) make sense then? Otherwise, how would I begin? $\endgroup$ – Caleb9 May 9 '15 at 18:36
  • $\begingroup$ The book that really helped me with this problem is "Introduction to algorithms" by Udi Manber. Chapter 2 "Mathematical induction" demonstrates many useful induction techniques with short and simple examples. $\endgroup$ – Panic Aug 27 '17 at 16:00
2
$\begingroup$

Yes, you are supposed to prove that the algorithm is actually calculating the greatest common divisor.

To prove the statement by induction, you could formulate is as

For all $N \in \Bbb N$ and for all nonnegative integers $a \le N$ and $b \le N$, the Euclidean algorithm computes the greatest common divisor of $a$ and $b$.

and prove this by induction on $N$.

$\gcd(a, b) = \gcd(b, a \bmod b)$ should be proved first and is the essential tool in the inductive step.

$\endgroup$
1
$\begingroup$

You need to prove two things:

  • Every divisor that $a$ and $b$ have in common is a divisor that $a$ and $a-b$ have in common; and
  • Every divisor that $a$ and $a-b$ have in common is a divisor that $a$ and $b$ have in common.

It follows that the set of all divisors that $a$ and $b$ have in common is the same as the set of all divisors that $a$ and $a-b$ have in common. Consequently the largest divisor that $a$ and $b$ have in common is the same largest divisor that $a$ and $a-b$ have in common.

$\endgroup$
  • $\begingroup$ Thanks, that should get me started. $\endgroup$ – Caleb9 May 9 '15 at 18:38
1
$\begingroup$

No induction is really required for that. It is needed only to prove the algorithm terminates. You just have to prove that $$\bigl\{\text{common divisors of }\,a\,\text{ and }\,b\bigr\}=\bigl\{\text{common divisors of }\,b\,\text{ and }\,b\bmod a\bigr\}.$$

$\endgroup$
  • $\begingroup$ To say that it terminat is almost the same thing as induction. ${}\qquad{}$ $\endgroup$ – Michael Hardy May 9 '15 at 20:20
  • $\begingroup$ It is the basis of induction: every non-empty subset of $\mathbf N$ has a smallest element. Or, if you want, it is finite descending induction. $\endgroup$ – Bernard May 9 '15 at 20:24
  • $\begingroup$ Exactly. ${}\qquad{}$ $\endgroup$ – Michael Hardy May 9 '15 at 20:32

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.