Proof Verification- Prove that $(a+b,a-b) geq (a,b)$ for any two integers.
$begingroup$
I came across this question while solving the book Challenge and Thrill of Pre-College mathematics. Please check if the proof that I have done is correct. (I am familiar with only basic number theory including basic theory of primes and modular arithmetic.)
I believe that I might have made some mistake in reasoning while proving that $bx-aygeq 0$
Proof:
Without loss of generality, we can assume that $a$ and $b$ are both positive with $ageq b gt 0$
Since GCD can be written as linear combination of the two integers,
$$(a,b) = ax + by$$
We know that $(a,b) leq b leq a$
Which implies that either $x$ or $y$ is is negative.
We can assume that $y$ is negative. This implies $bx-aygeq 0$. (Conversely if $x$ is negative then $ay-bx geq 0$ )
Now,
$$ax + by = (a,b)$$
$$Rightarrow ax + by + bx - ay geq (a,b)$$
$$Rightarrow (a+b)x + (b-a)y geq (a,b)$$
$$Rightarrow (a+b)x + (-y)(a-b) geq (a,b)$$
$$Rightarrow (a+b, a- b) geq (a,b)$$
QED.
number-theory proof-verification greatest-common-divisor
asked Jan 6 at 7:13
Naman KumarNaman Kumar
22813
$endgroup$
add a comment |
$begingroup$
I came across this question while solving the book Challenge and Thrill of Pre-College mathematics. Please check if the proof that I have done is correct. (I am familiar with only basic number theory including basic theory of primes and modular arithmetic.)
I believe that I might have made some mistake in reasoning while proving that $bx-aygeq 0$
Proof:
Without loss of generality, we can assume that $a$ and $b$ are both positive with $ageq b gt 0$
Since GCD can be written as linear combination of the two integers,
$$(a,b) = ax + by$$
We know that $(a,b) leq b leq a$
Which implies that either $x$ or $y$ is is negative.
We can assume that $y$ is negative. This implies $bx-aygeq 0$. (Conversely if $x$ is negative then $ay-bx geq 0$ )
Now,
$$ax + by = (a,b)$$
$$Rightarrow ax + by + bx - ay geq (a,b)$$
$$Rightarrow (a+b)x + (b-a)y geq (a,b)$$
$$Rightarrow (a+b)x + (-y)(a-b) geq (a,b)$$
$$Rightarrow (a+b, a- b) geq (a,b)$$
QED.
number-theory proof-verification greatest-common-divisor
asked Jan 6 at 7:13
Naman KumarNaman Kumar
22813
$endgroup$
$begingroup$
Your proof only shows that some linear combination of $a+b$ and $a-b$ is greater than or equal to $gcd(a,b)$. It doesn't necessarily imply that $gcd(a+b,a-b) geq gcd(a,b)$.
$endgroup$
– Anurag A
Jan 6 at 7:17
$begingroup$
Thank you. I suspected there was some mistake in the reasoning. If I want this question answered do I need to ask another question? Because I have no idea what to do and I am unable to find the answer anywhere.
$endgroup$
– Naman Kumar
Jan 6 at 7:23
add a comment |
$begingroup$
I came across this question while solving the book Challenge and Thrill of Pre-College mathematics. Please check if the proof that I have done is correct. (I am familiar with only basic number theory including basic theory of primes and modular arithmetic.)
I believe that I might have made some mistake in reasoning while proving that $bx-aygeq 0$
Proof:
Without loss of generality, we can assume that $a$ and $b$ are both positive with $ageq b gt 0$
Since GCD can be written as linear combination of the two integers,
$$(a,b) = ax + by$$
We know that $(a,b) leq b leq a$
Which implies that either $x$ or $y$ is is negative.
We can assume that $y$ is negative. This implies $bx-aygeq 0$. (Conversely if $x$ is negative then $ay-bx geq 0$ )
Now,
$$ax + by = (a,b)$$
$$Rightarrow ax + by + bx - ay geq (a,b)$$
$$Rightarrow (a+b)x + (b-a)y geq (a,b)$$
$$Rightarrow (a+b)x + (-y)(a-b) geq (a,b)$$
$$Rightarrow (a+b, a- b) geq (a,b)$$
QED.
number-theory proof-verification greatest-common-divisor
asked Jan 6 at 7:13
Naman KumarNaman Kumar
22813
$endgroup$
I came across this question while solving the book Challenge and Thrill of Pre-College mathematics. Please check if the proof that I have done is correct. (I am familiar with only basic number theory including basic theory of primes and modular arithmetic.)
I believe that I might have made some mistake in reasoning while proving that $bx-aygeq 0$
Proof:
Without loss of generality, we can assume that $a$ and $b$ are both positive with $ageq b gt 0$
Since GCD can be written as linear combination of the two integers,
$$(a,b) = ax + by$$
We know that $(a,b) leq b leq a$
Which implies that either $x$ or $y$ is is negative.
We can assume that $y$ is negative. This implies $bx-aygeq 0$. (Conversely if $x$ is negative then $ay-bx geq 0$ )
Now,
$$ax + by = (a,b)$$
$$Rightarrow ax + by + bx - ay geq (a,b)$$
$$Rightarrow (a+b)x + (b-a)y geq (a,b)$$
$$Rightarrow (a+b)x + (-y)(a-b) geq (a,b)$$
$$Rightarrow (a+b, a- b) geq (a,b)$$
QED.
number-theory proof-verification greatest-common-divisor
number-theory proof-verification greatest-common-divisor
asked Jan 6 at 7:13
Naman KumarNaman Kumar
22813
asked Jan 6 at 7:13
Naman KumarNaman Kumar
22813
asked Jan 6 at 7:13
Naman KumarNaman Kumar
22813
asked Jan 6 at 7:13
Naman KumarNaman Kumar
22813
asked Jan 6 at 7:13
Naman KumarNaman Kumar
22813
22813
$begingroup$
Your proof only shows that some linear combination of $a+b$ and $a-b$ is greater than or equal to $gcd(a,b)$. It doesn't necessarily imply that $gcd(a+b,a-b) geq gcd(a,b)$.
$endgroup$
– Anurag A
Jan 6 at 7:17
$begingroup$
Thank you. I suspected there was some mistake in the reasoning. If I want this question answered do I need to ask another question? Because I have no idea what to do and I am unable to find the answer anywhere.
$endgroup$
– Naman Kumar
Jan 6 at 7:23
add a comment |
$begingroup$
Your proof only shows that some linear combination of $a+b$ and $a-b$ is greater than or equal to $gcd(a,b)$. It doesn't necessarily imply that $gcd(a+b,a-b) geq gcd(a,b)$.
$endgroup$
– Anurag A
Jan 6 at 7:17
$begingroup$
Thank you. I suspected there was some mistake in the reasoning. If I want this question answered do I need to ask another question? Because I have no idea what to do and I am unable to find the answer anywhere.
$endgroup$
– Naman Kumar
Jan 6 at 7:23
$begingroup$
Your proof only shows that some linear combination of $a+b$ and $a-b$ is greater than or equal to $gcd(a,b)$. It doesn't necessarily imply that $gcd(a+b,a-b) geq gcd(a,b)$.
$endgroup$
– Anurag A
Jan 6 at 7:17
$begingroup$
Your proof only shows that some linear combination of $a+b$ and $a-b$ is greater than or equal to $gcd(a,b)$. It doesn't necessarily imply that $gcd(a+b,a-b) geq gcd(a,b)$.
$endgroup$
– Anurag A
Jan 6 at 7:17
$begingroup$
Thank you. I suspected there was some mistake in the reasoning. If I want this question answered do I need to ask another question? Because I have no idea what to do and I am unable to find the answer anywhere.
$endgroup$
– Naman Kumar
Jan 6 at 7:23
$begingroup$
Thank you. I suspected there was some mistake in the reasoning. If I want this question answered do I need to ask another question? Because I have no idea what to do and I am unable to find the answer anywhere.
$endgroup$
– Naman Kumar
Jan 6 at 7:23
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $d=gcd(a+b,a-b)$ and $gcd(a,b)=e$.
$e$ must divide the sum and the difference of $a$ and $b$. This means that $e mid a+b$ and $e mid a-b$. Thus $e$ is a common divisor of $a+b$ and $a-b$. Thus $e mid gcd(a+b, a-b)=d$. Thus
$$e leq d.$$
Your question is answered.
However one can do a bit more:
Furthermore, $d mid a+b$ and $d mid a-b$. Then $d mid 2a$ and $d mid 2b$. Thus $d$ is a common divisor of $2a$ and $2b$. Consequently, $d mid gcd(2a,2b)$. But $gcd(2a,2b)=2gcd(a,b)=2e$. Thus,
$$d mid 2e implies d leq 2e.$$
So we can say
$$ e leq d leq 2e.$$
answered Jan 6 at 7:33
Anurag AAnurag A
26.3k12251
$endgroup$
$begingroup$
I am unsure of what you exactly proved. Did you really prove that the gcd of $a-b,a+b$ is always the double of the gcd of $a,b$? What happens when, say, $a=3, b=12$?
$endgroup$
– Mindlack
Jan 6 at 8:44
$begingroup$
$d | gcd(2a,2b)$ doesn’t imply that $d = gcd(2a,2b)$.
$endgroup$
– Jonas De Schouwer
Jan 6 at 10:44
$begingroup$
Thank you for pointing out the error. I had typed some stuff which got deleted by mistake and I didn’t realize that. I have fixed it. Let me know if something is missing.
$endgroup$
– Anurag A
Jan 6 at 12:29
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%2f3063568%2fproof-verification-prove-that-ab-a-b-geq-a-b-for-any-two-integers%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$
Let $d=gcd(a+b,a-b)$ and $gcd(a,b)=e$.
$e$ must divide the sum and the difference of $a$ and $b$. This means that $e mid a+b$ and $e mid a-b$. Thus $e$ is a common divisor of $a+b$ and $a-b$. Thus $e mid gcd(a+b, a-b)=d$. Thus
$$e leq d.$$
Your question is answered.
However one can do a bit more:
Furthermore, $d mid a+b$ and $d mid a-b$. Then $d mid 2a$ and $d mid 2b$. Thus $d$ is a common divisor of $2a$ and $2b$. Consequently, $d mid gcd(2a,2b)$. But $gcd(2a,2b)=2gcd(a,b)=2e$. Thus,
$$d mid 2e implies d leq 2e.$$
So we can say
$$ e leq d leq 2e.$$
answered Jan 6 at 7:33
Anurag AAnurag A
26.3k12251
$endgroup$
$begingroup$
I am unsure of what you exactly proved. Did you really prove that the gcd of $a-b,a+b$ is always the double of the gcd of $a,b$? What happens when, say, $a=3, b=12$?
$endgroup$
– Mindlack
Jan 6 at 8:44
$begingroup$
$d | gcd(2a,2b)$ doesn’t imply that $d = gcd(2a,2b)$.
$endgroup$
– Jonas De Schouwer
Jan 6 at 10:44
$begingroup$
Thank you for pointing out the error. I had typed some stuff which got deleted by mistake and I didn’t realize that. I have fixed it. Let me know if something is missing.
$endgroup$
– Anurag A
Jan 6 at 12:29
add a comment |
$begingroup$
Let $d=gcd(a+b,a-b)$ and $gcd(a,b)=e$.
$e$ must divide the sum and the difference of $a$ and $b$. This means that $e mid a+b$ and $e mid a-b$. Thus $e$ is a common divisor of $a+b$ and $a-b$. Thus $e mid gcd(a+b, a-b)=d$. Thus
$$e leq d.$$
Your question is answered.
However one can do a bit more:
Furthermore, $d mid a+b$ and $d mid a-b$. Then $d mid 2a$ and $d mid 2b$. Thus $d$ is a common divisor of $2a$ and $2b$. Consequently, $d mid gcd(2a,2b)$. But $gcd(2a,2b)=2gcd(a,b)=2e$. Thus,
$$d mid 2e implies d leq 2e.$$
So we can say
$$ e leq d leq 2e.$$
answered Jan 6 at 7:33
Anurag AAnurag A
26.3k12251
$endgroup$
$begingroup$
I am unsure of what you exactly proved. Did you really prove that the gcd of $a-b,a+b$ is always the double of the gcd of $a,b$? What happens when, say, $a=3, b=12$?
$endgroup$
– Mindlack
Jan 6 at 8:44
$begingroup$
$d | gcd(2a,2b)$ doesn’t imply that $d = gcd(2a,2b)$.
$endgroup$
– Jonas De Schouwer
Jan 6 at 10:44
$begingroup$
Thank you for pointing out the error. I had typed some stuff which got deleted by mistake and I didn’t realize that. I have fixed it. Let me know if something is missing.
$endgroup$
– Anurag A
Jan 6 at 12:29
add a comment |
$begingroup$
Let $d=gcd(a+b,a-b)$ and $gcd(a,b)=e$.
$e$ must divide the sum and the difference of $a$ and $b$. This means that $e mid a+b$ and $e mid a-b$. Thus $e$ is a common divisor of $a+b$ and $a-b$. Thus $e mid gcd(a+b, a-b)=d$. Thus
$$e leq d.$$
Your question is answered.
However one can do a bit more:
Furthermore, $d mid a+b$ and $d mid a-b$. Then $d mid 2a$ and $d mid 2b$. Thus $d$ is a common divisor of $2a$ and $2b$. Consequently, $d mid gcd(2a,2b)$. But $gcd(2a,2b)=2gcd(a,b)=2e$. Thus,
$$d mid 2e implies d leq 2e.$$
So we can say
$$ e leq d leq 2e.$$
answered Jan 6 at 7:33
Anurag AAnurag A
26.3k12251
$endgroup$
Let $d=gcd(a+b,a-b)$ and $gcd(a,b)=e$.
$e$ must divide the sum and the difference of $a$ and $b$. This means that $e mid a+b$ and $e mid a-b$. Thus $e$ is a common divisor of $a+b$ and $a-b$. Thus $e mid gcd(a+b, a-b)=d$. Thus
$$e leq d.$$
Your question is answered.
However one can do a bit more:
Furthermore, $d mid a+b$ and $d mid a-b$. Then $d mid 2a$ and $d mid 2b$. Thus $d$ is a common divisor of $2a$ and $2b$. Consequently, $d mid gcd(2a,2b)$. But $gcd(2a,2b)=2gcd(a,b)=2e$. Thus,
$$d mid 2e implies d leq 2e.$$
So we can say
$$ e leq d leq 2e.$$
answered Jan 6 at 7:33
Anurag AAnurag A
26.3k12251
edited Jan 6 at 12:27
answered Jan 6 at 7:33
Anurag AAnurag A
26.3k12251
answered Jan 6 at 7:33
Anurag AAnurag A
26.3k12251
answered Jan 6 at 7:33
Anurag AAnurag A
26.3k12251
26.3k12251
$begingroup$
I am unsure of what you exactly proved. Did you really prove that the gcd of $a-b,a+b$ is always the double of the gcd of $a,b$? What happens when, say, $a=3, b=12$?
$endgroup$
– Mindlack
Jan 6 at 8:44
$begingroup$
$d | gcd(2a,2b)$ doesn’t imply that $d = gcd(2a,2b)$.
$endgroup$
– Jonas De Schouwer
Jan 6 at 10:44
$begingroup$
Thank you for pointing out the error. I had typed some stuff which got deleted by mistake and I didn’t realize that. I have fixed it. Let me know if something is missing.
$endgroup$
– Anurag A
Jan 6 at 12:29
add a comment |
$begingroup$
I am unsure of what you exactly proved. Did you really prove that the gcd of $a-b,a+b$ is always the double of the gcd of $a,b$? What happens when, say, $a=3, b=12$?
$endgroup$
– Mindlack
Jan 6 at 8:44
$begingroup$
$d | gcd(2a,2b)$ doesn’t imply that $d = gcd(2a,2b)$.
$endgroup$
– Jonas De Schouwer
Jan 6 at 10:44
$begingroup$
Thank you for pointing out the error. I had typed some stuff which got deleted by mistake and I didn’t realize that. I have fixed it. Let me know if something is missing.
$endgroup$
– Anurag A
Jan 6 at 12:29
$begingroup$
I am unsure of what you exactly proved. Did you really prove that the gcd of $a-b,a+b$ is always the double of the gcd of $a,b$? What happens when, say, $a=3, b=12$?
$endgroup$
– Mindlack
Jan 6 at 8:44
$begingroup$
I am unsure of what you exactly proved. Did you really prove that the gcd of $a-b,a+b$ is always the double of the gcd of $a,b$? What happens when, say, $a=3, b=12$?
$endgroup$
– Mindlack
Jan 6 at 8:44
$begingroup$
$d | gcd(2a,2b)$ doesn’t imply that $d = gcd(2a,2b)$.
$endgroup$
– Jonas De Schouwer
Jan 6 at 10:44
$begingroup$
$d | gcd(2a,2b)$ doesn’t imply that $d = gcd(2a,2b)$.
$endgroup$
– Jonas De Schouwer
Jan 6 at 10:44
$begingroup$
Thank you for pointing out the error. I had typed some stuff which got deleted by mistake and I didn’t realize that. I have fixed it. Let me know if something is missing.
$endgroup$
– Anurag A
Jan 6 at 12:29
$begingroup$
Thank you for pointing out the error. I had typed some stuff which got deleted by mistake and I didn’t realize that. I have fixed it. Let me know if something is missing.
$endgroup$
– Anurag A
Jan 6 at 12:29
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%2f3063568%2fproof-verification-prove-that-ab-a-b-geq-a-b-for-any-two-integers%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
$begingroup$
Your proof only shows that some linear combination of $a+b$ and $a-b$ is greater than or equal to $gcd(a,b)$. It doesn't necessarily imply that $gcd(a+b,a-b) geq gcd(a,b)$.
$endgroup$
– Anurag A
Jan 6 at 7:17
$begingroup$
Thank you. I suspected there was some mistake in the reasoning. If I want this question answered do I need to ask another question? Because I have no idea what to do and I am unable to find the answer anywhere.
$endgroup$
– Naman Kumar
Jan 6 at 7:23