5
$\begingroup$

In the book Elementary Number Theory: Primes, Congruences and Secrets written by William Stein, which can be found at http://wstein.org/ent/, Stein proves the following at page 6/lemma 1.1.17:

Lemma $\ $ For any integers $a, b, n,$ we have $\, \gcd(an, bn) = |n|\gcd(a, b)$

Proof $\ $ We step through Euclid's algorithm for $\gcd(an, bn)$ and note that at every step the equation is the equation from Euclid's algorithm for $\gcd(a, b)$ but multiplied through by $n.$ For simplicity, assume that both $a$ and $b$ are positive. We will prove the lemma by induction on $a + b$. The statement is true in the base case when $a + b \le 2$, since then $a = b = 1$. Now assume $a, b$ are arbitrary with $a \ge b$. Let $q$ and $r$ be such that $a = bq + r$ and $0 \le r < b$. Then by Lemmas 1.1.9-1.1.10, we have $\gcd(a, b) = \gcd(b, r)$. Multiplying $a = bq + r$ by $n$ we see that $an = bnq + rn$, so $\gcd(an, bn) = \gcd(bn, rn)$. Then

$$b + r = b + (a - bq) = a - b(q - 1) \le a < a + b,$$

so by induction $\gcd(bn, rn) = |n|\gcd(b, r)$. Since $\gcd(b, r) = \gcd(a, b)$, this proves the lemma.

My main question concerning this proof is that i have troubles following how $b + r < a + b$ leads to the fact that $\gcd(bn, rn) = |n| \gcd(b, r).$

I think that my troubles comprehending this proof is related to my basic understanding of mathematical induction, I never even knew what it was before stumbling upon this proof. My current understanding of induction is that you prove your statement for a base case, $a + b = 2,$ then you prove that if the statement is true for any one natural number then it is true for the next. However i do not understand how that principle is used in this proof, any explanation is greatly appriciated.

$\endgroup$
  • $\begingroup$ The induction is on $\,a+b,\,$ i.e. we are assuming it holds true for all $\,a_1,b_1\,$ such that $\,a_1+b_1 < a+b.\ $ You can think of $\,a+b\,$ as a measure of the "size" of the arguments of $\,\gcd(a,b),\,$ so the induction is on this integer size. $\endgroup$ – Bill Dubuque Jan 11 '17 at 18:26
  • $\begingroup$ For a similar (but simpler) proof see the last proof in this answer. It uses the simpler subtractive (vs, remainder / mod) form of the Euclidean algorithm for the descent, Also in that answer are a few other proofs of this GCD Distributive Law, which may lend further insight $\endgroup$ – Bill Dubuque Jan 11 '17 at 18:47
1
$\begingroup$

You are correct that mathematical induction consists of three steps:

  1. Prove the base case.
  2. Assume that the claim is true for some $n\in\Bbb N$ (possibly including $0$ if needed).
  3. 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).

  1. Prove the base case.
  2. Fix some $n\in\Bbb N$ and assume that the claim is true for all natural numbers $k$ when $k< n$.
  3. 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.

$\endgroup$
  • $\begingroup$ @ellac, I'm glad it was of help. If there is anything you'd like me to elaborate on, feel free to ask. $\endgroup$ – Ennar Jan 11 '17 at 21:13
  • $\begingroup$ Perfect explanation, Just if following is correct. $a + b = m = 3$ is proven since this holds true: $\gcd(na', nb') = |n|\gcd(a', b'), (\foralla', b' \in\Bbn) a' + b' < m$ $\endgroup$ – user406084 Jan 11 '17 at 21:14
  • $\begingroup$ @ellac, we proved the base case $m=2$. Now, for $m=3$, we have that the claim is true for $2<3$, thus for $3$ as well, by step 3 in induction. For $m=4$, we now have that the claim is true for $2,3<4$, and thus for $4$ as well, by step 3 and so on and so on. Is this what you wanted to confirm? $\endgroup$ – Ennar Jan 11 '17 at 21:17
  • $\begingroup$ Accidentally posted comments without being done typing. However you managed to respond to the intended comment anyway, thank you. What i meant to type: Perfect explanation, Just wondering if following is correct. Lemma is true $a + b = m = 3$ since this holds true: $\gcd(na', nb') = |n|\gcd(a', b'), (\forall a', b' \in\Bbb N) a' + b' < m$ there is only 1 combination where $a' + b' < m$ which is when $a' = b' = 1$ which is true. This can be applied multiple times and will thus prove the lemma. $\endgroup$ – user406084 Jan 11 '17 at 21:22
  • $\begingroup$ You are welcome. This is how induction works in general and you would do well to try solving some exercises on your own, until you are completely comfortable with this kind of reasoning. Induction is one of the most used tools in mathematics. Feel free to give this answer an upvote, or mark it as accepted answer. @ellac $\endgroup$ – Ennar Jan 11 '17 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy