Euclid's Divison Lemma and Mathematical Logic

Question

While I was trying to prove Euclid's Divison algorithm, I came across a certain problem. Let me share the proof and the problem.

Lemma : Let $ a , b \in \mathbb{N} , a > b $ then there exists $q , r$ , $ a = bq + r , 0 \leq r < b$

Proof : Let $S$ = {$a - bq : a - bq > 0 , a - bq \in \mathbb{N}$} , Since , it is a subset of the natural numbers then there exists a least element (Well Ordering Principle) . Let that be $ r \Rightarrow a - bq = r $ . If $r \geq b $ then $ r - b \geq 0 \Rightarrow a - bq - b = a - b(q + 1) \geq 0$ (I am assuming that $\mathbb{N}$ contains $0$) So it is a contradiction. Now, my doubt is why not the "assumption that the symbol $r$ leads to the contradiction rather than the assumption that $ b \leq r $? (Since we made two assumptions either one of them must be wrong because they are contradicting each other). This question may seem very strange, but I think that this question may lead to a more rigorous understanding of proofs.

Euclid's Divison Algorithm

Theorem: The process: $\\ $

$ a = bq_1 + r_1 , 0 \leq r_1 < b$ $\\ $

$ b = r_1q_2 + r_2 , $ $ 0 \leq r_2 < r_1 $

$ r_1 = r_2q_3 + r_3 $ $0 \leq r_3 < r_2 $

and so on, must terminate and the last remainder will be the gcd of $a, b$

Proof :

We again see that $r_1 > r_2 > r_3 > .. $ This process must terminate due to the well-ordering principle.

Let the process terminate here :

$ r_{n+1} - r_{n+2}q_{n+3} = t$ , if $t \geq 1 $ then we have to do another step which is a contradiction to our assumption that it will terminate here $ r_{n+1} - r_{n+2}q_{n+3} = t$ $\Rightarrow t < 1 \Rightarrow t = 0$. So my question is : Why not the assumption that it will terminate here $ r_{n+1} - r_{n+2}q_{n+3} = t$ was false rather than the assumption that if $ t \geq 1 $ this was false. The gcd part can easily be done from here. I was trying to prove my questions by the way of contradiction but didn't make any progress except going in a loop. And I felt like the previous question is like why when we take a random triangle and prove a geometric fact about it the proof holds good? The reason I read in a book called "proofs" was that we are taking general facts and proving it on a special case which doesn't affect the proof. I hope I have made my question clear if not please post your questions and I'll answer them.

Answer 1

It seems you're asking two related, but slightly different questions, so I will separate my answers.

Can a definition "assumption" lead to a contradiction?

why not the "assumption that the symbol r leads to the contradiction rather than the assumption that $b\le r$?

This question may seem strange from the perspective of someone very used to normal mathematical proofs, but I think it's a fair question.

I claim that "let $r=a-bq$", or any other definition of a symbol/shorthand like that, can't lead to a contradiction on its own. Let's say we have a proof like "…Let $r=a-bq$.…This is a contradiction." Then we can delete the sentence "Let $r=a-bq$." and replace every other instance of $r$ with $(a-bq)$. Since $r=a-bq$, this won't change any of the other lines in a meaningful way, and we'll still have a contradiction at the end. Since the contradiction exists even without the "Let $r=a-bq$." part, that couldn't have led to the contradiction.

---

What's going on with the termination assumption?

Why not the assumption that it will terminate here $r_{n+1}-r_{n+2}q_{n+3}=t$

Here, it may not be obvious what the proof is doing/trying to express. If the proof says "Let the process terminate here: $r_{n+1}-r_{n+2}q_{n+3}=t$.", that's shorthand for something like "let $n$ and $t$ be the numbers where the termination step (that you already know must exist) is '$r_{n+1}-r_{n+2}q_{n+3}=t$'." Since this is just defining variables $n$ and $t$, then just like the question I addressed above, it can't lead to any contradictions on its own.

Answer 2

You best do it by induction on $b$.

If $b=0$, then the algorithm doesn't even start, so it obviously terminates.

Suppose now $b>0$ and that the algorithm terminates for every number less than $b$.

By Euclidean division, we can write $a=bq+r$, with $0\le r<b$. By the induction hypothesis, the algorithm applied to $(b,r)$ terminates. Therefore also the algorithm applied to $(a,b)$ terminates, precisely with one more step than the one for $(b,r)$.

---

Alternative proof, by contradiction. Suppose there are pairs $(a,b)$ such that the algorithm doesn't terminate. Among them choose a pair with minimal $b$. Then do Euclidean division $a=bq+r$ and note you get a contradiction, because the algorithm applied to $(b,r)$ cannot terminate, but $r<b$.

---

Some way or another, induction has to be used. In the second proof I used the fact that every nonempty set of natural numbers has a minimum, which is equivalent to the induction principle (when we're in the framework of set theory).