Mixing
How to prove b | a iff remainder = 0
$begingroup$
I am trying to find a way to prove that $b|a$ if and only if the remainder of $a$ divided by $b$ is $0$.
So far this is what I have:
If $r$ is the remainder of $a$ divided by $b$, this means $a=bq+r$. Subsequently, if $r=0$ then $a=bq$ which means $b|a$ by definition.
What I can't figure out is how to prove the if and only if part. I'm not sure if its better to start from $b|a$ and prove that $r=0$ or try to prove that if $r>0$ then $b nmid a$. Either way I have had trouble with the steps to make the proper conclusion.
elementary-number-theory divisibility
edited Jan 30 at 16:48
Bill Dubuque
213k29196654
asked Jan 30 at 16:38
raznbagelraznbagel
206
$endgroup$
add a comment |
$begingroup$
I am trying to find a way to prove that $b|a$ if and only if the remainder of $a$ divided by $b$ is $0$.
So far this is what I have:
If $r$ is the remainder of $a$ divided by $b$, this means $a=bq+r$. Subsequently, if $r=0$ then $a=bq$ which means $b|a$ by definition.
What I can't figure out is how to prove the if and only if part. I'm not sure if its better to start from $b|a$ and prove that $r=0$ or try to prove that if $r>0$ then $b nmid a$. Either way I have had trouble with the steps to make the proper conclusion.
elementary-number-theory divisibility
edited Jan 30 at 16:48
Bill Dubuque
213k29196654
asked Jan 30 at 16:38
raznbagelraznbagel
206
$endgroup$
2
$begingroup$
What is the def of $b|a$ ?
$endgroup$
– Mauro ALLEGRANZA
Jan 30 at 16:40
$begingroup$
The def of $b|a$ is there exists some integer $k$ such that $a=bk$.
$endgroup$
– raznbagel
Jan 30 at 16:48
$begingroup$
Hint $ $ Use the uniqueness of the remainder.
$endgroup$
– Bill Dubuque
Jan 30 at 16:51
add a comment |
$begingroup$
I am trying to find a way to prove that $b|a$ if and only if the remainder of $a$ divided by $b$ is $0$.
So far this is what I have:
If $r$ is the remainder of $a$ divided by $b$, this means $a=bq+r$. Subsequently, if $r=0$ then $a=bq$ which means $b|a$ by definition.
What I can't figure out is how to prove the if and only if part. I'm not sure if its better to start from $b|a$ and prove that $r=0$ or try to prove that if $r>0$ then $b nmid a$. Either way I have had trouble with the steps to make the proper conclusion.
elementary-number-theory divisibility
edited Jan 30 at 16:48
Bill Dubuque
213k29196654
asked Jan 30 at 16:38
raznbagelraznbagel
206
$endgroup$
I am trying to find a way to prove that $b|a$ if and only if the remainder of $a$ divided by $b$ is $0$.
So far this is what I have:
If $r$ is the remainder of $a$ divided by $b$, this means $a=bq+r$. Subsequently, if $r=0$ then $a=bq$ which means $b|a$ by definition.
What I can't figure out is how to prove the if and only if part. I'm not sure if its better to start from $b|a$ and prove that $r=0$ or try to prove that if $r>0$ then $b nmid a$. Either way I have had trouble with the steps to make the proper conclusion.
elementary-number-theory divisibility
elementary-number-theory divisibility
edited Jan 30 at 16:48
Bill Dubuque
213k29196654
asked Jan 30 at 16:38
raznbagelraznbagel
206
edited Jan 30 at 16:48
Bill Dubuque
213k29196654
asked Jan 30 at 16:38
raznbagelraznbagel
206
edited Jan 30 at 16:48
Bill Dubuque
213k29196654
edited Jan 30 at 16:48
Bill Dubuque
213k29196654
edited Jan 30 at 16:48
Bill Dubuque
213k29196654
213k29196654
asked Jan 30 at 16:38
raznbagelraznbagel
206
asked Jan 30 at 16:38
raznbagelraznbagel
206
asked Jan 30 at 16:38
raznbagelraznbagel
206
206
2
$begingroup$
What is the def of $b|a$ ?
$endgroup$
– Mauro ALLEGRANZA
Jan 30 at 16:40
$begingroup$
The def of $b|a$ is there exists some integer $k$ such that $a=bk$.
$endgroup$
– raznbagel
Jan 30 at 16:48
$begingroup$
Hint $ $ Use the uniqueness of the remainder.
$endgroup$
– Bill Dubuque
Jan 30 at 16:51
add a comment |
2
$begingroup$
What is the def of $b|a$ ?
$endgroup$
– Mauro ALLEGRANZA
Jan 30 at 16:40
$begingroup$
The def of $b|a$ is there exists some integer $k$ such that $a=bk$.
$endgroup$
– raznbagel
Jan 30 at 16:48
$begingroup$
Hint $ $ Use the uniqueness of the remainder.
$endgroup$
– Bill Dubuque
Jan 30 at 16:51
2
2
$begingroup$
What is the def of $b|a$ ?
$endgroup$
– Mauro ALLEGRANZA
Jan 30 at 16:40
$begingroup$
What is the def of $b|a$ ?
$endgroup$
– Mauro ALLEGRANZA
Jan 30 at 16:40
$begingroup$
The def of $b|a$ is there exists some integer $k$ such that $a=bk$.
$endgroup$
– raznbagel
Jan 30 at 16:48
$begingroup$
The def of $b|a$ is there exists some integer $k$ such that $a=bk$.
$endgroup$
– raznbagel
Jan 30 at 16:48
$begingroup$
Hint $ $ Use the uniqueness of the remainder.
$endgroup$
– Bill Dubuque
Jan 30 at 16:51
$begingroup$
Hint $ $ Use the uniqueness of the remainder.
$endgroup$
– Bill Dubuque
Jan 30 at 16:51
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
In the other direction, you have $b|a$, and you want to prove that the reminder $r$ is 0.
$b|a$, therefore $a = bq$ for some $q$.
On the other hand, $a = bp + r$ for some $p$ and some $0 le r < b$.
Therefore, $bq = bp + r$, so $b(q-p) = r$.
If $q < p$, then $r < 0$, contradiction. On the other hand, if $q > p$, then $r > b$, again contradiction. So we have $q=p$, therefore $r=0$.
Also, if you have already proven the uniqueness of the reminder (which goes pretty much the same as what I have above), you can simply show that 0 works as reminder, so that must be it.
answered Jan 30 at 16:48
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
You're essentially duplicating the proof of the uniqueness of the remainder. If this is already know (as is common) then one should simply invoke it rather than duplicate it.
$endgroup$
– Bill Dubuque
Jan 30 at 16:52
$begingroup$
Thanks, this helped me understand why the uniqueness of the remainder is the key. I did already have that as given/proved but seeing it connected directly is helpful.
$endgroup$
– raznbagel
Jan 30 at 16:59
$begingroup$
@raznbagel Uniqueness theorems often provide powerful tools for proving equalities, so they are one of the first things one should try when they are available.
$endgroup$
– Bill Dubuque
Jan 30 at 17:07
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%2f3093769%2fhow-to-prove-b-a-iff-remainder-0%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In the other direction, you have $b|a$, and you want to prove that the reminder $r$ is 0.
$b|a$, therefore $a = bq$ for some $q$.
On the other hand, $a = bp + r$ for some $p$ and some $0 le r < b$.
Therefore, $bq = bp + r$, so $b(q-p) = r$.
If $q < p$, then $r < 0$, contradiction. On the other hand, if $q > p$, then $r > b$, again contradiction. So we have $q=p$, therefore $r=0$.
Also, if you have already proven the uniqueness of the reminder (which goes pretty much the same as what I have above), you can simply show that 0 works as reminder, so that must be it.
answered Jan 30 at 16:48
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
You're essentially duplicating the proof of the uniqueness of the remainder. If this is already know (as is common) then one should simply invoke it rather than duplicate it.
$endgroup$
– Bill Dubuque
Jan 30 at 16:52
$begingroup$
Thanks, this helped me understand why the uniqueness of the remainder is the key. I did already have that as given/proved but seeing it connected directly is helpful.
$endgroup$
– raznbagel
Jan 30 at 16:59
$begingroup$
@raznbagel Uniqueness theorems often provide powerful tools for proving equalities, so they are one of the first things one should try when they are available.
$endgroup$
– Bill Dubuque
Jan 30 at 17:07
add a comment |
$begingroup$
In the other direction, you have $b|a$, and you want to prove that the reminder $r$ is 0.
$b|a$, therefore $a = bq$ for some $q$.
On the other hand, $a = bp + r$ for some $p$ and some $0 le r < b$.
Therefore, $bq = bp + r$, so $b(q-p) = r$.
If $q < p$, then $r < 0$, contradiction. On the other hand, if $q > p$, then $r > b$, again contradiction. So we have $q=p$, therefore $r=0$.
Also, if you have already proven the uniqueness of the reminder (which goes pretty much the same as what I have above), you can simply show that 0 works as reminder, so that must be it.
answered Jan 30 at 16:48
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
You're essentially duplicating the proof of the uniqueness of the remainder. If this is already know (as is common) then one should simply invoke it rather than duplicate it.
$endgroup$
– Bill Dubuque
Jan 30 at 16:52
$begingroup$
Thanks, this helped me understand why the uniqueness of the remainder is the key. I did already have that as given/proved but seeing it connected directly is helpful.
$endgroup$
– raznbagel
Jan 30 at 16:59
$begingroup$
@raznbagel Uniqueness theorems often provide powerful tools for proving equalities, so they are one of the first things one should try when they are available.
$endgroup$
– Bill Dubuque
Jan 30 at 17:07
add a comment |
$begingroup$
In the other direction, you have $b|a$, and you want to prove that the reminder $r$ is 0.
$b|a$, therefore $a = bq$ for some $q$.
On the other hand, $a = bp + r$ for some $p$ and some $0 le r < b$.
Therefore, $bq = bp + r$, so $b(q-p) = r$.
If $q < p$, then $r < 0$, contradiction. On the other hand, if $q > p$, then $r > b$, again contradiction. So we have $q=p$, therefore $r=0$.
Also, if you have already proven the uniqueness of the reminder (which goes pretty much the same as what I have above), you can simply show that 0 works as reminder, so that must be it.
answered Jan 30 at 16:48
Todor MarkovTodor Markov
2,420412
$endgroup$
In the other direction, you have $b|a$, and you want to prove that the reminder $r$ is 0.
$b|a$, therefore $a = bq$ for some $q$.
On the other hand, $a = bp + r$ for some $p$ and some $0 le r < b$.
Therefore, $bq = bp + r$, so $b(q-p) = r$.
If $q < p$, then $r < 0$, contradiction. On the other hand, if $q > p$, then $r > b$, again contradiction. So we have $q=p$, therefore $r=0$.
Also, if you have already proven the uniqueness of the reminder (which goes pretty much the same as what I have above), you can simply show that 0 works as reminder, so that must be it.
answered Jan 30 at 16:48
Todor MarkovTodor Markov
2,420412
edited Jan 30 at 16:54
answered Jan 30 at 16:48
Todor MarkovTodor Markov
2,420412
answered Jan 30 at 16:48
Todor MarkovTodor Markov
2,420412
answered Jan 30 at 16:48
Todor MarkovTodor Markov
2,420412
2,420412
$begingroup$
You're essentially duplicating the proof of the uniqueness of the remainder. If this is already know (as is common) then one should simply invoke it rather than duplicate it.
$endgroup$
– Bill Dubuque
Jan 30 at 16:52
$begingroup$
Thanks, this helped me understand why the uniqueness of the remainder is the key. I did already have that as given/proved but seeing it connected directly is helpful.
$endgroup$
– raznbagel
Jan 30 at 16:59
$begingroup$
@raznbagel Uniqueness theorems often provide powerful tools for proving equalities, so they are one of the first things one should try when they are available.
$endgroup$
– Bill Dubuque
Jan 30 at 17:07
add a comment |
$begingroup$
You're essentially duplicating the proof of the uniqueness of the remainder. If this is already know (as is common) then one should simply invoke it rather than duplicate it.
$endgroup$
– Bill Dubuque
Jan 30 at 16:52
$begingroup$
Thanks, this helped me understand why the uniqueness of the remainder is the key. I did already have that as given/proved but seeing it connected directly is helpful.
$endgroup$
– raznbagel
Jan 30 at 16:59
$begingroup$
@raznbagel Uniqueness theorems often provide powerful tools for proving equalities, so they are one of the first things one should try when they are available.
$endgroup$
– Bill Dubuque
Jan 30 at 17:07
$begingroup$
You're essentially duplicating the proof of the uniqueness of the remainder. If this is already know (as is common) then one should simply invoke it rather than duplicate it.
$endgroup$
– Bill Dubuque
Jan 30 at 16:52
$begingroup$
You're essentially duplicating the proof of the uniqueness of the remainder. If this is already know (as is common) then one should simply invoke it rather than duplicate it.
$endgroup$
– Bill Dubuque
Jan 30 at 16:52
$begingroup$
Thanks, this helped me understand why the uniqueness of the remainder is the key. I did already have that as given/proved but seeing it connected directly is helpful.
$endgroup$
– raznbagel
Jan 30 at 16:59
$begingroup$
Thanks, this helped me understand why the uniqueness of the remainder is the key. I did already have that as given/proved but seeing it connected directly is helpful.
$endgroup$
– raznbagel
Jan 30 at 16:59
$begingroup$
@raznbagel Uniqueness theorems often provide powerful tools for proving equalities, so they are one of the first things one should try when they are available.
$endgroup$
– Bill Dubuque
Jan 30 at 17:07
$begingroup$
@raznbagel Uniqueness theorems often provide powerful tools for proving equalities, so they are one of the first things one should try when they are available.
$endgroup$
– Bill Dubuque
Jan 30 at 17:07
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%2f3093769%2fhow-to-prove-b-a-iff-remainder-0%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
2
$begingroup$
What is the def of $b|a$ ?
$endgroup$
– Mauro ALLEGRANZA
Jan 30 at 16:40
$begingroup$
The def of $b|a$ is there exists some integer $k$ such that $a=bk$.
$endgroup$
– raznbagel
Jan 30 at 16:48
$begingroup$
Hint $ $ Use the uniqueness of the remainder.
$endgroup$
– Bill Dubuque
Jan 30 at 16:51