# Math Help - Well Ordering Principle

1. ## Well Ordering Principle

I need help for the question below, i simply do not know where to start.

In the proof of the quotient remainder theorem, we have "if n>=0 and 0<d<=n, then there is a largest integer q such that qd<=n". Use the well ordering principle to justify the existence of q. (Consider the set S={i element of Natural numbers: id<=n}).

2. Originally Posted by shaoen01
In the proof of the quotient remainder theorem, we have "if n>=0 and 0<d<=n, then there is a largest integer q such that qd<=n". Use the well ordering principle to justify the existence of q. (Consider the set S={i element of Natural numbers: id<=n}).
We know that 1 belongs to S, so S is not empty.
We also know that $\exists J \in N\left[ {n < J} \right]$ so J does not belong to S.
If $T = N\backslash S$ then $J \in T$; thus T is not empty.
By well ordering, there is a first element, t, in T.
Now t-1 is not in T so t-1 belongs to S.
Can you complete the proof?

3. Originally Posted by shaoen01
I need help for the question below, i simply do not know where to start.

In the proof of the quotient remainder theorem, we have "if n>=0 and 0<d<=n, then there is a largest integer q such that qd<=n". Use the well ordering principle to justify the existence of q. (Consider the set S={i element of Natural numbers: id<=n}).
Given $a,b\in \mathbb{Z}$ with $b>0$ we want to show there exists $q,r$ so that $a = qb+r$ where $0\leq r < b$. Define the set $\{ a - sb \geq 0 | s\in \mathbb{Z} \}$. This set is non-empty (why?) and so by Well-Order it means there is a $r$ that is the least element. Thus, $a - qb = r$ for some $q$. We will show $0\leq r < b$, because if not then $r = b+r'$ where $r' < r$. And then $a - qb = b + r' \implies a - (q+1)b = r'$ which is impossible since $r$ is the least element and $r' < r$.

4. Hi,

But i didn't quite understand what you mean by "
$
T = N\backslash S
$
".

Thanks

Originally Posted by Plato
We know that 1 belongs to S, so S is not empty.
We also know that $\exists J \in N\left[ {n < J} \right]$ so J does not belong to S.
If $T = N\backslash S$ then $J \in T$; thus T is not empty.
By well ordering, there is a first element, t, in T.
Now t-1 is not in T so t-1 belongs to S.
Can you complete the proof?

5. Hi,

I understand your explanation but when it comes down to trying to do it by myself i am always lost. Do you have any tips or certain methods to determine how to do this? Thanks

Originally Posted by ThePerfectHacker
Given $a,b\in \mathbb{Z}$ with $b>0$ we want to show there exists $q,r$ so that $a = qb+r$ where $0\leq r < b$. Define the set $\{ a - sb \geq 0 | s\in \mathbb{Z} \}$. This set is non-empty (why?) and so by Well-Order it means there is a $r$ that is the least element. Thus, $a - qb = r$ for some $q$. We will show $0\leq r < b$, because if not then $r = b+r'$ where $r' < r$. And then $a - qb = b + r' \implies a - (q+1)b = r'$ which is impossible since $r$ is the least element and $r' < r$.