Mixing
Proving the Division Algorithm using induction
$begingroup$
Let $n in mathbb{N}$. For every $m in mathbb{Z}$, there exist unique $q, r in mathbb{Z}$ such that $ m = qn+r$ and $0 le r le n-1$. We call $q$ the quotient and $r$ the remainder when dividing into $m$.
I'm having trouble proving this with induction. I believe the idea is to first prove for all $m in mathbb{Z} _{ge 0}$ by induction, then prove for all $m in mathbb{Z}$ but $m notin mathbb{Z} _{ge 0}$ using the induction proof on $-m$, since $-m in mathbb{N}$.
I'd appreciate any help, thank you.
proof-writing
asked Apr 2 '14 at 14:37
user135340user135340
4214
$endgroup$
add a comment |
$begingroup$
Let $n in mathbb{N}$. For every $m in mathbb{Z}$, there exist unique $q, r in mathbb{Z}$ such that $ m = qn+r$ and $0 le r le n-1$. We call $q$ the quotient and $r$ the remainder when dividing into $m$.
I'm having trouble proving this with induction. I believe the idea is to first prove for all $m in mathbb{Z} _{ge 0}$ by induction, then prove for all $m in mathbb{Z}$ but $m notin mathbb{Z} _{ge 0}$ using the induction proof on $-m$, since $-m in mathbb{N}$.
I'd appreciate any help, thank you.
proof-writing
asked Apr 2 '14 at 14:37
user135340user135340
4214
$endgroup$
add a comment |
$begingroup$
Let $n in mathbb{N}$. For every $m in mathbb{Z}$, there exist unique $q, r in mathbb{Z}$ such that $ m = qn+r$ and $0 le r le n-1$. We call $q$ the quotient and $r$ the remainder when dividing into $m$.
I'm having trouble proving this with induction. I believe the idea is to first prove for all $m in mathbb{Z} _{ge 0}$ by induction, then prove for all $m in mathbb{Z}$ but $m notin mathbb{Z} _{ge 0}$ using the induction proof on $-m$, since $-m in mathbb{N}$.
I'd appreciate any help, thank you.
proof-writing
asked Apr 2 '14 at 14:37
user135340user135340
4214
$endgroup$
Let $n in mathbb{N}$. For every $m in mathbb{Z}$, there exist unique $q, r in mathbb{Z}$ such that $ m = qn+r$ and $0 le r le n-1$. We call $q$ the quotient and $r$ the remainder when dividing into $m$.
I'm having trouble proving this with induction. I believe the idea is to first prove for all $m in mathbb{Z} _{ge 0}$ by induction, then prove for all $m in mathbb{Z}$ but $m notin mathbb{Z} _{ge 0}$ using the induction proof on $-m$, since $-m in mathbb{N}$.
I'd appreciate any help, thank you.
proof-writing
proof-writing
asked Apr 2 '14 at 14:37
user135340user135340
4214
asked Apr 2 '14 at 14:37
user135340user135340
4214
asked Apr 2 '14 at 14:37
user135340user135340
4214
asked Apr 2 '14 at 14:37
user135340user135340
4214
asked Apr 2 '14 at 14:37
user135340user135340
4214
4214
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
Uniqueness doesn't need induction. Suppose $m=qn+r=q'n+r'$, where $0le rle n-1$. It's not restrictive to assume $rle r'$, so we have $0le r'-rle n-1$; but $r'-r=n(q-q')$, so
$$
0le n(q-q')<n
$$
As $n>0$, this implies
$$
0le q-q'<1
$$
so $q=q'$ and therefore $r'=r$.
The proof of existence can be conveniently split into the cases $mge0$ and $m<0$.
The first case is done by induction. The case $m=0$ is obvious: take $q=0$ and $r=0$. Assume you know $m=qn+r$, with $0le r<n$; then
$$
m+1=qn+r+1
$$
If $r+1=n$, then $m+1=q(n+1)+0$, otherwise $r+1<n$ (using the hypothesis that $rle n-1$, so $r+1le n$) and the assert is true.
Now let's prove the case $m<0$. From the first case we get
$$
-m=qn+r
$$
with $0le r<n$. If $r=0$, then $m=(-q)n+0$ and we're done. Otherwise $0<r<n$ and
$$
m=(-q)n-r=(-q)n-n+n-r=(-q-1)n+(n-r)
$$
where $0<n-r<n$ and we're done.
answered Nov 8 '15 at 12:25
egregegreg
184k1486206
$endgroup$
add a comment |
$begingroup$
Theorem : If a,b$in$Z such that b>0 then
$exists$ unique q,r$in$ Z such that a=bq+r , 0≤r
Proof : Consider, S={ a-nb≥0 | n$in$ Z }
First thing to prove that S≠∅
It is clear that a-(-|a|)b ≥ 0
So a-(-|a|)b$in$S
Hence S≠∅
By WOP , there exists r=min(S)
So, r = a-qb for q$in$Z
Hence, a = bq+r
So Here Existence part completes here!!
Now we have to prove that r
Let's assume to the contrary that r≥b
So, r-b≥0
since r=a-qb
So a-qb-b≥0
a-(q+1)b≥0
So, r-b$in$ S
Since r-b
This contradicts the minimality of "r"
Hence r < b
This completes our proof !!!
I am sorry that I couldn't provide the uniqueness part of division algorithm
Hope it helps 😋😋
answered Jan 26 at 8:11
user629660user629660
123
$endgroup$
add a comment |
$begingroup$
Well lets take $m=1$
$$1=qn+r\$$
If $qn$ is negative $r$ would have to be greater than $n-1$ so that is out,if $qn$ is positive $q=1$ and $r=1-n$ and since $rgeq 0$,if $qn=0$,$r=1$ so it's unique now lets take
$$m=an+l\m+1=an+l+1$$
If $l+1=n$ then $m+1=(a+1)n+0$ which is unique since a is fixed(unique),otherwise since both $a$ and $l$ are fixed so are $an$ and $l+1$
answered Apr 2 '14 at 15:18
kingW3kingW3
11.1k72655
$endgroup$
add a comment |
$begingroup$
Base case, $m=0$:$$0=0n+0, 0le0<n.$$
For any other $q$, we have $qnle-nlor qnge n$, and as $r=-qn$, $rge nlor rle-n$, which is not allowed.
Induction, $mto m+1$:
$$m=qn+riff m+1=qn+r+1$$
if $0le r+1<n$, all conditions are met;
if $r+1=n$, take $q'=q+1,r'=0$ and $$m+1=q'n+r',0le r'<n.$$
answered Jun 28 '16 at 21:32
Yves DaoustYves Daoust
131k676229
$endgroup$
$begingroup$
In what does this differ from my answer?
$endgroup$
– egreg
Jun 28 '16 at 23:02
$begingroup$
In the sense that it's identical to the corresponding part.
$endgroup$
– egreg
Jun 28 '16 at 23:45
add a comment |
$begingroup$
(I). Let $P(s)$ denote a statement about s, which may or may not be true. The Principle of Induction :
If (i) $P(1)$ is true,
and if (ii) For all $sin mathbb N;(P(s)implies P(s+1),$
then (iii) $P(s)$ is true for all $sin mathbb N.$
Digression: If (ii) is true, it does not follow that $P(s)$ is true for any $s.$ For example if $P(s)$ is "$s<s$" then (ii) is true ( although (i) is false).
Equivalent to the Principle of Induction is the Well-Ordering Principle:
If $P(s)$ is true for some $sin mathbb N$ then there is a least $sin mathbb N$ for which $P(s)$ is true.
(II). By Induction we get the Archimedean property of $mathbb N:$ For any $x,y in mathbb N$ there exists $zin mathbb N$ such that $x< zy.$
Proof: Let $P(s)$ be " There exists $z$ with $s< yz"$. (So $P(s)$ is "$s$ is less than some multiple of $y$".) We have:
(i). $P(1)$ because $1<2y.$
(ii). $(P(s)implies P(s+1))$ for each $s,$ because if $s< yz$ then $$s+1< yz+1< yz+2y=y(z+2).$$ So by Induction, $P(s)$ holds for all $s.$ In particular $P(x)$ is true.
(III). So for $n,min mathbb N,$ there exists $zin mathbb N$ such that $m< zn.$ By the Well-Ordering Principle, let $q'$ be the least such $n.$ We have $(q'-1)nleq m<q'n.$ (This is immediate if $q'=1.$ If $q'>1$ then $q'>q-1in mathbb N,$ and then the def'n of $q'$ implies $(q'-1)nleq m.$)
Let $q=q'-1.$ So $qnleq m<(q+1)n.$ Let $r=m-qn.$ Then $$0=qn-qnleq m-qn=r<(q+1)n-qn=n.$$ And of course $m=qn+r.$
Now if $m=q_1n+r_1$ with for integers $q_1,r_1$ with $0leq r_1<n$ then $$0=m-m=(qn+r)-(q_1n+r_1)=(q-q_1)n+(r-r_1),$$ so $|r-r_1|=|(q-q_1)n|.$ This is impossible if $q_1ne q.$ Because (i). $q_1ne qimplies |(q-q_1)n|geq n,$ but (ii). $|r-r_1|<n$ because $$(0leq r<n land 0leq r_1<n)implies (;(r-r_1<n-0=n) land (r_1-r<n-0=n);).$$
Since $q_1=q$ we have $r_1=q_1n -m=qn-m=r.$
I will leave the case $mleq 0$ to you.
answered Dec 14 '16 at 23:43
DanielWainfleetDanielWainfleet
35.6k31648
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f736667%2fproving-the-division-algorithm-using-induction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Uniqueness doesn't need induction. Suppose $m=qn+r=q'n+r'$, where $0le rle n-1$. It's not restrictive to assume $rle r'$, so we have $0le r'-rle n-1$; but $r'-r=n(q-q')$, so
$$
0le n(q-q')<n
$$
As $n>0$, this implies
$$
0le q-q'<1
$$
so $q=q'$ and therefore $r'=r$.
The proof of existence can be conveniently split into the cases $mge0$ and $m<0$.
The first case is done by induction. The case $m=0$ is obvious: take $q=0$ and $r=0$. Assume you know $m=qn+r$, with $0le r<n$; then
$$
m+1=qn+r+1
$$
If $r+1=n$, then $m+1=q(n+1)+0$, otherwise $r+1<n$ (using the hypothesis that $rle n-1$, so $r+1le n$) and the assert is true.
Now let's prove the case $m<0$. From the first case we get
$$
-m=qn+r
$$
with $0le r<n$. If $r=0$, then $m=(-q)n+0$ and we're done. Otherwise $0<r<n$ and
$$
m=(-q)n-r=(-q)n-n+n-r=(-q-1)n+(n-r)
$$
where $0<n-r<n$ and we're done.
answered Nov 8 '15 at 12:25
egregegreg
184k1486206
$endgroup$
add a comment |
$begingroup$
Uniqueness doesn't need induction. Suppose $m=qn+r=q'n+r'$, where $0le rle n-1$. It's not restrictive to assume $rle r'$, so we have $0le r'-rle n-1$; but $r'-r=n(q-q')$, so
$$
0le n(q-q')<n
$$
As $n>0$, this implies
$$
0le q-q'<1
$$
so $q=q'$ and therefore $r'=r$.
The proof of existence can be conveniently split into the cases $mge0$ and $m<0$.
The first case is done by induction. The case $m=0$ is obvious: take $q=0$ and $r=0$. Assume you know $m=qn+r$, with $0le r<n$; then
$$
m+1=qn+r+1
$$
If $r+1=n$, then $m+1=q(n+1)+0$, otherwise $r+1<n$ (using the hypothesis that $rle n-1$, so $r+1le n$) and the assert is true.
Now let's prove the case $m<0$. From the first case we get
$$
-m=qn+r
$$
with $0le r<n$. If $r=0$, then $m=(-q)n+0$ and we're done. Otherwise $0<r<n$ and
$$
m=(-q)n-r=(-q)n-n+n-r=(-q-1)n+(n-r)
$$
where $0<n-r<n$ and we're done.
answered Nov 8 '15 at 12:25
egregegreg
184k1486206
$endgroup$
add a comment |
$begingroup$
Uniqueness doesn't need induction. Suppose $m=qn+r=q'n+r'$, where $0le rle n-1$. It's not restrictive to assume $rle r'$, so we have $0le r'-rle n-1$; but $r'-r=n(q-q')$, so
$$
0le n(q-q')<n
$$
As $n>0$, this implies
$$
0le q-q'<1
$$
so $q=q'$ and therefore $r'=r$.
The proof of existence can be conveniently split into the cases $mge0$ and $m<0$.
The first case is done by induction. The case $m=0$ is obvious: take $q=0$ and $r=0$. Assume you know $m=qn+r$, with $0le r<n$; then
$$
m+1=qn+r+1
$$
If $r+1=n$, then $m+1=q(n+1)+0$, otherwise $r+1<n$ (using the hypothesis that $rle n-1$, so $r+1le n$) and the assert is true.
Now let's prove the case $m<0$. From the first case we get
$$
-m=qn+r
$$
with $0le r<n$. If $r=0$, then $m=(-q)n+0$ and we're done. Otherwise $0<r<n$ and
$$
m=(-q)n-r=(-q)n-n+n-r=(-q-1)n+(n-r)
$$
where $0<n-r<n$ and we're done.
answered Nov 8 '15 at 12:25
egregegreg
184k1486206
$endgroup$
Uniqueness doesn't need induction. Suppose $m=qn+r=q'n+r'$, where $0le rle n-1$. It's not restrictive to assume $rle r'$, so we have $0le r'-rle n-1$; but $r'-r=n(q-q')$, so
$$
0le n(q-q')<n
$$
As $n>0$, this implies
$$
0le q-q'<1
$$
so $q=q'$ and therefore $r'=r$.
The proof of existence can be conveniently split into the cases $mge0$ and $m<0$.
The first case is done by induction. The case $m=0$ is obvious: take $q=0$ and $r=0$. Assume you know $m=qn+r$, with $0le r<n$; then
$$
m+1=qn+r+1
$$
If $r+1=n$, then $m+1=q(n+1)+0$, otherwise $r+1<n$ (using the hypothesis that $rle n-1$, so $r+1le n$) and the assert is true.
Now let's prove the case $m<0$. From the first case we get
$$
-m=qn+r
$$
with $0le r<n$. If $r=0$, then $m=(-q)n+0$ and we're done. Otherwise $0<r<n$ and
$$
m=(-q)n-r=(-q)n-n+n-r=(-q-1)n+(n-r)
$$
where $0<n-r<n$ and we're done.
answered Nov 8 '15 at 12:25
egregegreg
184k1486206
edited Jun 28 '16 at 21:00
answered Nov 8 '15 at 12:25
egregegreg
184k1486206
answered Nov 8 '15 at 12:25
egregegreg
184k1486206
answered Nov 8 '15 at 12:25
egregegreg
184k1486206
184k1486206
add a comment |
add a comment |
$begingroup$
Theorem : If a,b$in$Z such that b>0 then
$exists$ unique q,r$in$ Z such that a=bq+r , 0≤r
Proof : Consider, S={ a-nb≥0 | n$in$ Z }
First thing to prove that S≠∅
It is clear that a-(-|a|)b ≥ 0
So a-(-|a|)b$in$S
Hence S≠∅
By WOP , there exists r=min(S)
So, r = a-qb for q$in$Z
Hence, a = bq+r
So Here Existence part completes here!!
Now we have to prove that r
Let's assume to the contrary that r≥b
So, r-b≥0
since r=a-qb
So a-qb-b≥0
a-(q+1)b≥0
So, r-b$in$ S
Since r-b
This contradicts the minimality of "r"
Hence r < b
This completes our proof !!!
I am sorry that I couldn't provide the uniqueness part of division algorithm
Hope it helps 😋😋
answered Jan 26 at 8:11
user629660user629660
123
$endgroup$
add a comment |
$begingroup$
Theorem : If a,b$in$Z such that b>0 then
$exists$ unique q,r$in$ Z such that a=bq+r , 0≤r
Proof : Consider, S={ a-nb≥0 | n$in$ Z }
First thing to prove that S≠∅
It is clear that a-(-|a|)b ≥ 0
So a-(-|a|)b$in$S
Hence S≠∅
By WOP , there exists r=min(S)
So, r = a-qb for q$in$Z
Hence, a = bq+r
So Here Existence part completes here!!
Now we have to prove that r
Let's assume to the contrary that r≥b
So, r-b≥0
since r=a-qb
So a-qb-b≥0
a-(q+1)b≥0
So, r-b$in$ S
Since r-b
This contradicts the minimality of "r"
Hence r < b
This completes our proof !!!
I am sorry that I couldn't provide the uniqueness part of division algorithm
Hope it helps 😋😋
answered Jan 26 at 8:11
user629660user629660
123
$endgroup$
add a comment |
$begingroup$
Theorem : If a,b$in$Z such that b>0 then
$exists$ unique q,r$in$ Z such that a=bq+r , 0≤r
Proof : Consider, S={ a-nb≥0 | n$in$ Z }
First thing to prove that S≠∅
It is clear that a-(-|a|)b ≥ 0
So a-(-|a|)b$in$S
Hence S≠∅
By WOP , there exists r=min(S)
So, r = a-qb for q$in$Z
Hence, a = bq+r
So Here Existence part completes here!!
Now we have to prove that r
Let's assume to the contrary that r≥b
So, r-b≥0
since r=a-qb
So a-qb-b≥0
a-(q+1)b≥0
So, r-b$in$ S
Since r-b
This contradicts the minimality of "r"
Hence r < b
This completes our proof !!!
I am sorry that I couldn't provide the uniqueness part of division algorithm
Hope it helps 😋😋
answered Jan 26 at 8:11
user629660user629660
123
$endgroup$
Theorem : If a,b$in$Z such that b>0 then
$exists$ unique q,r$in$ Z such that a=bq+r , 0≤r
Proof : Consider, S={ a-nb≥0 | n$in$ Z }
First thing to prove that S≠∅
It is clear that a-(-|a|)b ≥ 0
So a-(-|a|)b$in$S
Hence S≠∅
By WOP , there exists r=min(S)
So, r = a-qb for q$in$Z
Hence, a = bq+r
So Here Existence part completes here!!
Now we have to prove that r
Let's assume to the contrary that r≥b
So, r-b≥0
since r=a-qb
So a-qb-b≥0
a-(q+1)b≥0
So, r-b$in$ S
Since r-b
This contradicts the minimality of "r"
Hence r < b
This completes our proof !!!
I am sorry that I couldn't provide the uniqueness part of division algorithm
Hope it helps 😋😋
answered Jan 26 at 8:11
user629660user629660
123
edited Jan 28 at 5:18
answered Jan 26 at 8:11
user629660user629660
123
answered Jan 26 at 8:11
user629660user629660
123
answered Jan 26 at 8:11
user629660user629660
123
123
add a comment |
add a comment |
$begingroup$
Well lets take $m=1$
$$1=qn+r\$$
If $qn$ is negative $r$ would have to be greater than $n-1$ so that is out,if $qn$ is positive $q=1$ and $r=1-n$ and since $rgeq 0$,if $qn=0$,$r=1$ so it's unique now lets take
$$m=an+l\m+1=an+l+1$$
If $l+1=n$ then $m+1=(a+1)n+0$ which is unique since a is fixed(unique),otherwise since both $a$ and $l$ are fixed so are $an$ and $l+1$
answered Apr 2 '14 at 15:18
kingW3kingW3
11.1k72655
$endgroup$
add a comment |
$begingroup$
Well lets take $m=1$
$$1=qn+r\$$
If $qn$ is negative $r$ would have to be greater than $n-1$ so that is out,if $qn$ is positive $q=1$ and $r=1-n$ and since $rgeq 0$,if $qn=0$,$r=1$ so it's unique now lets take
$$m=an+l\m+1=an+l+1$$
If $l+1=n$ then $m+1=(a+1)n+0$ which is unique since a is fixed(unique),otherwise since both $a$ and $l$ are fixed so are $an$ and $l+1$
answered Apr 2 '14 at 15:18
kingW3kingW3
11.1k72655
$endgroup$
add a comment |
$begingroup$
Well lets take $m=1$
$$1=qn+r\$$
If $qn$ is negative $r$ would have to be greater than $n-1$ so that is out,if $qn$ is positive $q=1$ and $r=1-n$ and since $rgeq 0$,if $qn=0$,$r=1$ so it's unique now lets take
$$m=an+l\m+1=an+l+1$$
If $l+1=n$ then $m+1=(a+1)n+0$ which is unique since a is fixed(unique),otherwise since both $a$ and $l$ are fixed so are $an$ and $l+1$
answered Apr 2 '14 at 15:18
kingW3kingW3
11.1k72655
$endgroup$
Well lets take $m=1$
$$1=qn+r\$$
If $qn$ is negative $r$ would have to be greater than $n-1$ so that is out,if $qn$ is positive $q=1$ and $r=1-n$ and since $rgeq 0$,if $qn=0$,$r=1$ so it's unique now lets take
$$m=an+l\m+1=an+l+1$$
If $l+1=n$ then $m+1=(a+1)n+0$ which is unique since a is fixed(unique),otherwise since both $a$ and $l$ are fixed so are $an$ and $l+1$
answered Apr 2 '14 at 15:18
kingW3kingW3
11.1k72655
answered Apr 2 '14 at 15:18
kingW3kingW3
11.1k72655
answered Apr 2 '14 at 15:18
kingW3kingW3
11.1k72655
answered Apr 2 '14 at 15:18
kingW3kingW3
11.1k72655
11.1k72655
add a comment |
add a comment |
$begingroup$
Base case, $m=0$:$$0=0n+0, 0le0<n.$$
For any other $q$, we have $qnle-nlor qnge n$, and as $r=-qn$, $rge nlor rle-n$, which is not allowed.
Induction, $mto m+1$:
$$m=qn+riff m+1=qn+r+1$$
if $0le r+1<n$, all conditions are met;
if $r+1=n$, take $q'=q+1,r'=0$ and $$m+1=q'n+r',0le r'<n.$$
answered Jun 28 '16 at 21:32
Yves DaoustYves Daoust
131k676229
$endgroup$
$begingroup$
In what does this differ from my answer?
$endgroup$
– egreg
Jun 28 '16 at 23:02
$begingroup$
In the sense that it's identical to the corresponding part.
$endgroup$
– egreg
Jun 28 '16 at 23:45
add a comment |
$begingroup$
Base case, $m=0$:$$0=0n+0, 0le0<n.$$
For any other $q$, we have $qnle-nlor qnge n$, and as $r=-qn$, $rge nlor rle-n$, which is not allowed.
Induction, $mto m+1$:
$$m=qn+riff m+1=qn+r+1$$
if $0le r+1<n$, all conditions are met;
if $r+1=n$, take $q'=q+1,r'=0$ and $$m+1=q'n+r',0le r'<n.$$
answered Jun 28 '16 at 21:32
Yves DaoustYves Daoust
131k676229
$endgroup$
$begingroup$
In what does this differ from my answer?
$endgroup$
– egreg
Jun 28 '16 at 23:02
$begingroup$
In the sense that it's identical to the corresponding part.
$endgroup$
– egreg
Jun 28 '16 at 23:45
add a comment |
$begingroup$
Base case, $m=0$:$$0=0n+0, 0le0<n.$$
For any other $q$, we have $qnle-nlor qnge n$, and as $r=-qn$, $rge nlor rle-n$, which is not allowed.
Induction, $mto m+1$:
$$m=qn+riff m+1=qn+r+1$$
if $0le r+1<n$, all conditions are met;
if $r+1=n$, take $q'=q+1,r'=0$ and $$m+1=q'n+r',0le r'<n.$$
answered Jun 28 '16 at 21:32
Yves DaoustYves Daoust
131k676229
$endgroup$
Base case, $m=0$:$$0=0n+0, 0le0<n.$$
For any other $q$, we have $qnle-nlor qnge n$, and as $r=-qn$, $rge nlor rle-n$, which is not allowed.
Induction, $mto m+1$:
$$m=qn+riff m+1=qn+r+1$$
if $0le r+1<n$, all conditions are met;
if $r+1=n$, take $q'=q+1,r'=0$ and $$m+1=q'n+r',0le r'<n.$$
answered Jun 28 '16 at 21:32
Yves DaoustYves Daoust
131k676229
edited Jun 28 '16 at 21:57
answered Jun 28 '16 at 21:32
Yves DaoustYves Daoust
131k676229
answered Jun 28 '16 at 21:32
Yves DaoustYves Daoust
131k676229
answered Jun 28 '16 at 21:32
Yves DaoustYves Daoust
131k676229
131k676229
$begingroup$
In what does this differ from my answer?
$endgroup$
– egreg
Jun 28 '16 at 23:02
$begingroup$
In the sense that it's identical to the corresponding part.
$endgroup$
– egreg
Jun 28 '16 at 23:45
add a comment |
$begingroup$
In what does this differ from my answer?
$endgroup$
– egreg
Jun 28 '16 at 23:02
$begingroup$
In the sense that it's identical to the corresponding part.
$endgroup$
– egreg
Jun 28 '16 at 23:45
$begingroup$
In what does this differ from my answer?
$endgroup$
– egreg
Jun 28 '16 at 23:02
$begingroup$
In what does this differ from my answer?
$endgroup$
– egreg
Jun 28 '16 at 23:02
$begingroup$
In the sense that it's identical to the corresponding part.
$endgroup$
– egreg
Jun 28 '16 at 23:45
$begingroup$
In the sense that it's identical to the corresponding part.
$endgroup$
– egreg
Jun 28 '16 at 23:45
add a comment |
$begingroup$
(I). Let $P(s)$ denote a statement about s, which may or may not be true. The Principle of Induction :
If (i) $P(1)$ is true,
and if (ii) For all $sin mathbb N;(P(s)implies P(s+1),$
then (iii) $P(s)$ is true for all $sin mathbb N.$
Digression: If (ii) is true, it does not follow that $P(s)$ is true for any $s.$ For example if $P(s)$ is "$s<s$" then (ii) is true ( although (i) is false).
Equivalent to the Principle of Induction is the Well-Ordering Principle:
If $P(s)$ is true for some $sin mathbb N$ then there is a least $sin mathbb N$ for which $P(s)$ is true.
(II). By Induction we get the Archimedean property of $mathbb N:$ For any $x,y in mathbb N$ there exists $zin mathbb N$ such that $x< zy.$
Proof: Let $P(s)$ be " There exists $z$ with $s< yz"$. (So $P(s)$ is "$s$ is less than some multiple of $y$".) We have:
(i). $P(1)$ because $1<2y.$
(ii). $(P(s)implies P(s+1))$ for each $s,$ because if $s< yz$ then $$s+1< yz+1< yz+2y=y(z+2).$$ So by Induction, $P(s)$ holds for all $s.$ In particular $P(x)$ is true.
(III). So for $n,min mathbb N,$ there exists $zin mathbb N$ such that $m< zn.$ By the Well-Ordering Principle, let $q'$ be the least such $n.$ We have $(q'-1)nleq m<q'n.$ (This is immediate if $q'=1.$ If $q'>1$ then $q'>q-1in mathbb N,$ and then the def'n of $q'$ implies $(q'-1)nleq m.$)
Let $q=q'-1.$ So $qnleq m<(q+1)n.$ Let $r=m-qn.$ Then $$0=qn-qnleq m-qn=r<(q+1)n-qn=n.$$ And of course $m=qn+r.$
Now if $m=q_1n+r_1$ with for integers $q_1,r_1$ with $0leq r_1<n$ then $$0=m-m=(qn+r)-(q_1n+r_1)=(q-q_1)n+(r-r_1),$$ so $|r-r_1|=|(q-q_1)n|.$ This is impossible if $q_1ne q.$ Because (i). $q_1ne qimplies |(q-q_1)n|geq n,$ but (ii). $|r-r_1|<n$ because $$(0leq r<n land 0leq r_1<n)implies (;(r-r_1<n-0=n) land (r_1-r<n-0=n);).$$
Since $q_1=q$ we have $r_1=q_1n -m=qn-m=r.$
I will leave the case $mleq 0$ to you.
answered Dec 14 '16 at 23:43
DanielWainfleetDanielWainfleet
35.6k31648
$endgroup$
add a comment |
$begingroup$
(I). Let $P(s)$ denote a statement about s, which may or may not be true. The Principle of Induction :
If (i) $P(1)$ is true,
and if (ii) For all $sin mathbb N;(P(s)implies P(s+1),$
then (iii) $P(s)$ is true for all $sin mathbb N.$
Digression: If (ii) is true, it does not follow that $P(s)$ is true for any $s.$ For example if $P(s)$ is "$s<s$" then (ii) is true ( although (i) is false).
Equivalent to the Principle of Induction is the Well-Ordering Principle:
If $P(s)$ is true for some $sin mathbb N$ then there is a least $sin mathbb N$ for which $P(s)$ is true.
(II). By Induction we get the Archimedean property of $mathbb N:$ For any $x,y in mathbb N$ there exists $zin mathbb N$ such that $x< zy.$
Proof: Let $P(s)$ be " There exists $z$ with $s< yz"$. (So $P(s)$ is "$s$ is less than some multiple of $y$".) We have:
(i). $P(1)$ because $1<2y.$
(ii). $(P(s)implies P(s+1))$ for each $s,$ because if $s< yz$ then $$s+1< yz+1< yz+2y=y(z+2).$$ So by Induction, $P(s)$ holds for all $s.$ In particular $P(x)$ is true.
(III). So for $n,min mathbb N,$ there exists $zin mathbb N$ such that $m< zn.$ By the Well-Ordering Principle, let $q'$ be the least such $n.$ We have $(q'-1)nleq m<q'n.$ (This is immediate if $q'=1.$ If $q'>1$ then $q'>q-1in mathbb N,$ and then the def'n of $q'$ implies $(q'-1)nleq m.$)
Let $q=q'-1.$ So $qnleq m<(q+1)n.$ Let $r=m-qn.$ Then $$0=qn-qnleq m-qn=r<(q+1)n-qn=n.$$ And of course $m=qn+r.$
Now if $m=q_1n+r_1$ with for integers $q_1,r_1$ with $0leq r_1<n$ then $$0=m-m=(qn+r)-(q_1n+r_1)=(q-q_1)n+(r-r_1),$$ so $|r-r_1|=|(q-q_1)n|.$ This is impossible if $q_1ne q.$ Because (i). $q_1ne qimplies |(q-q_1)n|geq n,$ but (ii). $|r-r_1|<n$ because $$(0leq r<n land 0leq r_1<n)implies (;(r-r_1<n-0=n) land (r_1-r<n-0=n);).$$
Since $q_1=q$ we have $r_1=q_1n -m=qn-m=r.$
I will leave the case $mleq 0$ to you.
answered Dec 14 '16 at 23:43
DanielWainfleetDanielWainfleet
35.6k31648
$endgroup$
add a comment |
$begingroup$
(I). Let $P(s)$ denote a statement about s, which may or may not be true. The Principle of Induction :
If (i) $P(1)$ is true,
and if (ii) For all $sin mathbb N;(P(s)implies P(s+1),$
then (iii) $P(s)$ is true for all $sin mathbb N.$
Digression: If (ii) is true, it does not follow that $P(s)$ is true for any $s.$ For example if $P(s)$ is "$s<s$" then (ii) is true ( although (i) is false).
Equivalent to the Principle of Induction is the Well-Ordering Principle:
If $P(s)$ is true for some $sin mathbb N$ then there is a least $sin mathbb N$ for which $P(s)$ is true.
(II). By Induction we get the Archimedean property of $mathbb N:$ For any $x,y in mathbb N$ there exists $zin mathbb N$ such that $x< zy.$
Proof: Let $P(s)$ be " There exists $z$ with $s< yz"$. (So $P(s)$ is "$s$ is less than some multiple of $y$".) We have:
(i). $P(1)$ because $1<2y.$
(ii). $(P(s)implies P(s+1))$ for each $s,$ because if $s< yz$ then $$s+1< yz+1< yz+2y=y(z+2).$$ So by Induction, $P(s)$ holds for all $s.$ In particular $P(x)$ is true.
(III). So for $n,min mathbb N,$ there exists $zin mathbb N$ such that $m< zn.$ By the Well-Ordering Principle, let $q'$ be the least such $n.$ We have $(q'-1)nleq m<q'n.$ (This is immediate if $q'=1.$ If $q'>1$ then $q'>q-1in mathbb N,$ and then the def'n of $q'$ implies $(q'-1)nleq m.$)
Let $q=q'-1.$ So $qnleq m<(q+1)n.$ Let $r=m-qn.$ Then $$0=qn-qnleq m-qn=r<(q+1)n-qn=n.$$ And of course $m=qn+r.$
Now if $m=q_1n+r_1$ with for integers $q_1,r_1$ with $0leq r_1<n$ then $$0=m-m=(qn+r)-(q_1n+r_1)=(q-q_1)n+(r-r_1),$$ so $|r-r_1|=|(q-q_1)n|.$ This is impossible if $q_1ne q.$ Because (i). $q_1ne qimplies |(q-q_1)n|geq n,$ but (ii). $|r-r_1|<n$ because $$(0leq r<n land 0leq r_1<n)implies (;(r-r_1<n-0=n) land (r_1-r<n-0=n);).$$
Since $q_1=q$ we have $r_1=q_1n -m=qn-m=r.$
I will leave the case $mleq 0$ to you.
answered Dec 14 '16 at 23:43
DanielWainfleetDanielWainfleet
35.6k31648
$endgroup$
(I). Let $P(s)$ denote a statement about s, which may or may not be true. The Principle of Induction :
If (i) $P(1)$ is true,
and if (ii) For all $sin mathbb N;(P(s)implies P(s+1),$
then (iii) $P(s)$ is true for all $sin mathbb N.$
Digression: If (ii) is true, it does not follow that $P(s)$ is true for any $s.$ For example if $P(s)$ is "$s<s$" then (ii) is true ( although (i) is false).
Equivalent to the Principle of Induction is the Well-Ordering Principle:
If $P(s)$ is true for some $sin mathbb N$ then there is a least $sin mathbb N$ for which $P(s)$ is true.
(II). By Induction we get the Archimedean property of $mathbb N:$ For any $x,y in mathbb N$ there exists $zin mathbb N$ such that $x< zy.$
Proof: Let $P(s)$ be " There exists $z$ with $s< yz"$. (So $P(s)$ is "$s$ is less than some multiple of $y$".) We have:
(i). $P(1)$ because $1<2y.$
(ii). $(P(s)implies P(s+1))$ for each $s,$ because if $s< yz$ then $$s+1< yz+1< yz+2y=y(z+2).$$ So by Induction, $P(s)$ holds for all $s.$ In particular $P(x)$ is true.
(III). So for $n,min mathbb N,$ there exists $zin mathbb N$ such that $m< zn.$ By the Well-Ordering Principle, let $q'$ be the least such $n.$ We have $(q'-1)nleq m<q'n.$ (This is immediate if $q'=1.$ If $q'>1$ then $q'>q-1in mathbb N,$ and then the def'n of $q'$ implies $(q'-1)nleq m.$)
Let $q=q'-1.$ So $qnleq m<(q+1)n.$ Let $r=m-qn.$ Then $$0=qn-qnleq m-qn=r<(q+1)n-qn=n.$$ And of course $m=qn+r.$
Now if $m=q_1n+r_1$ with for integers $q_1,r_1$ with $0leq r_1<n$ then $$0=m-m=(qn+r)-(q_1n+r_1)=(q-q_1)n+(r-r_1),$$ so $|r-r_1|=|(q-q_1)n|.$ This is impossible if $q_1ne q.$ Because (i). $q_1ne qimplies |(q-q_1)n|geq n,$ but (ii). $|r-r_1|<n$ because $$(0leq r<n land 0leq r_1<n)implies (;(r-r_1<n-0=n) land (r_1-r<n-0=n);).$$
Since $q_1=q$ we have $r_1=q_1n -m=qn-m=r.$
I will leave the case $mleq 0$ to you.
answered Dec 14 '16 at 23:43
DanielWainfleetDanielWainfleet
35.6k31648
answered Dec 14 '16 at 23:43
DanielWainfleetDanielWainfleet
35.6k31648
answered Dec 14 '16 at 23:43
DanielWainfleetDanielWainfleet
35.6k31648
answered Dec 14 '16 at 23:43
DanielWainfleetDanielWainfleet
35.6k31648
35.6k31648
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f736667%2fproving-the-division-algorithm-using-induction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
