0

I would have thought this would have been on here somewhere.

Here I go.

Let $S$ be the set of positive integers $n$ which can be expressed in the form $n = pq + r$ where $ 0 \leq r < p.$ where $p$ is a positive integer and $q,r$ are natural numbers. We can fix $p\geq2$ for if $p = 1$ every integer is divisible by $1$ and we have $n = 1(q) + 0$ and so $S = \mathbb{N}$ trivially.

Now $ 1 \in S$ since $1 = p(0) + 1$ where we can choose a $p$ such that $0 \leq 1<p$.

Suppose that $n\in S \implies n=pq+r$ for some $p,q,r$ where $0 \leq r < p $

Now $n+1 = pq + r + 1 = pq + (r +1)$

If $(r +1) < p$ we are done, if that is not the case then $r + 1 = p$ we can not have $r + 1 > p$ for that would imply that $r \geq p$.

$r + 1 = p \implies r+ 1 - p = 0$

and so

$0 \leq r+ 1 - p < p$

This gives:

$n+1 = p(q+1) + (r + 1 - p) $ where $0 \leq r+ 1 - p < p$

and $(q+1)$ and $(r + 1 - p)$ are integers.

So $n+1 \in S$

Hence by the Induction principle $S = \mathbb{N}$

I have a feeling I have taken the long way. Could someone verify or dispute this 'proof' please.

  • There are various ways of proving this, but they depend on the assumptions you are allowed to make. You can fix $p$. For $p=2$ the statement just tells you that every positive integer is even $(r=0)$ or odd $(r=1)$. But have you yet defined odd and even numbers? – Mark Bennet Aug 11 '15 at 19:31
  • Yes they have been defined. Am i wrong in using some general p? as oppose to fixing it for a given value like 2 or 3? –  Aug 11 '15 at 19:44
  • The point is that for fixed $p$ this is just the division algorithm. It works for all fixed $p$ and is a very important property of the integers (it works for polynomials too with appropriate modifications). It is unclear from your question quite what it is you are trying to achieve. – Mark Bennet Aug 11 '15 at 19:49
  • He is trying to prove that the division algorithm gives a result in that form for every pair of n and p. – YoTengoUnLCD Aug 11 '15 at 20:43

1 Answers1

0

I think quantifiers would be helpful when setting up the statement of this proof. I am assuming from reading through the proof that what we want is $\forall n, p \in \mathbb{N}, \exists q, r \in \mathbb{N}_0, r < p \wedge n = pq + r$. This is ugly, but it's rigorous. It says for all numbers $n, p$, there exists a $q$ and an $r < p$ such that $n$ can be expressed as $pq + r$. Also in the statement $\mathbb{N}_0$ refers to the "version" of the natural numbers starting at $0$. This statement is true, and the proof given in the question is a correct proof of this statement.

Colm Bhandal
  • 4,649