Confused by induction on $\max(n ,m)$ in proof of $\gcd(t^n-1, t^m-1)=t^{\gcd(n,m)}-1$

Question

I am a non-mathemetician carefully working his way through a detailed introduction to Euclidean domains and Euclid's algorithm. I'm stuck trying to follow an 'induction' step in one of the proofs and I'd really appreciate some help.

My objective here is to understand the thought process that the author is trying to lead me through. I am aware of other answers (e.g. this one) discussing alternate proofs.

I understand the basics of proof by induction but this is the first time I've looked at one involving two variables. I think I just need a bit more clarity on the intermediate steps.

I'm OK with everything preceding the line commented in red, but I can't see how the author intends me to make that step...

Theorem 2.2. $\gcd(s,t)=\gcd(s,t-rs)$ for any elements s, t, r.

Theorem 2.3. Let t be an element in any domain where gcd's exist. Then if $m$ and $n$ are positive integers, $$\gcd(t^n-1,t^m-1)=t^{\gcd(n,m)}-1$$ Proof: Induction on $\max(n,m)$. If $\max(m,n)=1$, or if $n=m$, the result is trivial. Otherwise we assume $m<n$ and note that $(t^n-1)-t^{n-m}(t^m-1)=t^{n-m}-1 \tag{E}$. Hence: \begin{align} \gcd(t^n-1, t^m-1)&=\gcd(t^m-1, t^{n-m}-1)&\text{(Theorem 2.2)}\\ &=t^{\gcd(m,n-m)}-1 &\text{(induction)} &\color{red}{\Leftarrow \text{ I get stuck here}}\\ &=t^{\gcd(n,m)}-1 &\text{(Theorem 2.2 again).} \end{align}

Answer 1

Point 1: induction with two variables

Suppose that you want to demonstrate that a property $P(n,m)$ is valid for all ordered pairs of integers $(n,m)$. I claim that if:

1. $P(1,1)$ is valid
2. $P(n,m)$ is valid for all $(n,m)$ such that $\max(n,m) \le N$ then $P$ is valid for all $(n,m)$ such that $\max(n,m) \le N+1$

then $P$ is valid for all ordered pairs of integers $(n,m)$.

Proof by contradiction. Suppose that $P(n_0,m_0)$ is not valid and that $N_0 = \max(n_0,m_0)$ is the smallest maximum of $(n,m)$ for which $P$ is not valid. Then one of the $n_0,m_0$ is not equal to $1$ as asserted by the first assumption above. By symmetry, we can suppose that $n_0 \ge m_0 > 1$ and $N_0 = \max(n_0,m_0) > 1$. By the hypothesis on $N_0$ if $n_0 = m_0$, then $P(n_0-1,m_0-1)$ is valid and by second assumption above $P(n_0,m_0)$ is also valid; a contradiction. And if $n_0 >m_0$ then $P(n_0-1,m_0)$ is valid as $\max(n_0-1,m_0) = \max(n_0,m_0) -1$. But then again applying second assumption above you get again the contradiction $P(n_0,m_0)$ is valid.

This is exactly the rationale of the proof that you describe. What I did above is to explain why it is valid.

Point 2: coming back to the prove of Theorem 2.3

The author uses the two assumptions I mention above. First for $\max(n,m)=1$. And then as he assumes $m <n$, he gets $\max(m,n-m) < \max(m,n)$ and can apply equation $(E)$.

Answer 2

Building and expanding on the answer above, here for the record is my attempt at a full explanation.

To prove some property $P(m,n)$ by induction on $max(m,n)$ requires two steps:

1. show that $P(1,1)$ is valid
2. show that if $P(m,n)$ is valid for all $max(m,n)\leqslant N$, then it is valid for all $max(m,n) \leqslant N+1$

In this case we aim to prove the property $gcd(t^m-1,t^n-1)=t^{gcd(m,n)}-1$.

Step 1 is trivial in this case, so we address step 2.

Clearly the property holds for $m=n$, so we consider the case $m<n$ (the reverse follows by symmetry).

As $m<n$ we can say with certainty that: $$max(m,n-m)<max(m,n)$$

Therefore we can prove step 2 by showing that if $P(m,n-m)$ is valid, then $P(m,n)$ must be too.

So we start by asserting that $P(m,n-m)$ is valid: $$gcd(t^m-1,t^{n-m}-1)=t^{gcd(m,n-m)}-1$$ We have already shown that $gcd(t^m-1, t^{n-m}-1)=gcd(t^m-1,t^n-1)$, so if the above holds it must also be true to say: $$gcd(t^m-1,t^n-1)=t^{gcd(m,n-m)}-1$$ Finally we know that $gcd(m,n-m)=gcd(m,n)$, so it must also be valid to say that: $$gcd(t^m-1,t^n-1)=t^{gcd(m,n)}-1$$ This states that $P(m,n)$ is valid; so we have shown that if $P(m,n-m)$ is valid, then $P(m,n)$ is too. Consequently we have proven step 2 and the proof is complete.