As others say, one way to do it is using the identity $\gcd(a,b,c)=\gcd(a,(\gcd(b,c))$.
This identity is true since the "gcd" is the maximal element of the intersection of the sets of factors of the inputs. For example, taking $\gcd(6,10)$, the set of factors of $6$ is {$6, 3, 2, 1$}, the set of factors of $10$ is {$10, 5, 2, 1$}, their intersection is {$2, 1$}, and the maximal element is $2$. The identity follows since intersections of sets are commutative and associative.
However, it's also possible to extend Stein's algorithm to handle more than two inputs. Wikipedia gives 5 steps to Stein's algorithm, and we can change them to the following to compute the gcd of a set $S$ of numbers:
- If anything in $S$ is zero, remove it.
- If everything in $S$ is even, divide everything in $S$ by 2, and then multiply the final answer by 2 at the end.
- If some numbers in $S$ are even and some are odd, divide all the even numbers by 2.
- If every number in $S$ is odd, then choose an arbitrary element of $S$ and call it $k$. Replace every other element, say $n$, with $|n-k|/2$.
- Repeat steps 1–4 until there is only one remaining element in $S$. After you remember to multiply in the twos that you got from step 2, that's your gcd!
You are correct that mathematical induction consists of three steps:
- Prove the base case.
- Assume that the claim is true for some $n\in\Bbb N$ (possibly including $0$ if needed).
- Use the above assumption to prove the claim for $n+1$.
Let us see this in practice with standard example:
$$1+2+3+\ldots+n = \frac{n(n+1)}{2}\tag{1}$$
Base case: $$1=\frac{1(1+1)}{2}\quad\small\text{(obviously true)}$$
Assume that formula $(1)$ is true for some $n$. Now we need to prove that $$\underbrace{1+2+3+\ldots +n}_{\text{use the assumption on this}}+(n+1) = \frac{(n+1)(n+2)}{2}$$ and we can use the assumption to get $$1+2+3+\ldots +n+(n+1) = \frac{n(n+1)}{2} +(n+1) = \frac{(n+1)(n+2)}{2}$$ so we are done.
Now, in your example, what is used is version of induction called strong induction. The difference is that in step 2, we assume something stronger, but it turns out this is equivalent to "weak" induction (just happens to be more convenient in some cases).
- Prove the base case.
- Fix some $n\in\Bbb N$ and assume that the claim is true for all natural numbers $k$ when $k< n$.
- Use the above assumption to prove the claim for $n$.
I will now try to clarify the steps in your proof. Let us define $m=a+b\in\Bbb N$. We will do induction on $m$.
Base case is $m = 2$. Since $a+b = 2$ and $a,b>0$, we must have $a=b=1$, so $$\gcd(na,nb) = \gcd(n,n) = |n| = |n|\gcd(a,b).$$
Now let $m\in\Bbb N$ and assume that $$\gcd(na',nb') = |n|\gcd(a',b'),\quad(\forall a',b'\in\Bbb N)\ a'+b' < m.\tag{2}$$ We want to prove that the claim is true for $a,b$ (remember that $a+b=m$).
Using Euclid's division, we have $a = qb + r$, $0\leq |r|<b$, and thus $$\gcd(a,b) = \gcd(b,r).$$ But if we multiply everything by $n$, we get $na = qnb + nr$, $0\leq |nr| < nb$, so we have that $$\gcd(na,nb) = \gcd(nb,nr).$$
Notice that if we can prove that $$\gcd(nb,nr) = |n|\gcd(b,r),\tag{3}$$ we will have $$\gcd(na,nb) = |n|\gcd(a,b)$$ as well. So let us see if we can employ our assumption $(2)$ - for it to work, we must check that $b+r<m$, and you can check with your proof how it is done. Hence, we can apply induction assumption to conclude that $(3)$ is true.
Also, notice that we indeed needed strong induction, since we don't know that $b + r + 1 = m$, which we would want in ordinary induction.
Best Answer
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
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.