# Euclidean Algorithm proof exercise Terence Tao "Analysis I"

I'm self-studying Analysis from Terence Tao's "Analysis I" and one of the exercises given is prove the following proposition

Proposition 2.3.9 (Euclidean Algorithm). Let $$n$$ be a natural number and let $$q$$ be a positive natural number. Then there exist natural numbers $$m$$, $$r$$ such that $$0 \leq r < q$$ and $$n = mq + r$$.

I'm fairly new to proving so I initially got stuck so I looked at the hint which was to fix $$q$$ and induct on $$n$$. And now I currently have the following:

Proof.

We fix $$q$$ and use induction on $$n$$. We first prove the base case $$n=0$$. If we set $$m=0$$ and $$r=0$$ then we have $$n = 0 \cdot q + 0 = 0$$ but $$0 \leq 0 < q$$, so we are done with the base case.

Now suppose inductively that $$n = m \cdot q + r$$ for some natural numbers $$m$$, $$r$$ such that $$0 \leq r < q$$ and $$n = mq + r$$. We wish to show that there exist natural numbers $$m'$$ and $$r'$$ such that $$n+1= m' \cdot q + r'$$ where $$0\leq r'< q$$.

From the inductive hypothesis we have $$n+1 = mq + (r+1)$$.
Since $$r, $$r+1 \leq q$$ that is $$r+1 = q$$ or $$r+1 .
If $$r+1 = q$$, we set $$m' = m+1$$ and $$r'=0$$ then $$m' \cdot q + r' = (m+1) \cdot q + 0$$ but $$n+1 =(m+1) \cdot q + 0$$, so $$n+1 = m' \cdot q + r'$$ and $$0\leq r'< q$$.
If however $$r+1 then we set $$m' = m$$ and $$r' = r+1$$ then we have that $$n+1 = m' \cdot q + r'$$ and $$0\leq r'< q$$.

This completes the induction. $$\tag*{\Box}$$

I'd be grateful for any corrections or suggestions for improvement.

• What do you denote $r$++ and $n$++? Commented Nov 15, 2019 at 21:56
• Why write it in such a cryptic way? Commented Nov 15, 2019 at 22:05
• @Bernard Hmm I'm not sure. I just followed how the textbook denoted it in the previous section. It would probably be clearer if changed it. I'll make the edit
– Herb
Commented Nov 15, 2019 at 22:09
• Your proof is correct. Commented Nov 15, 2019 at 22:20
• Before the edit, he was just following Tao's notation in his analysis book. And it's not original with Tao, Peano's Axioms are generally stated with an "increment" operator before addition is ever introduced. Tao is working from Peano's axioms, and seems to be just borrowing the modern computer increment operator $++$. Commented Nov 15, 2019 at 22:37

• It is also good style to have any two formulas separated by a word (so replace "Since $$r, $$r+1\leq q$$" by "Since $$r, we have $$r+1\leq q$$").
• Moreover, I would switch the meanings of the letters $$m$$ and $$q$$, since $$q$$ usually denotes the quotient, which however is what $$m$$ stands for in your argument. Alas, this nonstandard choice of notation originates in the book itself.