Proof by induction of the Euclide formula

Question

I would like to know if the solution I found for this exercise is correct (Terence Tao, Analysis 1)

$\boldsymbol{Proposition}$

Let n be a natural number, and let $q$ be a positive number. Then there exist natural numbers $m$, $r$ such that $ 0\leq r<q$ and $n = mq + r$. (Hint: fix q and induct on n)

$\boldsymbol{Proof}:$

$\boldsymbol{Base} $ $\boldsymbol{ case}$ : $ n=1$

We have $n=1 =(1+0)\cdot 1=1\cdot1 +0= m\cdot q+ r$

and so the base case results true, since $0=r<q=1$, $m=1$ (they are all natural numbers and $q$ is positive)

$\boldsymbol{Inductive} $ $\boldsymbol{step}$

Let we assume it holds for $n$, hence $n =(n+0)\cdot 1=n\cdot1 +0= m\cdot q+ r$ with $m=n$, $q=1$ and $r=0$

$\boldsymbol{(n+1)} $ $\boldsymbol{step}$

$n+1 =((n+1)+0)\cdot 1=(n+1)\cdot1 +0= m\cdot q+ r$

We have $m=n+1$, which is again a natural number by the inductive hypothesis (if $n$ is natural then also $n+1$ is natural by definition); $q=1$ positive and $r=0$ (of course, all natural numbers).

Hence the proof is concluded.

Thanks in advance.

Answer 1

You have proven that if $q = 1$ then $n = n*1 + 0$ which is trivial.

You can not assume $q = 1$. You have to prove that if you are given a $q$ that no matter what the $q$ is, so long as it is a positive integer you can find $m,r$ so that the statement is true.

So numbers involve:

$q$. You have no choice in this. It is given to you by God, the Devil, or your professor (whichever one you fear the most). But you do know $q \ge 1$ and $q$ is a natural number.

$m,r$ you can choose these based on what $q$ is and what $n$ is.

$n$ you have to prove this is possible for all natural numbers (including $0$) and you must prove it for every one. SO you start with $n =0$ and then you show that if it is true for one specific $n$ then it will be true for $n+1$. Thus you can through all the natural numbers and know it is true for all. (It's true for $0$. SO it is true for $1$. Which means it is true for $2$. Which means it is true for $3$. Which means .....)

So

Base case: $n = 0$. We have no idea what $q$ is but we want to show we can find $m,r; 0\le r < q$ so that $0 = mq + r$.

Well, that's easy. If $m = 0$ and $r= 0$ we have $0 = 0*q + r$. That was easy.

Induction step: Assume we know that $n = mq +r$ for some $m$ and $r$ and $0\le r < q$.

Can we find $m', r'; 0\le r' < q$ so that $n + 1 = m'q + r'$?

Well if $n = mq + r$ then

$n+1 = ????????$

$n +1 = mq + (r + 1)$.

What does that mean? Keep reading:

If $r + 1 < q$ (or in other words if $r < q-1$) we are done. Just let $m' = m$ and $r' = r+1$.

But what if $r = q-1$? What do we do then?

Well $n + 1 = mq + (r + 1) = mq + q = (m+1)q = (m+1)q + 0$.

Then we let $m' = m+1$ and $r = 0$ and we are done:

To recap:

If $n= mq + r; r< q$ then if $r < q-1$ then $n+1 = mq + (r + 1)$ and the result is true. If $r = q-1$ then $n+1 = (m+1)q + 0$ and the result is true.

So by induction we can find such $m$ and $r$ for any $n$ given the $q$ we were forced to use.