Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The proof given for the statement

$$\exists \: q, \, r \in \mathbb{N} \; (n = q \times m + r \wedge r < m)$$

looks like:

  1. Let $n \in \mathbb{N}$, $m \in \mathbb{N}^+$
  2. Let $S = \{ s \in \mathbb{N} \; | \; \exists q \in \mathbb{N} \; (s = n - (q \times m)) \}$
  3. We prove $S$ contains at least 1 natural number

    1. We know $n = n - (0 \times m)$
    2. Therefore $n \in S$
    3. Therefore $S$ is not empty
  4. We prove $S$ contains a smallest element

    1. We know $S \subset \mathbb{N}$
    2. We know $S$ is not empty (from 3)
    3. Therefore $S$ contains a smallest element as $\mathbb{N}$ well ordered
  5. Let $r$ be the smallest element in $S$

  6. We know $\exists q \in \mathbb{N} \; (r = n - (q \times m))$ by dfn. of $S$
  7. Therefore $n = (q \times m) + r$
  8. We prove $r < m$

    1. Lets assume $r \ge m$

      1. $n - (q \times m) \ge m$
      2. $n - (q \times m) -m \ge 0$
      3. $n - ((q + 1) \times m) \ge 0$
      4. $n - ((q+1) \times m) \in S$
      5. $n - ((q+1) \times m) = r - m$
      6. $n - ((q+1) \times m) < r$ (becos $m \in \mathbb{N}^+$)
      7. $r$ is not the smallest element (contradiction)
    2. $r < m$

A few questions

  • Is $S$ the set of possible remainders? If so, how can the divined ($n$) be in the set of possible remainders?
  • Why might $r$ be the smallest element in $S$?
  • Can someone explain the rationale behind steps 8.1.2 - 8.1.5?
share|cite|improve this question
Why is this so complicated? Suppose $n=qm+r$ and $r\geq q$. Redefine $r \rightarrow r-q$ and $m \rightarrow m+1$. Repeat until $r<q$. – Douglas B. Staple Apr 10 '13 at 13:36
up vote 1 down vote accepted

Hint $\,\ $ The idea is this: $ $ the least natural $\rm\: r\in \bar S = n\!-\!m\,\Bbb N\ $ satisfies $\rm\ r < m,\ $ since otherwise $\rm\:r\ge m\ $ so $\rm\ r\!-\!m\ge 0 \:$ is a smaller natural in $\rm\,\bar S,\:$ by $\rm\:r = n\!-\!mq\:$ $\Rightarrow$ $\rm\:r\!-\!m = n\!-\!m(q\!+\!1)\in\bar S.$

Said dynamically: if you repeatedly subtract $\rm\:m\:$ from $\rm\:n\:$ you eventually reach an $\rm\, r\in [0,m\!-\!1].$

share|cite|improve this answer

In a loose sense $S$ is the set of possible remainders: it’s the set of amounts by which $n$ differs from a multiple of $m$. That is, you look at all possible multiples $qm$ of $m$ (for $q\in\Bbb N$) and see how much $n$ differs from each of them; those differences are the members of $S$. As a result $S$ contains the non-negative numbers in the following list:

$$\begin{align*} &n-0\cdot m=n\;,\\ &n-1\cdot m=n-m\;,\\ &n-2\cdot m=n-2m\;,\\ &n-3\cdot m=n-3m\;,\\ &\qquad\qquad\;\,\vdots \end{align*}\tag{1}$$

Remember, we’re looking for natural numbers $q$ and $r$ such that $n=qm+r$, which means that $r=n-qm$; thus, if such $q$ and $r$ exist, the remainder $r$ must be one of the numbers in the list $(1)$. We also want $r$ to be non-negative, so $r$ will actually be in $S$ and not just in the list $(1)$.

We know that $n\in\Bbb N$, so we know that the list $(1)$ does have at least one non-negative member, and therefore $S\ne\varnothing$. You ask how $n$ can be a candidate for the remainder: what if $m>n$? What if, for instance, $m=5$ and $n=3$? Then dividing $n$ by $m$ yields a quotient $q=0$ and a remainder $r=n=3$: $3=0\cdot 5+3$.

Why might $r$ be the smallest element of $S$?

I’m not sure what you’re asking here. In the proof we simply let $r$ be the smallest element of $S$ and then prove that this number has the desired properties. Are you asking why we might think of trying this value of $r$? We already know that the remainder has to be in $S$, and we also know that it has to be less than $m$, so we want it to be small rather than large; it makes sense, therefore, to try the smallest member of $S$ to see whether it does the job.

The argument in step 8 is by contradiction: we suppose that $r\ge m$ and derive a contradiction, so that we can conclude that $r<m$, just as we want. Recall that $r$ is the smallest member of $S$ and that $q$ has been chosen so that $n=qm+r$. Thus, $n-qm=r$, and since we’ve assumed that $r\ge m$, this implies that $n-qm\ge m$. Subtract $m$ from both sides of the inequality to get $n-qm-m\ge 0$, and then combine the two $m$ terms to get $n-(q+1)m\ge 0$. Now $q\in\Bbb N$, so $q+1\in\Bbb N$, and therefore $n-(q+1)m$ is one of the numbers in the list $(1)$. For convenience let $s=n-(q+1)m$; as we just saw, $s$ is in the list $(1)$. Moreover, we just showed that $s\ge 0$, so $s$ is actually in $S$. (Recall that $S$ is the set of non-negative members of the list $(1)$.)

But if you look back at the algebra that we just did, you can see that $$s=n-(q+1)m=(n-qm)-m=r-m\;.$$ Now recall that by hypothesis $m\in\Bbb N^+$, so $m>0$, and therefore $s=r-m<r$. In other words, $s$ is a member of $S$ that’s smaller than $r$, contradicting our choice of $r$ as the smallest member of $S$. This contradiction shows that $r$ cannot be greater than or equal to $m$ and hence that $r<m$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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