Prove that Euclid's algorithm computes the GCD of any pair of nonnegative integers 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.
 A: 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. 
A: 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.
A: 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\}.$$
