gcd(2a+1, 9a+4) = 1
The question is from Burton's Elementary Number Theory. I want to know if my proof is legible.
Proof : Let $$d=gcd(2a+1, 9a+4)$$
Then $$d|2a+1$$ and $$d|9a+4$$
$$2a+1=db$$ and $$9a+4=dc$$
$$ a = frac{db-1}{2}$$and$$a= frac{dc-4}{9}$$
Equating both equations :
$$ 9db-9=2dc-8 $$
$$ d(9b-2c) = 1 $$
$$ 9b-2c = frac{1}{d}$$
Now, since b and c are integers, therefore $frac{1}{d}$ is an integer, i.e d divides 1 and therefore $$gcd(a, b)= d = 1$$.
proof-verification
asked Jan 4 at 15:31
P.JoP.Jo
85
New contributor
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 4 more comments
The question is from Burton's Elementary Number Theory. I want to know if my proof is legible.
Proof : Let $$d=gcd(2a+1, 9a+4)$$
Then $$d|2a+1$$ and $$d|9a+4$$
$$2a+1=db$$ and $$9a+4=dc$$
$$ a = frac{db-1}{2}$$and$$a= frac{dc-4}{9}$$
Equating both equations :
$$ 9db-9=2dc-8 $$
$$ d(9b-2c) = 1 $$
$$ 9b-2c = frac{1}{d}$$
Now, since b and c are integers, therefore $frac{1}{d}$ is an integer, i.e d divides 1 and therefore $$gcd(a, b)= d = 1$$.
proof-verification
asked Jan 4 at 15:31
P.JoP.Jo
85
New contributor
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
It's correct. Essentially you eliminated $,a,,$ which can be done more directly as follows: $$bmod d!:, 2a!+!1equiv 0equiv 9a!+!4 Rightarrow color{#c00}0equiv 9(2a!+!1)-2(9a!+!4)equivcolor{#c00} 1 Rightarrow dmid color{#c00}{1!-!0}qquad$$
– Bill Dubuque
Jan 4 at 17:02
@BillDubuque Thanks. I'm sure it's a more direct approach but I'm unfamiliar with modular arithmetic so it had to be something without it.
– P.Jo
Jan 4 at 17:22
We can eliminate congruence notation too! Namely the above means $$dmid 2a!+!1,9a!+!4 Rightarrow dmid 1!=! 9(2a!+!1)-2(9a!+!4)qquad $$ since multiples of $d$ are closed under integral linear combinations.
– Bill Dubuque
Jan 4 at 17:27
@BillDubuque Yeah. That makes perfect sense. But what does it mean to be 'closed under integral linear combinations'?
– P.Jo
Jan 5 at 4:19
@BillDubuque Does it mean that the multiples of d= gcd(a, b) are all the linear combinations of a and b?
– P.Jo
Jan 5 at 4:27
|
show 4 more comments
The question is from Burton's Elementary Number Theory. I want to know if my proof is legible.
Proof : Let $$d=gcd(2a+1, 9a+4)$$
Then $$d|2a+1$$ and $$d|9a+4$$
$$2a+1=db$$ and $$9a+4=dc$$
$$ a = frac{db-1}{2}$$and$$a= frac{dc-4}{9}$$
Equating both equations :
$$ 9db-9=2dc-8 $$
$$ d(9b-2c) = 1 $$
$$ 9b-2c = frac{1}{d}$$
Now, since b and c are integers, therefore $frac{1}{d}$ is an integer, i.e d divides 1 and therefore $$gcd(a, b)= d = 1$$.
proof-verification
asked Jan 4 at 15:31
P.JoP.Jo
85
New contributor
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
The question is from Burton's Elementary Number Theory. I want to know if my proof is legible.
Proof : Let $$d=gcd(2a+1, 9a+4)$$
Then $$d|2a+1$$ and $$d|9a+4$$
$$2a+1=db$$ and $$9a+4=dc$$
$$ a = frac{db-1}{2}$$and$$a= frac{dc-4}{9}$$
Equating both equations :
$$ 9db-9=2dc-8 $$
$$ d(9b-2c) = 1 $$
$$ 9b-2c = frac{1}{d}$$
Now, since b and c are integers, therefore $frac{1}{d}$ is an integer, i.e d divides 1 and therefore $$gcd(a, b)= d = 1$$.
proof-verification
proof-verification
asked Jan 4 at 15:31
P.JoP.Jo
85
New contributor
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 4 at 15:31
P.JoP.Jo
85
New contributor
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 4 at 15:31
P.JoP.Jo
85
New contributor
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 4 at 15:31
P.JoP.Jo
85
asked Jan 4 at 15:31
P.JoP.Jo
85
85
New contributor
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
P.Jo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
It's correct. Essentially you eliminated $,a,,$ which can be done more directly as follows: $$bmod d!:, 2a!+!1equiv 0equiv 9a!+!4 Rightarrow color{#c00}0equiv 9(2a!+!1)-2(9a!+!4)equivcolor{#c00} 1 Rightarrow dmid color{#c00}{1!-!0}qquad$$
– Bill Dubuque
Jan 4 at 17:02
@BillDubuque Thanks. I'm sure it's a more direct approach but I'm unfamiliar with modular arithmetic so it had to be something without it.
– P.Jo
Jan 4 at 17:22
We can eliminate congruence notation too! Namely the above means $$dmid 2a!+!1,9a!+!4 Rightarrow dmid 1!=! 9(2a!+!1)-2(9a!+!4)qquad $$ since multiples of $d$ are closed under integral linear combinations.
– Bill Dubuque
Jan 4 at 17:27
@BillDubuque Yeah. That makes perfect sense. But what does it mean to be 'closed under integral linear combinations'?
– P.Jo
Jan 5 at 4:19
@BillDubuque Does it mean that the multiples of d= gcd(a, b) are all the linear combinations of a and b?
– P.Jo
Jan 5 at 4:27
|
show 4 more comments
It's correct. Essentially you eliminated $,a,,$ which can be done more directly as follows: $$bmod d!:, 2a!+!1equiv 0equiv 9a!+!4 Rightarrow color{#c00}0equiv 9(2a!+!1)-2(9a!+!4)equivcolor{#c00} 1 Rightarrow dmid color{#c00}{1!-!0}qquad$$
– Bill Dubuque
Jan 4 at 17:02
@BillDubuque Thanks. I'm sure it's a more direct approach but I'm unfamiliar with modular arithmetic so it had to be something without it.
– P.Jo
Jan 4 at 17:22
We can eliminate congruence notation too! Namely the above means $$dmid 2a!+!1,9a!+!4 Rightarrow dmid 1!=! 9(2a!+!1)-2(9a!+!4)qquad $$ since multiples of $d$ are closed under integral linear combinations.
– Bill Dubuque
Jan 4 at 17:27
@BillDubuque Yeah. That makes perfect sense. But what does it mean to be 'closed under integral linear combinations'?
– P.Jo
Jan 5 at 4:19
@BillDubuque Does it mean that the multiples of d= gcd(a, b) are all the linear combinations of a and b?
– P.Jo
Jan 5 at 4:27
It's correct. Essentially you eliminated $,a,,$ which can be done more directly as follows: $$bmod d!:, 2a!+!1equiv 0equiv 9a!+!4 Rightarrow color{#c00}0equiv 9(2a!+!1)-2(9a!+!4)equivcolor{#c00} 1 Rightarrow dmid color{#c00}{1!-!0}qquad$$
– Bill Dubuque
Jan 4 at 17:02
It's correct. Essentially you eliminated $,a,,$ which can be done more directly as follows: $$bmod d!:, 2a!+!1equiv 0equiv 9a!+!4 Rightarrow color{#c00}0equiv 9(2a!+!1)-2(9a!+!4)equivcolor{#c00} 1 Rightarrow dmid color{#c00}{1!-!0}qquad$$
– Bill Dubuque
Jan 4 at 17:02
@BillDubuque Thanks. I'm sure it's a more direct approach but I'm unfamiliar with modular arithmetic so it had to be something without it.
– P.Jo
Jan 4 at 17:22
@BillDubuque Thanks. I'm sure it's a more direct approach but I'm unfamiliar with modular arithmetic so it had to be something without it.
– P.Jo
Jan 4 at 17:22
We can eliminate congruence notation too! Namely the above means $$dmid 2a!+!1,9a!+!4 Rightarrow dmid 1!=! 9(2a!+!1)-2(9a!+!4)qquad $$ since multiples of $d$ are closed under integral linear combinations.
– Bill Dubuque
Jan 4 at 17:27
We can eliminate congruence notation too! Namely the above means $$dmid 2a!+!1,9a!+!4 Rightarrow dmid 1!=! 9(2a!+!1)-2(9a!+!4)qquad $$ since multiples of $d$ are closed under integral linear combinations.
– Bill Dubuque
Jan 4 at 17:27
@BillDubuque Yeah. That makes perfect sense. But what does it mean to be 'closed under integral linear combinations'?
– P.Jo
Jan 5 at 4:19
@BillDubuque Yeah. That makes perfect sense. But what does it mean to be 'closed under integral linear combinations'?
– P.Jo
Jan 5 at 4:19
@BillDubuque Does it mean that the multiples of d= gcd(a, b) are all the linear combinations of a and b?
– P.Jo
Jan 5 at 4:27
@BillDubuque Does it mean that the multiples of d= gcd(a, b) are all the linear combinations of a and b?
– P.Jo
Jan 5 at 4:27
|
show 4 more comments
3 Answers
3
active
oldest
votes
Seems fine.
Alternatively,
$$9a+4=4(2a+1)+a$$
$$2a+1=2(a)+1$$
Hence,
$$1=(2a+1)-2a=(2a+1)-2(9a+4)+8=9(2a+1)-2(9a+4)$$
That is the greatest common divisor of $2a+1$ and $9a+4$ must divide $1$. Hence the greatest common divisor is $1$.
answered Jan 4 at 15:42
Siong Thye GohSiong Thye Goh
99.9k1465117
What did you do here really?
– Michael Munta
Jan 6 at 10:57
I am using Euclidean algorithm to express the gcd as a combination of the two numbers.
– Siong Thye Goh
Jan 6 at 11:08
Can you please explain how this happens? I know how it works with integers, but not with expressions like these.
– Michael Munta
Jan 6 at 11:16
For the first part, I divide $9a+4$ by $2a+1$ and find that the remainder to be $a$. After which , I divide $2a+1$ by $a$ and obtain a remainder of $1$, then I work backward to substitute $a$ in terms of $9a+4$ and $2a+1$.
– Siong Thye Goh
Jan 6 at 11:21
This is the extended algorithm?
– Michael Munta
Jan 6 at 12:36
|
show 4 more comments
Looks good to me. Some nit picks follow:
A bit of formatting may help readability. For much of your answer you have pairs of equations which belong together, but the pairs which belong together aren't the pairs which appear close to one another.
After "therefore $frac{1}{d}$ is an integer", you can just say "so $d=1$ and we're done". Remember that $d=1$ is the very thing we want to prove, so it's unnecessary to continue with more calculations once you've reached that conclusion.
And personally I would probably have used the Euclidean algorithm instead.
answered Jan 4 at 15:39
ArthurArthur
111k7106188
The formatting is sloppy indeed. Thanks for the 'nitpicks'. I seem to lack the knowledge of the Euclidean Algorithm since it is the next topic in the book.
– P.Jo
Jan 4 at 16:21
@P.Jo Then it's no wonder you didn't use it. The Euclidean algorithm is basically a way of simplifying the two expressions without changing their $gcd$. If you can simplify until one of them becomes $1$ or $0$ (which always happens if you only have integers, but not necessarily if you have expressions like yours), then you're done. If not, then at least it will be simplified and easier to use alternate methods like yours.
– Arthur
Jan 4 at 16:30
Nice preview before starting. Sounds like it's gonna make this easier.
– P.Jo
Jan 4 at 17:11
add a comment |
Divide $2a+1$ into $9a+4$ giving $9a+4 = 9/2cdot (2a+1) - 1/2$ or $2(9a+4) = 9(2a+1)-1$, or $1= -2(9a+4) + 9(2a+1)$. So each divisor of $9a+4$ and $2a+1$ divides $1$.
answered Jan 4 at 15:39
WuestenfuxWuestenfux
3,7561411
You are dividing $2a+1$ into $9a+4$, not the other way around as you have typed.
– Michael Munta
yesterday
Indeed, you're right. Thanks.
– Wuestenfux
yesterday
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
});
}
});
P.Jo is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3061760%2fgcd2a1-9a4-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
Seems fine.
Alternatively,
$$9a+4=4(2a+1)+a$$
$$2a+1=2(a)+1$$
Hence,
$$1=(2a+1)-2a=(2a+1)-2(9a+4)+8=9(2a+1)-2(9a+4)$$
That is the greatest common divisor of $2a+1$ and $9a+4$ must divide $1$. Hence the greatest common divisor is $1$.
answered Jan 4 at 15:42
Siong Thye GohSiong Thye Goh
99.9k1465117
What did you do here really?
– Michael Munta
Jan 6 at 10:57
I am using Euclidean algorithm to express the gcd as a combination of the two numbers.
– Siong Thye Goh
Jan 6 at 11:08
Can you please explain how this happens? I know how it works with integers, but not with expressions like these.
– Michael Munta
Jan 6 at 11:16
For the first part, I divide $9a+4$ by $2a+1$ and find that the remainder to be $a$. After which , I divide $2a+1$ by $a$ and obtain a remainder of $1$, then I work backward to substitute $a$ in terms of $9a+4$ and $2a+1$.
– Siong Thye Goh
Jan 6 at 11:21
This is the extended algorithm?
– Michael Munta
Jan 6 at 12:36
|
show 4 more comments
Seems fine.
Alternatively,
$$9a+4=4(2a+1)+a$$
$$2a+1=2(a)+1$$
Hence,
$$1=(2a+1)-2a=(2a+1)-2(9a+4)+8=9(2a+1)-2(9a+4)$$
That is the greatest common divisor of $2a+1$ and $9a+4$ must divide $1$. Hence the greatest common divisor is $1$.
answered Jan 4 at 15:42
Siong Thye GohSiong Thye Goh
99.9k1465117
What did you do here really?
– Michael Munta
Jan 6 at 10:57
I am using Euclidean algorithm to express the gcd as a combination of the two numbers.
– Siong Thye Goh
Jan 6 at 11:08
Can you please explain how this happens? I know how it works with integers, but not with expressions like these.
– Michael Munta
Jan 6 at 11:16
For the first part, I divide $9a+4$ by $2a+1$ and find that the remainder to be $a$. After which , I divide $2a+1$ by $a$ and obtain a remainder of $1$, then I work backward to substitute $a$ in terms of $9a+4$ and $2a+1$.
– Siong Thye Goh
Jan 6 at 11:21
This is the extended algorithm?
– Michael Munta
Jan 6 at 12:36
|
show 4 more comments
Seems fine.
Alternatively,
$$9a+4=4(2a+1)+a$$
$$2a+1=2(a)+1$$
Hence,
$$1=(2a+1)-2a=(2a+1)-2(9a+4)+8=9(2a+1)-2(9a+4)$$
That is the greatest common divisor of $2a+1$ and $9a+4$ must divide $1$. Hence the greatest common divisor is $1$.
answered Jan 4 at 15:42
Siong Thye GohSiong Thye Goh
99.9k1465117
Seems fine.
Alternatively,
$$9a+4=4(2a+1)+a$$
$$2a+1=2(a)+1$$
Hence,
$$1=(2a+1)-2a=(2a+1)-2(9a+4)+8=9(2a+1)-2(9a+4)$$
That is the greatest common divisor of $2a+1$ and $9a+4$ must divide $1$. Hence the greatest common divisor is $1$.
answered Jan 4 at 15:42
Siong Thye GohSiong Thye Goh
99.9k1465117
answered Jan 4 at 15:42
Siong Thye GohSiong Thye Goh
99.9k1465117
answered Jan 4 at 15:42
Siong Thye GohSiong Thye Goh
99.9k1465117
answered Jan 4 at 15:42
Siong Thye GohSiong Thye Goh
99.9k1465117
99.9k1465117
What did you do here really?
– Michael Munta
Jan 6 at 10:57
I am using Euclidean algorithm to express the gcd as a combination of the two numbers.
– Siong Thye Goh
Jan 6 at 11:08
Can you please explain how this happens? I know how it works with integers, but not with expressions like these.
– Michael Munta
Jan 6 at 11:16
For the first part, I divide $9a+4$ by $2a+1$ and find that the remainder to be $a$. After which , I divide $2a+1$ by $a$ and obtain a remainder of $1$, then I work backward to substitute $a$ in terms of $9a+4$ and $2a+1$.
– Siong Thye Goh
Jan 6 at 11:21
This is the extended algorithm?
– Michael Munta
Jan 6 at 12:36
|
show 4 more comments
What did you do here really?
– Michael Munta
Jan 6 at 10:57
I am using Euclidean algorithm to express the gcd as a combination of the two numbers.
– Siong Thye Goh
Jan 6 at 11:08
Can you please explain how this happens? I know how it works with integers, but not with expressions like these.
– Michael Munta
Jan 6 at 11:16
For the first part, I divide $9a+4$ by $2a+1$ and find that the remainder to be $a$. After which , I divide $2a+1$ by $a$ and obtain a remainder of $1$, then I work backward to substitute $a$ in terms of $9a+4$ and $2a+1$.
– Siong Thye Goh
Jan 6 at 11:21
This is the extended algorithm?
– Michael Munta
Jan 6 at 12:36
What did you do here really?
– Michael Munta
Jan 6 at 10:57
What did you do here really?
– Michael Munta
Jan 6 at 10:57
I am using Euclidean algorithm to express the gcd as a combination of the two numbers.
– Siong Thye Goh
Jan 6 at 11:08
I am using Euclidean algorithm to express the gcd as a combination of the two numbers.
– Siong Thye Goh
Jan 6 at 11:08
Can you please explain how this happens? I know how it works with integers, but not with expressions like these.
– Michael Munta
Jan 6 at 11:16
Can you please explain how this happens? I know how it works with integers, but not with expressions like these.
– Michael Munta
Jan 6 at 11:16
For the first part, I divide $9a+4$ by $2a+1$ and find that the remainder to be $a$. After which , I divide $2a+1$ by $a$ and obtain a remainder of $1$, then I work backward to substitute $a$ in terms of $9a+4$ and $2a+1$.
– Siong Thye Goh
Jan 6 at 11:21
For the first part, I divide $9a+4$ by $2a+1$ and find that the remainder to be $a$. After which , I divide $2a+1$ by $a$ and obtain a remainder of $1$, then I work backward to substitute $a$ in terms of $9a+4$ and $2a+1$.
– Siong Thye Goh
Jan 6 at 11:21
This is the extended algorithm?
– Michael Munta
Jan 6 at 12:36
This is the extended algorithm?
– Michael Munta
Jan 6 at 12:36
|
show 4 more comments
Looks good to me. Some nit picks follow:
A bit of formatting may help readability. For much of your answer you have pairs of equations which belong together, but the pairs which belong together aren't the pairs which appear close to one another.
After "therefore $frac{1}{d}$ is an integer", you can just say "so $d=1$ and we're done". Remember that $d=1$ is the very thing we want to prove, so it's unnecessary to continue with more calculations once you've reached that conclusion.
And personally I would probably have used the Euclidean algorithm instead.
answered Jan 4 at 15:39
ArthurArthur
111k7106188
The formatting is sloppy indeed. Thanks for the 'nitpicks'. I seem to lack the knowledge of the Euclidean Algorithm since it is the next topic in the book.
– P.Jo
Jan 4 at 16:21
@P.Jo Then it's no wonder you didn't use it. The Euclidean algorithm is basically a way of simplifying the two expressions without changing their $gcd$. If you can simplify until one of them becomes $1$ or $0$ (which always happens if you only have integers, but not necessarily if you have expressions like yours), then you're done. If not, then at least it will be simplified and easier to use alternate methods like yours.
– Arthur
Jan 4 at 16:30
Nice preview before starting. Sounds like it's gonna make this easier.
– P.Jo
Jan 4 at 17:11
add a comment |
Looks good to me. Some nit picks follow:
A bit of formatting may help readability. For much of your answer you have pairs of equations which belong together, but the pairs which belong together aren't the pairs which appear close to one another.
After "therefore $frac{1}{d}$ is an integer", you can just say "so $d=1$ and we're done". Remember that $d=1$ is the very thing we want to prove, so it's unnecessary to continue with more calculations once you've reached that conclusion.
And personally I would probably have used the Euclidean algorithm instead.
answered Jan 4 at 15:39
ArthurArthur
111k7106188
The formatting is sloppy indeed. Thanks for the 'nitpicks'. I seem to lack the knowledge of the Euclidean Algorithm since it is the next topic in the book.
– P.Jo
Jan 4 at 16:21
@P.Jo Then it's no wonder you didn't use it. The Euclidean algorithm is basically a way of simplifying the two expressions without changing their $gcd$. If you can simplify until one of them becomes $1$ or $0$ (which always happens if you only have integers, but not necessarily if you have expressions like yours), then you're done. If not, then at least it will be simplified and easier to use alternate methods like yours.
– Arthur
Jan 4 at 16:30
Nice preview before starting. Sounds like it's gonna make this easier.
– P.Jo
Jan 4 at 17:11
add a comment |
Looks good to me. Some nit picks follow:
A bit of formatting may help readability. For much of your answer you have pairs of equations which belong together, but the pairs which belong together aren't the pairs which appear close to one another.
After "therefore $frac{1}{d}$ is an integer", you can just say "so $d=1$ and we're done". Remember that $d=1$ is the very thing we want to prove, so it's unnecessary to continue with more calculations once you've reached that conclusion.
And personally I would probably have used the Euclidean algorithm instead.
answered Jan 4 at 15:39
ArthurArthur
111k7106188
Looks good to me. Some nit picks follow:
A bit of formatting may help readability. For much of your answer you have pairs of equations which belong together, but the pairs which belong together aren't the pairs which appear close to one another.
After "therefore $frac{1}{d}$ is an integer", you can just say "so $d=1$ and we're done". Remember that $d=1$ is the very thing we want to prove, so it's unnecessary to continue with more calculations once you've reached that conclusion.
And personally I would probably have used the Euclidean algorithm instead.
answered Jan 4 at 15:39
ArthurArthur
111k7106188
answered Jan 4 at 15:39
ArthurArthur
111k7106188
answered Jan 4 at 15:39
ArthurArthur
111k7106188
answered Jan 4 at 15:39
ArthurArthur
111k7106188
111k7106188
The formatting is sloppy indeed. Thanks for the 'nitpicks'. I seem to lack the knowledge of the Euclidean Algorithm since it is the next topic in the book.
– P.Jo
Jan 4 at 16:21
@P.Jo Then it's no wonder you didn't use it. The Euclidean algorithm is basically a way of simplifying the two expressions without changing their $gcd$. If you can simplify until one of them becomes $1$ or $0$ (which always happens if you only have integers, but not necessarily if you have expressions like yours), then you're done. If not, then at least it will be simplified and easier to use alternate methods like yours.
– Arthur
Jan 4 at 16:30
Nice preview before starting. Sounds like it's gonna make this easier.
– P.Jo
Jan 4 at 17:11
add a comment |
The formatting is sloppy indeed. Thanks for the 'nitpicks'. I seem to lack the knowledge of the Euclidean Algorithm since it is the next topic in the book.
– P.Jo
Jan 4 at 16:21
@P.Jo Then it's no wonder you didn't use it. The Euclidean algorithm is basically a way of simplifying the two expressions without changing their $gcd$. If you can simplify until one of them becomes $1$ or $0$ (which always happens if you only have integers, but not necessarily if you have expressions like yours), then you're done. If not, then at least it will be simplified and easier to use alternate methods like yours.
– Arthur
Jan 4 at 16:30
Nice preview before starting. Sounds like it's gonna make this easier.
– P.Jo
Jan 4 at 17:11
The formatting is sloppy indeed. Thanks for the 'nitpicks'. I seem to lack the knowledge of the Euclidean Algorithm since it is the next topic in the book.
– P.Jo
Jan 4 at 16:21
The formatting is sloppy indeed. Thanks for the 'nitpicks'. I seem to lack the knowledge of the Euclidean Algorithm since it is the next topic in the book.
– P.Jo
Jan 4 at 16:21
@P.Jo Then it's no wonder you didn't use it. The Euclidean algorithm is basically a way of simplifying the two expressions without changing their $gcd$. If you can simplify until one of them becomes $1$ or $0$ (which always happens if you only have integers, but not necessarily if you have expressions like yours), then you're done. If not, then at least it will be simplified and easier to use alternate methods like yours.
– Arthur
Jan 4 at 16:30
@P.Jo Then it's no wonder you didn't use it. The Euclidean algorithm is basically a way of simplifying the two expressions without changing their $gcd$. If you can simplify until one of them becomes $1$ or $0$ (which always happens if you only have integers, but not necessarily if you have expressions like yours), then you're done. If not, then at least it will be simplified and easier to use alternate methods like yours.
– Arthur
Jan 4 at 16:30
Nice preview before starting. Sounds like it's gonna make this easier.
– P.Jo
Jan 4 at 17:11
Nice preview before starting. Sounds like it's gonna make this easier.
– P.Jo
Jan 4 at 17:11
add a comment |
Divide $2a+1$ into $9a+4$ giving $9a+4 = 9/2cdot (2a+1) - 1/2$ or $2(9a+4) = 9(2a+1)-1$, or $1= -2(9a+4) + 9(2a+1)$. So each divisor of $9a+4$ and $2a+1$ divides $1$.
answered Jan 4 at 15:39
WuestenfuxWuestenfux
3,7561411
You are dividing $2a+1$ into $9a+4$, not the other way around as you have typed.
– Michael Munta
yesterday
Indeed, you're right. Thanks.
– Wuestenfux
yesterday
add a comment |
Divide $2a+1$ into $9a+4$ giving $9a+4 = 9/2cdot (2a+1) - 1/2$ or $2(9a+4) = 9(2a+1)-1$, or $1= -2(9a+4) + 9(2a+1)$. So each divisor of $9a+4$ and $2a+1$ divides $1$.
answered Jan 4 at 15:39
WuestenfuxWuestenfux
3,7561411
You are dividing $2a+1$ into $9a+4$, not the other way around as you have typed.
– Michael Munta
yesterday
Indeed, you're right. Thanks.
– Wuestenfux
yesterday
add a comment |
Divide $2a+1$ into $9a+4$ giving $9a+4 = 9/2cdot (2a+1) - 1/2$ or $2(9a+4) = 9(2a+1)-1$, or $1= -2(9a+4) + 9(2a+1)$. So each divisor of $9a+4$ and $2a+1$ divides $1$.
answered Jan 4 at 15:39
WuestenfuxWuestenfux
3,7561411
Divide $2a+1$ into $9a+4$ giving $9a+4 = 9/2cdot (2a+1) - 1/2$ or $2(9a+4) = 9(2a+1)-1$, or $1= -2(9a+4) + 9(2a+1)$. So each divisor of $9a+4$ and $2a+1$ divides $1$.
answered Jan 4 at 15:39
WuestenfuxWuestenfux
3,7561411
edited yesterday
answered Jan 4 at 15:39
WuestenfuxWuestenfux
3,7561411
answered Jan 4 at 15:39
WuestenfuxWuestenfux
3,7561411
answered Jan 4 at 15:39
WuestenfuxWuestenfux
3,7561411
3,7561411
You are dividing $2a+1$ into $9a+4$, not the other way around as you have typed.
– Michael Munta
yesterday
Indeed, you're right. Thanks.
– Wuestenfux
yesterday
add a comment |
You are dividing $2a+1$ into $9a+4$, not the other way around as you have typed.
– Michael Munta
yesterday
Indeed, you're right. Thanks.
– Wuestenfux
yesterday
You are dividing $2a+1$ into $9a+4$, not the other way around as you have typed.
– Michael Munta
yesterday
You are dividing $2a+1$ into $9a+4$, not the other way around as you have typed.
– Michael Munta
yesterday
Indeed, you're right. Thanks.
– Wuestenfux
yesterday
Indeed, you're right. Thanks.
– Wuestenfux
yesterday
add a comment |
P.Jo is a new contributor. Be nice, and check out our Code of Conduct.
P.Jo is a new contributor. Be nice, and check out our Code of Conduct.
P.Jo is a new contributor. Be nice, and check out our Code of Conduct.
P.Jo is a new contributor. Be nice, and check out our Code of Conduct.
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3061760%2fgcd2a1-9a4-1%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
It's correct. Essentially you eliminated $,a,,$ which can be done more directly as follows: $$bmod d!:, 2a!+!1equiv 0equiv 9a!+!4 Rightarrow color{#c00}0equiv 9(2a!+!1)-2(9a!+!4)equivcolor{#c00} 1 Rightarrow dmid color{#c00}{1!-!0}qquad$$
– Bill Dubuque
Jan 4 at 17:02
@BillDubuque Thanks. I'm sure it's a more direct approach but I'm unfamiliar with modular arithmetic so it had to be something without it.
– P.Jo
Jan 4 at 17:22
We can eliminate congruence notation too! Namely the above means $$dmid 2a!+!1,9a!+!4 Rightarrow dmid 1!=! 9(2a!+!1)-2(9a!+!4)qquad $$ since multiples of $d$ are closed under integral linear combinations.
– Bill Dubuque
Jan 4 at 17:27
@BillDubuque Yeah. That makes perfect sense. But what does it mean to be 'closed under integral linear combinations'?
– P.Jo
Jan 5 at 4:19
@BillDubuque Does it mean that the multiples of d= gcd(a, b) are all the linear combinations of a and b?
– P.Jo
Jan 5 at 4:27