Mixing
greatest common divisor of two elements
$begingroup$
Find all possible values of GCD(4n + 4, 6n + 3) for naturals n
and prove that there are no others
3·(4n + 4) - 2·(6n + 3) = 6,
whence the desired GCD is a divisor 6.
But 6n + 3 is odd, so only 1 and 3 remain.
n=1 and n=2 are examples for GCD=1 and GCD=3
is the solution correct ?
any other way to solve this ?
greatest-common-divisor
asked Jan 2 at 16:50
Mustafa AzzurriMustafa Azzurri
92
$endgroup$
add a comment |
$begingroup$
Find all possible values of GCD(4n + 4, 6n + 3) for naturals n
and prove that there are no others
3·(4n + 4) - 2·(6n + 3) = 6,
whence the desired GCD is a divisor 6.
But 6n + 3 is odd, so only 1 and 3 remain.
n=1 and n=2 are examples for GCD=1 and GCD=3
is the solution correct ?
any other way to solve this ?
greatest-common-divisor
asked Jan 2 at 16:50
Mustafa AzzurriMustafa Azzurri
92
$endgroup$
add a comment |
$begingroup$
Find all possible values of GCD(4n + 4, 6n + 3) for naturals n
and prove that there are no others
3·(4n + 4) - 2·(6n + 3) = 6,
whence the desired GCD is a divisor 6.
But 6n + 3 is odd, so only 1 and 3 remain.
n=1 and n=2 are examples for GCD=1 and GCD=3
is the solution correct ?
any other way to solve this ?
greatest-common-divisor
asked Jan 2 at 16:50
Mustafa AzzurriMustafa Azzurri
92
$endgroup$
Find all possible values of GCD(4n + 4, 6n + 3) for naturals n
and prove that there are no others
3·(4n + 4) - 2·(6n + 3) = 6,
whence the desired GCD is a divisor 6.
But 6n + 3 is odd, so only 1 and 3 remain.
n=1 and n=2 are examples for GCD=1 and GCD=3
is the solution correct ?
any other way to solve this ?
greatest-common-divisor
greatest-common-divisor
asked Jan 2 at 16:50
Mustafa AzzurriMustafa Azzurri
92
asked Jan 2 at 16:50
Mustafa AzzurriMustafa Azzurri
92
asked Jan 2 at 16:50
Mustafa AzzurriMustafa Azzurri
92
asked Jan 2 at 16:50
Mustafa AzzurriMustafa Azzurri
92
asked Jan 2 at 16:50
Mustafa AzzurriMustafa Azzurri
92
92
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
This is correct. A slightly different way to solve it is by observing that
$$ (4n+4,6n+3) = (4n+4,2n-1) = (6,2n-1) = (3,2n-1). $$
answered Jan 2 at 17:23
W-t-PW-t-P
64559
$endgroup$
$begingroup$
thanks for answering
$endgroup$
– Mustafa Azzurri
Jan 2 at 17:50
add a comment |
$begingroup$
Your way is correct.
Other way.
$gcd(4n+4, 6n+3) = gcd(4n+4, (6n+3) - (4n+4)) =$
$gcd (4n+4, 2n -1) = gcd(4n+4 - 2(2n-1), 2n-1)=$
$gcd (6, 2n- 1) = $
... Now two things should be apparent. $2n-1$ is odd and $6$ is even so the prime factor $2$ of $6$ will not be a factor of $2n-1$. And Lemma: if $gcd(j,b) = 1$ then $gcd(j*a, b) = gcd(a,b)$. That can be easily proven many ways.
So $gcd(2*3, 2n-1) = gcd(3,2n-1)$. Which is equal to $3$ if $3|2n-1$ which can happen if $2n-1 equiv 0 pmod 3$ or $nequiv 2 pmod 3$. Or is equal to $1$ if $3not mid 2n-1$ which can happen if $nequiv 0, 1 pmod 3$.
And another way:
$gcd(4n+4, 6n+3) = gcd(4(n+1), 3(2n+1)=$.
... as $3(2n+1)$ is odd....
$gcd(n+1, 3(2n+1))$.
Now $gcd(n+1, 2n+1) = gcd(n+1, (2n+1)-(n+1) = gcd(n+1, n) = gcd(n+1 - n, n) = gcd(1, n) = 1$.
So... $gcd(n+1, 3(2n+1)) = gcd(n+1, 3)$.
Which is $3$ if $3|n+1$ and is $1$ if not.
Perhaps we can retrofit this as
$gcd(3,n+1) = {1,3}$
$gcd(2n+1, n+1) = 1$ so
$gcd(3(2n+1), n+1) = gcd(3,n+1)$.
$gcd(3(2n+1), 2) = 1$ so
$gcd(3(2n+1), 2^2(n+1)) = gcd(3,n+1)$.
All comes down to "casting out" relatively prime factors.
answered Jan 2 at 18:10
fleabloodfleablood
68.7k22685
$endgroup$
add a comment |
$begingroup$
$begin{align}
(color{#c00}4(n!+!1),,3(2n!+!1)), &=, (n!+!1,,3(color{#0a0}{2n!+!1})) {rm by} (color{#c00}4,3)=1=(color{#c00}4,2n!+!1)\[.2em]
&=, (n!+!1,3) {rm by} bmod n!+!1!: nequiv -1,Rightarrow, color{#0a0}{2n!+!1equiv -1}
end{align}$
Remark $ $ Your argument that the gcd $,dmid color{#c00}3$ is correct, but we can take it further as follows
$$d = (4n!+!4,6n!+!3) = (underbrace{4n!+!4,6n!+!3}_{large{rm reduce} bmod color{#c00}3},color{#c00}3) = (n!+!1,0,3)qquad$$
Therefore $, d = 3,$ if $,3mid n!+!1,,$ else $,d= 1$
answered Jan 2 at 19:07
Bill DubuqueBill Dubuque
209k29190633
$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%2f3059698%2fgreatest-common-divisor-of-two-elements%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
$begingroup$
This is correct. A slightly different way to solve it is by observing that
$$ (4n+4,6n+3) = (4n+4,2n-1) = (6,2n-1) = (3,2n-1). $$
answered Jan 2 at 17:23
W-t-PW-t-P
64559
$endgroup$
$begingroup$
thanks for answering
$endgroup$
– Mustafa Azzurri
Jan 2 at 17:50
add a comment |
$begingroup$
This is correct. A slightly different way to solve it is by observing that
$$ (4n+4,6n+3) = (4n+4,2n-1) = (6,2n-1) = (3,2n-1). $$
answered Jan 2 at 17:23
W-t-PW-t-P
64559
$endgroup$
$begingroup$
thanks for answering
$endgroup$
– Mustafa Azzurri
Jan 2 at 17:50
add a comment |
$begingroup$
This is correct. A slightly different way to solve it is by observing that
$$ (4n+4,6n+3) = (4n+4,2n-1) = (6,2n-1) = (3,2n-1). $$
answered Jan 2 at 17:23
W-t-PW-t-P
64559
$endgroup$
This is correct. A slightly different way to solve it is by observing that
$$ (4n+4,6n+3) = (4n+4,2n-1) = (6,2n-1) = (3,2n-1). $$
answered Jan 2 at 17:23
W-t-PW-t-P
64559
answered Jan 2 at 17:23
W-t-PW-t-P
64559
answered Jan 2 at 17:23
W-t-PW-t-P
64559
answered Jan 2 at 17:23
W-t-PW-t-P
64559
64559
$begingroup$
thanks for answering
$endgroup$
– Mustafa Azzurri
Jan 2 at 17:50
add a comment |
$begingroup$
thanks for answering
$endgroup$
– Mustafa Azzurri
Jan 2 at 17:50
$begingroup$
thanks for answering
$endgroup$
– Mustafa Azzurri
Jan 2 at 17:50
$begingroup$
thanks for answering
$endgroup$
– Mustafa Azzurri
Jan 2 at 17:50
add a comment |
$begingroup$
Your way is correct.
Other way.
$gcd(4n+4, 6n+3) = gcd(4n+4, (6n+3) - (4n+4)) =$
$gcd (4n+4, 2n -1) = gcd(4n+4 - 2(2n-1), 2n-1)=$
$gcd (6, 2n- 1) = $
... Now two things should be apparent. $2n-1$ is odd and $6$ is even so the prime factor $2$ of $6$ will not be a factor of $2n-1$. And Lemma: if $gcd(j,b) = 1$ then $gcd(j*a, b) = gcd(a,b)$. That can be easily proven many ways.
So $gcd(2*3, 2n-1) = gcd(3,2n-1)$. Which is equal to $3$ if $3|2n-1$ which can happen if $2n-1 equiv 0 pmod 3$ or $nequiv 2 pmod 3$. Or is equal to $1$ if $3not mid 2n-1$ which can happen if $nequiv 0, 1 pmod 3$.
And another way:
$gcd(4n+4, 6n+3) = gcd(4(n+1), 3(2n+1)=$.
... as $3(2n+1)$ is odd....
$gcd(n+1, 3(2n+1))$.
Now $gcd(n+1, 2n+1) = gcd(n+1, (2n+1)-(n+1) = gcd(n+1, n) = gcd(n+1 - n, n) = gcd(1, n) = 1$.
So... $gcd(n+1, 3(2n+1)) = gcd(n+1, 3)$.
Which is $3$ if $3|n+1$ and is $1$ if not.
Perhaps we can retrofit this as
$gcd(3,n+1) = {1,3}$
$gcd(2n+1, n+1) = 1$ so
$gcd(3(2n+1), n+1) = gcd(3,n+1)$.
$gcd(3(2n+1), 2) = 1$ so
$gcd(3(2n+1), 2^2(n+1)) = gcd(3,n+1)$.
All comes down to "casting out" relatively prime factors.
answered Jan 2 at 18:10
fleabloodfleablood
68.7k22685
$endgroup$
add a comment |
$begingroup$
Your way is correct.
Other way.
$gcd(4n+4, 6n+3) = gcd(4n+4, (6n+3) - (4n+4)) =$
$gcd (4n+4, 2n -1) = gcd(4n+4 - 2(2n-1), 2n-1)=$
$gcd (6, 2n- 1) = $
... Now two things should be apparent. $2n-1$ is odd and $6$ is even so the prime factor $2$ of $6$ will not be a factor of $2n-1$. And Lemma: if $gcd(j,b) = 1$ then $gcd(j*a, b) = gcd(a,b)$. That can be easily proven many ways.
So $gcd(2*3, 2n-1) = gcd(3,2n-1)$. Which is equal to $3$ if $3|2n-1$ which can happen if $2n-1 equiv 0 pmod 3$ or $nequiv 2 pmod 3$. Or is equal to $1$ if $3not mid 2n-1$ which can happen if $nequiv 0, 1 pmod 3$.
And another way:
$gcd(4n+4, 6n+3) = gcd(4(n+1), 3(2n+1)=$.
... as $3(2n+1)$ is odd....
$gcd(n+1, 3(2n+1))$.
Now $gcd(n+1, 2n+1) = gcd(n+1, (2n+1)-(n+1) = gcd(n+1, n) = gcd(n+1 - n, n) = gcd(1, n) = 1$.
So... $gcd(n+1, 3(2n+1)) = gcd(n+1, 3)$.
Which is $3$ if $3|n+1$ and is $1$ if not.
Perhaps we can retrofit this as
$gcd(3,n+1) = {1,3}$
$gcd(2n+1, n+1) = 1$ so
$gcd(3(2n+1), n+1) = gcd(3,n+1)$.
$gcd(3(2n+1), 2) = 1$ so
$gcd(3(2n+1), 2^2(n+1)) = gcd(3,n+1)$.
All comes down to "casting out" relatively prime factors.
answered Jan 2 at 18:10
fleabloodfleablood
68.7k22685
$endgroup$
add a comment |
$begingroup$
Your way is correct.
Other way.
$gcd(4n+4, 6n+3) = gcd(4n+4, (6n+3) - (4n+4)) =$
$gcd (4n+4, 2n -1) = gcd(4n+4 - 2(2n-1), 2n-1)=$
$gcd (6, 2n- 1) = $
... Now two things should be apparent. $2n-1$ is odd and $6$ is even so the prime factor $2$ of $6$ will not be a factor of $2n-1$. And Lemma: if $gcd(j,b) = 1$ then $gcd(j*a, b) = gcd(a,b)$. That can be easily proven many ways.
So $gcd(2*3, 2n-1) = gcd(3,2n-1)$. Which is equal to $3$ if $3|2n-1$ which can happen if $2n-1 equiv 0 pmod 3$ or $nequiv 2 pmod 3$. Or is equal to $1$ if $3not mid 2n-1$ which can happen if $nequiv 0, 1 pmod 3$.
And another way:
$gcd(4n+4, 6n+3) = gcd(4(n+1), 3(2n+1)=$.
... as $3(2n+1)$ is odd....
$gcd(n+1, 3(2n+1))$.
Now $gcd(n+1, 2n+1) = gcd(n+1, (2n+1)-(n+1) = gcd(n+1, n) = gcd(n+1 - n, n) = gcd(1, n) = 1$.
So... $gcd(n+1, 3(2n+1)) = gcd(n+1, 3)$.
Which is $3$ if $3|n+1$ and is $1$ if not.
Perhaps we can retrofit this as
$gcd(3,n+1) = {1,3}$
$gcd(2n+1, n+1) = 1$ so
$gcd(3(2n+1), n+1) = gcd(3,n+1)$.
$gcd(3(2n+1), 2) = 1$ so
$gcd(3(2n+1), 2^2(n+1)) = gcd(3,n+1)$.
All comes down to "casting out" relatively prime factors.
answered Jan 2 at 18:10
fleabloodfleablood
68.7k22685
$endgroup$
Your way is correct.
Other way.
$gcd(4n+4, 6n+3) = gcd(4n+4, (6n+3) - (4n+4)) =$
$gcd (4n+4, 2n -1) = gcd(4n+4 - 2(2n-1), 2n-1)=$
$gcd (6, 2n- 1) = $
... Now two things should be apparent. $2n-1$ is odd and $6$ is even so the prime factor $2$ of $6$ will not be a factor of $2n-1$. And Lemma: if $gcd(j,b) = 1$ then $gcd(j*a, b) = gcd(a,b)$. That can be easily proven many ways.
So $gcd(2*3, 2n-1) = gcd(3,2n-1)$. Which is equal to $3$ if $3|2n-1$ which can happen if $2n-1 equiv 0 pmod 3$ or $nequiv 2 pmod 3$. Or is equal to $1$ if $3not mid 2n-1$ which can happen if $nequiv 0, 1 pmod 3$.
And another way:
$gcd(4n+4, 6n+3) = gcd(4(n+1), 3(2n+1)=$.
... as $3(2n+1)$ is odd....
$gcd(n+1, 3(2n+1))$.
Now $gcd(n+1, 2n+1) = gcd(n+1, (2n+1)-(n+1) = gcd(n+1, n) = gcd(n+1 - n, n) = gcd(1, n) = 1$.
So... $gcd(n+1, 3(2n+1)) = gcd(n+1, 3)$.
Which is $3$ if $3|n+1$ and is $1$ if not.
Perhaps we can retrofit this as
$gcd(3,n+1) = {1,3}$
$gcd(2n+1, n+1) = 1$ so
$gcd(3(2n+1), n+1) = gcd(3,n+1)$.
$gcd(3(2n+1), 2) = 1$ so
$gcd(3(2n+1), 2^2(n+1)) = gcd(3,n+1)$.
All comes down to "casting out" relatively prime factors.
answered Jan 2 at 18:10
fleabloodfleablood
68.7k22685
answered Jan 2 at 18:10
fleabloodfleablood
68.7k22685
answered Jan 2 at 18:10
fleabloodfleablood
68.7k22685
answered Jan 2 at 18:10
fleabloodfleablood
68.7k22685
68.7k22685
add a comment |
add a comment |
$begingroup$
$begin{align}
(color{#c00}4(n!+!1),,3(2n!+!1)), &=, (n!+!1,,3(color{#0a0}{2n!+!1})) {rm by} (color{#c00}4,3)=1=(color{#c00}4,2n!+!1)\[.2em]
&=, (n!+!1,3) {rm by} bmod n!+!1!: nequiv -1,Rightarrow, color{#0a0}{2n!+!1equiv -1}
end{align}$
Remark $ $ Your argument that the gcd $,dmid color{#c00}3$ is correct, but we can take it further as follows
$$d = (4n!+!4,6n!+!3) = (underbrace{4n!+!4,6n!+!3}_{large{rm reduce} bmod color{#c00}3},color{#c00}3) = (n!+!1,0,3)qquad$$
Therefore $, d = 3,$ if $,3mid n!+!1,,$ else $,d= 1$
answered Jan 2 at 19:07
Bill DubuqueBill Dubuque
209k29190633
$endgroup$
add a comment |
$begingroup$
$begin{align}
(color{#c00}4(n!+!1),,3(2n!+!1)), &=, (n!+!1,,3(color{#0a0}{2n!+!1})) {rm by} (color{#c00}4,3)=1=(color{#c00}4,2n!+!1)\[.2em]
&=, (n!+!1,3) {rm by} bmod n!+!1!: nequiv -1,Rightarrow, color{#0a0}{2n!+!1equiv -1}
end{align}$
Remark $ $ Your argument that the gcd $,dmid color{#c00}3$ is correct, but we can take it further as follows
$$d = (4n!+!4,6n!+!3) = (underbrace{4n!+!4,6n!+!3}_{large{rm reduce} bmod color{#c00}3},color{#c00}3) = (n!+!1,0,3)qquad$$
Therefore $, d = 3,$ if $,3mid n!+!1,,$ else $,d= 1$
answered Jan 2 at 19:07
Bill DubuqueBill Dubuque
209k29190633
$endgroup$
add a comment |
$begingroup$
$begin{align}
(color{#c00}4(n!+!1),,3(2n!+!1)), &=, (n!+!1,,3(color{#0a0}{2n!+!1})) {rm by} (color{#c00}4,3)=1=(color{#c00}4,2n!+!1)\[.2em]
&=, (n!+!1,3) {rm by} bmod n!+!1!: nequiv -1,Rightarrow, color{#0a0}{2n!+!1equiv -1}
end{align}$
Remark $ $ Your argument that the gcd $,dmid color{#c00}3$ is correct, but we can take it further as follows
$$d = (4n!+!4,6n!+!3) = (underbrace{4n!+!4,6n!+!3}_{large{rm reduce} bmod color{#c00}3},color{#c00}3) = (n!+!1,0,3)qquad$$
Therefore $, d = 3,$ if $,3mid n!+!1,,$ else $,d= 1$
answered Jan 2 at 19:07
Bill DubuqueBill Dubuque
209k29190633
$endgroup$
$begin{align}
(color{#c00}4(n!+!1),,3(2n!+!1)), &=, (n!+!1,,3(color{#0a0}{2n!+!1})) {rm by} (color{#c00}4,3)=1=(color{#c00}4,2n!+!1)\[.2em]
&=, (n!+!1,3) {rm by} bmod n!+!1!: nequiv -1,Rightarrow, color{#0a0}{2n!+!1equiv -1}
end{align}$
Remark $ $ Your argument that the gcd $,dmid color{#c00}3$ is correct, but we can take it further as follows
$$d = (4n!+!4,6n!+!3) = (underbrace{4n!+!4,6n!+!3}_{large{rm reduce} bmod color{#c00}3},color{#c00}3) = (n!+!1,0,3)qquad$$
Therefore $, d = 3,$ if $,3mid n!+!1,,$ else $,d= 1$
answered Jan 2 at 19:07
Bill DubuqueBill Dubuque
209k29190633
edited Jan 2 at 19:31
answered Jan 2 at 19:07
Bill DubuqueBill Dubuque
209k29190633
answered Jan 2 at 19:07
Bill DubuqueBill Dubuque
209k29190633
answered Jan 2 at 19:07
Bill DubuqueBill Dubuque
209k29190633
209k29190633
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%2f3059698%2fgreatest-common-divisor-of-two-elements%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
