2

I was reading "Number Theory" by George E. Andrews.

On P.17, where he proves that for each pair of positive integers a,b, gcd(a,b) uniquely exists, I came up with a question.

The approach he used is probably the most common one, that is, to make use of Euclidean Algorithm.

There exist integers $q_o, r_o $ ,$0 \leq r_0 <b$. such that

$a=q_0 \times b +r_0$.

If $r_0 \neq 0$, we can find $q_1,r_1$, $0 \leq r_1 < r_0$ such that

$b=q_1 \times r_0 + r_1$.

Since $b>r_0>r_1>....\geq 0$, there exists $k$ such that $r_k=0$.

Then we can prove that $d=r_{k-1}$ divides $r_{k-2}$.

Moreover, we can divide every $r_t$ by $d$.

I believe this is proved as following;

Suppose that $d$ divides both $r_t, r_{t-1}$.

Since $r_{t-2}=q_t \times r_{t-1} + r_t$ and the right side is clearly divisible by $d$, so is the left side. And suppose that $d$ divides both $r_{t-1},r_{t-2}$. And keep going and going till we have $d$ divides both $a,b$

And the author says that this procedure requires the Principle of Mathematical Induction.

This looks like a Mathematical Induction but this is not proving for infinitely many numbers,so I think this does not need Principle of Mathematical Induction because k is a finite number.

To my understanding, we need to use the Principle of mathematical Induction only when we want to prove that a statement is true for infinitely many integers, because we cannot write infinitely long proofs. However, in this situation, we could write the proof of k steps but it was just troublesome. That is why I think it does not need Mathematical Induction

Could you help me figure out why we need to use Principle of Mathematical Induction in this situation?

Tengu
  • 1,078

2 Answers2

3

For any given value of $k$ you can prove the theorem without induction, though it would be tedious. However, to prove the theorem for all values of $k$ does require induction. What you don't need is the axiom of infinity. That is, it's possible to prove the theorem for all natural numbers without assuming that there is such a thing as a set of all natural numbers.

dfeuer
  • 9,069
2

Here are the spots where induction is required:

"Since $b>r_0>r_1>....≥0$, there exists $k$ such that $r_k=0$." Not true for real numbers, right?

"I think this does not need Principle of Mathematical Induction because k is a finite number." But how do we know it's finite? You could descend forever in some rings.

Personally though, I'd use the well-ordering principle, it's much cleaner than induction in most cases.

Let $S$ be the set of those $r_i$. It's fine if it's infinite, sets can do that. Now, since we know all of them are $\ge 0$, there is a minimum element. Call this element $d$. [continue as you did in your post].

Henry Swanson
  • 12,972
  • Thank you for your reply. For the first one, that is not true for real numbers, but we assume that $r_t$ are all integers. And $k$ is a finite number because $k<b$ and $b$ is a given integer. – Tengu Apr 26 '13 at 01:45
  • 1
    Yes, they're all integers. But what is the property that makes the integers different than real numbers? You need a justification other than "yeah, integers can't do that". – Henry Swanson Apr 26 '13 at 01:48
  • The key use of induction is after this one, where step by step one shows that $d$ divides $r_i$ for all $i\le k$. Once you reach this stage, $k$ is an integer, so that's not the issue. That induction is needed here is more subtle. – Andrés E. Caicedo Apr 26 '13 at 01:48
  • Thank you for your reply. I think I kind of understood why we need that. – Tengu Apr 27 '13 at 01:34