Generalized Induction Verification Consider the following simple exercise.

Prove or disprove: $\gcd(km, kn) = k \gcd(m, n)$, where $m, n, k$ are natural numbers.

Now, this is easy to prove using prime factorization. Knowing that this proposition was true, I decided to try and prove it just using induction and the Euclidean algorithm.
I only recently learned about generalized induction, so I was wondering if someone could look this over and tell me if it is valid or not.

Since the $\gcd$ function is symmetric with respect to its arguments, we can assume without loss of generality that $m \le n$. We proceed by strong induction using a lexicographical ordering $(<<)$ on $\mathbb{N}^2$.
For $m = n = 0$, the result is trivial. Assume true for all $(m', n') < < (m, n)$. Then
  \begin{align*}
 k\gcd(m, n) &= k \gcd(n \!\!\!\!\mod m, m) & \textit{By the Euclidean algorithm}\\
 &= \gcd( k (n \!\!\!\!\mod m), k m) & \textit{By induction}\\
 &= \gcd( k n \!\!\!\!\mod k m, k m) & \textit{Property of mod function} \\
 &= \gcd( k m, k n) & \textit{By the Euclidean algorithm}\\
 \end{align*}
  The reader will forgive the slight abuse of notation: $n \!\!\mod m = n - m \lfloor n / m\rfloor$. Thus the result holds for all pairs of natural numbers. 

 A: Your proof is very close. The problem is with the base case. You cannot take a number modulo $0$, and you do not eliminate the possibility that $m=0$. Instead of proving just the case $(m',n')=(0,0)$ (and is that trivial by the way? ... I have never seen anyone take the GCD of $0$ and $0$), I would take as base case all $(0,n)$ for $n\in\mathbb{N}$. This is easy since $$k\gcd(0,n)=kn, \quad\gcd(k\cdot0,k\cdot n)=\gcd(0,kn)=kn.$$ Now the next case must have $m\ge 1$, so your proof follows through validly.

If this is your first time using strong induction, I have always found it very helpful to make things "concrete" to aid my understanding. I like to actually "visualize" the transition that happens from base case to case I, from case I to case II, etc. Your proof is a sort of "algorithm" which we can follow to make each transition.
Here, we have established the case $(0,0)$. Next in line is $(0,1)$. You proof tells us to write down $$k\gcd (0,1)=k\gcd (1\bmod 0,0)=\gcd(k\bmod (k0),k\cdot 0)$$ But already this is making no sense. What is $1\bmod 0$?
Now assume that we have strengthened our base knowledge to all $(0,n)$. Next in line is $(1,0)$. We write $$k\gcd(1,0)=k\gcd(0\bmod 1,1)$$ By induction (i.e. previous knowledge) this is $$\gcd(k\cdot 0\bmod 1,k\cdot 1)=\gcd(k\cdot 0\bmod (k\cdot 1),k\cdot 1)=\gcd(k\cdot 1,k\cdot 0)$$ and we have proven the case! You can see how each case follows naturally from a previous one.
