7
$\begingroup$

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<q$, $r+1 \leq q$ that is $r+1 = q$ or $r+1 <q$.
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 <q$ 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.

$\endgroup$
7
  • 1
    $\begingroup$ What do you denote $r$++ and $n$++? $\endgroup$
    – Bernard
    Commented Nov 15, 2019 at 21:56
  • 1
    $\begingroup$ Why write it in such a cryptic way? $\endgroup$
    – Bernard
    Commented Nov 15, 2019 at 22:05
  • 1
    $\begingroup$ @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 $\endgroup$
    – Herb
    Commented Nov 15, 2019 at 22:09
  • 2
    $\begingroup$ Your proof is correct. $\endgroup$
    – conditionalMethod
    Commented Nov 15, 2019 at 22:20
  • 2
    $\begingroup$ 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 $++$. $\endgroup$
    – Lee Mosher
    Commented Nov 15, 2019 at 22:37

1 Answer 1

Reset to default
4
$\begingroup$

The proof as it stands in the current form of your post is correct and well-written. Exceptions:

  • It is recommended to put the induction base and the induction step in their own paragraphs.

  • It is also good style to have any two formulas separated by a word (so replace "Since $r<q$, $r+1\leq q$" by "Since $r<q$, 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .