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?


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].

  • $\begingroup$ 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. $\endgroup$ – Tengu Apr 26 '13 at 1:45
  • 1
    $\begingroup$ 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". $\endgroup$ – Henry Swanson Apr 26 '13 at 1:48
  • $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Apr 26 '13 at 1:48
  • $\begingroup$ Thank you for your reply. I think I kind of understood why we need that. $\endgroup$ – Tengu Apr 27 '13 at 1:34

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.