Mixing
Check divisibility by using $gcd$.
$begingroup$
Let $k$ be an odd integer. As a part of an introductory class to proofs, I wanted to show that the number $k^2 - 1$ is divisible by $8$, and managed to do this by checking that it is congruent modulo $8$. However a student came to me today asking if it was possible to prove the claim by using the greatest common divisor of the two numbers $8$ and $k^2 - 1$, but I couldn't answer them since I have very little experience in number theory and the question came right out of the bushes.
Is there a proof to this claim, that a high school student who is fairly fluent in math could grasp, and that uses the $gcd$ to its advantage somehow? To clarify, the student tried using the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
elementary-number-theory divisibility greatest-common-divisor
asked Jan 17 at 17:50
TheSodesaTheSodesa
1268
$endgroup$
add a comment |
$begingroup$
Let $k$ be an odd integer. As a part of an introductory class to proofs, I wanted to show that the number $k^2 - 1$ is divisible by $8$, and managed to do this by checking that it is congruent modulo $8$. However a student came to me today asking if it was possible to prove the claim by using the greatest common divisor of the two numbers $8$ and $k^2 - 1$, but I couldn't answer them since I have very little experience in number theory and the question came right out of the bushes.
Is there a proof to this claim, that a high school student who is fairly fluent in math could grasp, and that uses the $gcd$ to its advantage somehow? To clarify, the student tried using the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
elementary-number-theory divisibility greatest-common-divisor
asked Jan 17 at 17:50
TheSodesaTheSodesa
1268
$endgroup$
add a comment |
$begingroup$
Let $k$ be an odd integer. As a part of an introductory class to proofs, I wanted to show that the number $k^2 - 1$ is divisible by $8$, and managed to do this by checking that it is congruent modulo $8$. However a student came to me today asking if it was possible to prove the claim by using the greatest common divisor of the two numbers $8$ and $k^2 - 1$, but I couldn't answer them since I have very little experience in number theory and the question came right out of the bushes.
Is there a proof to this claim, that a high school student who is fairly fluent in math could grasp, and that uses the $gcd$ to its advantage somehow? To clarify, the student tried using the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
elementary-number-theory divisibility greatest-common-divisor
asked Jan 17 at 17:50
TheSodesaTheSodesa
1268
$endgroup$
Let $k$ be an odd integer. As a part of an introductory class to proofs, I wanted to show that the number $k^2 - 1$ is divisible by $8$, and managed to do this by checking that it is congruent modulo $8$. However a student came to me today asking if it was possible to prove the claim by using the greatest common divisor of the two numbers $8$ and $k^2 - 1$, but I couldn't answer them since I have very little experience in number theory and the question came right out of the bushes.
Is there a proof to this claim, that a high school student who is fairly fluent in math could grasp, and that uses the $gcd$ to its advantage somehow? To clarify, the student tried using the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
elementary-number-theory divisibility greatest-common-divisor
elementary-number-theory divisibility greatest-common-divisor
asked Jan 17 at 17:50
TheSodesaTheSodesa
1268
asked Jan 17 at 17:50
TheSodesaTheSodesa
1268
edited Jan 17 at 18:15
TheSodesa
asked Jan 17 at 17:50
TheSodesaTheSodesa
1268
asked Jan 17 at 17:50
TheSodesaTheSodesa
1268
asked Jan 17 at 17:50
TheSodesaTheSodesa
1268
1268
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Well $k= 2m+1$ is odd so $k^2 - 1= 4m^2 + 4m$ so $gcd(8,4m^2+4m) = 4gcd(2,m^2+m)= 4gcd(2, m(m+1))$.
And $gcd(2,m(m+1))$ is $2$ if $m(m+1)$ is even and $1$ if $m(m+1)$ is odd.
And either $m$ is even and $m(m+1)$ is even; or $m$ is odd and $m+1$ is even and $m(m+1)$ is even. SO $m(m+1)$ is even.
So $gcd(8,k^2 -1)=gcd(8,4m^2 +4m) = 4gcd(2,m(m+1))=4*2 =8$.
The only real trouble is there's nothing there that couldn't have been explained (and probably easierly) without gcd.
answered Jan 17 at 20:02
fleabloodfleablood
71.5k22686
$endgroup$
add a comment |
$begingroup$
The problem is that you want to demonstrate a specific case of $mmid n$, and $mmid n iff gcd(m,n)=m$. Can you show the RHS other than by showing the LHS?
I think perhaps yes. Many of the ideas in this answer have been alluded to or incorporated in other answers, but have not been assembled in this way.
The one idea not explicitly stated in other answers (it's sort of hinted at) is that for two consecutive even numbers, one contains a single factor of $2$ and the other contains more than one factor of $2$, i.e. $2^j, j ge 2$. Without giving a formal proof, this can be seen from the fact that the even numbers (in order) are just $2$ times the natural numbers. If you look at an even number that is twice an odd number, it has only one factor of $2$. The next larger even number is therefore twice an even number, so it has more than one factor of $2$. The next even number is once again twice an odd number and only has one factor of $2$; and so forth.
$k^2-1=(k+1)(k-1)$ and $(k+1),(k-1)$ are two consecutive even numbers ($k$ is odd and their difference is $2$). Thus one of them can be represented as $2r$ and the other as $2^js$, where $r,s$ are odd and $jge 2$ (we can't know which is represented which way without knowing the value of $k$). Thus $k^2-1=(k+1)(k-1)=2^{j+1}rs$.
$gcd(2^3,2^{j+1}rs)=2^{min(3,(j+1))}$; for $jge 2, min(3,(j+1))=3$. Substituting back, we get $gcd(8,(k^2-1)=8 $QED.
answered Jan 19 at 16:49
Keith BackmanKeith Backman
1,3701812
$endgroup$
add a comment |
$begingroup$
I don't know if this is what you are looking for, but I have another approach without using congruences. Since $k$ is odd integer and if $k = 1$, we have $k^2-1 = 0$ is divisible by $8$, I will assume $k ge 3$. Then, $k^2-1 = (k+1)(k-1)$. Now, if $k ge 3$,
$k+1 ge 4$ and $k-1 ge 2$. Then the product will be always greater than or equal to $8$. Hence, there will always be a factor of $8$ in $k^2 -1$.
answered Jan 17 at 18:03
RickRick
868
$endgroup$
$begingroup$
This is a nice approach, but would definitely like to reward the student for actually reading the book and trying to use something that they previously learned to their advantage, even if it is related to memorizing a formula. I wish I remembered what exactly the student wrote, but they definitely tried to use the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
$endgroup$
– TheSodesa
Jan 17 at 18:10
add a comment |
$begingroup$
You can use it and make an induction to solve the problem.
$(k+2)^2 - 1 - (k^2 - 1) = 4k+4$ is a multiple of $8$ ($k$ is odd) so $gcd ((k+2)^2 -1, 8) = gcd (k^2 -1, 8)$
And the result is trivial for $k = 1$.
answered Jan 17 at 19:06
DLeMeurDLeMeur
3148
$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%2f3077284%2fcheck-divisibility-by-using-gcd%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Well $k= 2m+1$ is odd so $k^2 - 1= 4m^2 + 4m$ so $gcd(8,4m^2+4m) = 4gcd(2,m^2+m)= 4gcd(2, m(m+1))$.
And $gcd(2,m(m+1))$ is $2$ if $m(m+1)$ is even and $1$ if $m(m+1)$ is odd.
And either $m$ is even and $m(m+1)$ is even; or $m$ is odd and $m+1$ is even and $m(m+1)$ is even. SO $m(m+1)$ is even.
So $gcd(8,k^2 -1)=gcd(8,4m^2 +4m) = 4gcd(2,m(m+1))=4*2 =8$.
The only real trouble is there's nothing there that couldn't have been explained (and probably easierly) without gcd.
answered Jan 17 at 20:02
fleabloodfleablood
71.5k22686
$endgroup$
add a comment |
$begingroup$
Well $k= 2m+1$ is odd so $k^2 - 1= 4m^2 + 4m$ so $gcd(8,4m^2+4m) = 4gcd(2,m^2+m)= 4gcd(2, m(m+1))$.
And $gcd(2,m(m+1))$ is $2$ if $m(m+1)$ is even and $1$ if $m(m+1)$ is odd.
And either $m$ is even and $m(m+1)$ is even; or $m$ is odd and $m+1$ is even and $m(m+1)$ is even. SO $m(m+1)$ is even.
So $gcd(8,k^2 -1)=gcd(8,4m^2 +4m) = 4gcd(2,m(m+1))=4*2 =8$.
The only real trouble is there's nothing there that couldn't have been explained (and probably easierly) without gcd.
answered Jan 17 at 20:02
fleabloodfleablood
71.5k22686
$endgroup$
add a comment |
$begingroup$
Well $k= 2m+1$ is odd so $k^2 - 1= 4m^2 + 4m$ so $gcd(8,4m^2+4m) = 4gcd(2,m^2+m)= 4gcd(2, m(m+1))$.
And $gcd(2,m(m+1))$ is $2$ if $m(m+1)$ is even and $1$ if $m(m+1)$ is odd.
And either $m$ is even and $m(m+1)$ is even; or $m$ is odd and $m+1$ is even and $m(m+1)$ is even. SO $m(m+1)$ is even.
So $gcd(8,k^2 -1)=gcd(8,4m^2 +4m) = 4gcd(2,m(m+1))=4*2 =8$.
The only real trouble is there's nothing there that couldn't have been explained (and probably easierly) without gcd.
answered Jan 17 at 20:02
fleabloodfleablood
71.5k22686
$endgroup$
Well $k= 2m+1$ is odd so $k^2 - 1= 4m^2 + 4m$ so $gcd(8,4m^2+4m) = 4gcd(2,m^2+m)= 4gcd(2, m(m+1))$.
And $gcd(2,m(m+1))$ is $2$ if $m(m+1)$ is even and $1$ if $m(m+1)$ is odd.
And either $m$ is even and $m(m+1)$ is even; or $m$ is odd and $m+1$ is even and $m(m+1)$ is even. SO $m(m+1)$ is even.
So $gcd(8,k^2 -1)=gcd(8,4m^2 +4m) = 4gcd(2,m(m+1))=4*2 =8$.
The only real trouble is there's nothing there that couldn't have been explained (and probably easierly) without gcd.
answered Jan 17 at 20:02
fleabloodfleablood
71.5k22686
answered Jan 17 at 20:02
fleabloodfleablood
71.5k22686
answered Jan 17 at 20:02
fleabloodfleablood
71.5k22686
answered Jan 17 at 20:02
fleabloodfleablood
71.5k22686
71.5k22686
add a comment |
add a comment |
$begingroup$
The problem is that you want to demonstrate a specific case of $mmid n$, and $mmid n iff gcd(m,n)=m$. Can you show the RHS other than by showing the LHS?
I think perhaps yes. Many of the ideas in this answer have been alluded to or incorporated in other answers, but have not been assembled in this way.
The one idea not explicitly stated in other answers (it's sort of hinted at) is that for two consecutive even numbers, one contains a single factor of $2$ and the other contains more than one factor of $2$, i.e. $2^j, j ge 2$. Without giving a formal proof, this can be seen from the fact that the even numbers (in order) are just $2$ times the natural numbers. If you look at an even number that is twice an odd number, it has only one factor of $2$. The next larger even number is therefore twice an even number, so it has more than one factor of $2$. The next even number is once again twice an odd number and only has one factor of $2$; and so forth.
$k^2-1=(k+1)(k-1)$ and $(k+1),(k-1)$ are two consecutive even numbers ($k$ is odd and their difference is $2$). Thus one of them can be represented as $2r$ and the other as $2^js$, where $r,s$ are odd and $jge 2$ (we can't know which is represented which way without knowing the value of $k$). Thus $k^2-1=(k+1)(k-1)=2^{j+1}rs$.
$gcd(2^3,2^{j+1}rs)=2^{min(3,(j+1))}$; for $jge 2, min(3,(j+1))=3$. Substituting back, we get $gcd(8,(k^2-1)=8 $QED.
answered Jan 19 at 16:49
Keith BackmanKeith Backman
1,3701812
$endgroup$
add a comment |
$begingroup$
The problem is that you want to demonstrate a specific case of $mmid n$, and $mmid n iff gcd(m,n)=m$. Can you show the RHS other than by showing the LHS?
I think perhaps yes. Many of the ideas in this answer have been alluded to or incorporated in other answers, but have not been assembled in this way.
The one idea not explicitly stated in other answers (it's sort of hinted at) is that for two consecutive even numbers, one contains a single factor of $2$ and the other contains more than one factor of $2$, i.e. $2^j, j ge 2$. Without giving a formal proof, this can be seen from the fact that the even numbers (in order) are just $2$ times the natural numbers. If you look at an even number that is twice an odd number, it has only one factor of $2$. The next larger even number is therefore twice an even number, so it has more than one factor of $2$. The next even number is once again twice an odd number and only has one factor of $2$; and so forth.
$k^2-1=(k+1)(k-1)$ and $(k+1),(k-1)$ are two consecutive even numbers ($k$ is odd and their difference is $2$). Thus one of them can be represented as $2r$ and the other as $2^js$, where $r,s$ are odd and $jge 2$ (we can't know which is represented which way without knowing the value of $k$). Thus $k^2-1=(k+1)(k-1)=2^{j+1}rs$.
$gcd(2^3,2^{j+1}rs)=2^{min(3,(j+1))}$; for $jge 2, min(3,(j+1))=3$. Substituting back, we get $gcd(8,(k^2-1)=8 $QED.
answered Jan 19 at 16:49
Keith BackmanKeith Backman
1,3701812
$endgroup$
add a comment |
$begingroup$
The problem is that you want to demonstrate a specific case of $mmid n$, and $mmid n iff gcd(m,n)=m$. Can you show the RHS other than by showing the LHS?
I think perhaps yes. Many of the ideas in this answer have been alluded to or incorporated in other answers, but have not been assembled in this way.
The one idea not explicitly stated in other answers (it's sort of hinted at) is that for two consecutive even numbers, one contains a single factor of $2$ and the other contains more than one factor of $2$, i.e. $2^j, j ge 2$. Without giving a formal proof, this can be seen from the fact that the even numbers (in order) are just $2$ times the natural numbers. If you look at an even number that is twice an odd number, it has only one factor of $2$. The next larger even number is therefore twice an even number, so it has more than one factor of $2$. The next even number is once again twice an odd number and only has one factor of $2$; and so forth.
$k^2-1=(k+1)(k-1)$ and $(k+1),(k-1)$ are two consecutive even numbers ($k$ is odd and their difference is $2$). Thus one of them can be represented as $2r$ and the other as $2^js$, where $r,s$ are odd and $jge 2$ (we can't know which is represented which way without knowing the value of $k$). Thus $k^2-1=(k+1)(k-1)=2^{j+1}rs$.
$gcd(2^3,2^{j+1}rs)=2^{min(3,(j+1))}$; for $jge 2, min(3,(j+1))=3$. Substituting back, we get $gcd(8,(k^2-1)=8 $QED.
answered Jan 19 at 16:49
Keith BackmanKeith Backman
1,3701812
$endgroup$
The problem is that you want to demonstrate a specific case of $mmid n$, and $mmid n iff gcd(m,n)=m$. Can you show the RHS other than by showing the LHS?
I think perhaps yes. Many of the ideas in this answer have been alluded to or incorporated in other answers, but have not been assembled in this way.
The one idea not explicitly stated in other answers (it's sort of hinted at) is that for two consecutive even numbers, one contains a single factor of $2$ and the other contains more than one factor of $2$, i.e. $2^j, j ge 2$. Without giving a formal proof, this can be seen from the fact that the even numbers (in order) are just $2$ times the natural numbers. If you look at an even number that is twice an odd number, it has only one factor of $2$. The next larger even number is therefore twice an even number, so it has more than one factor of $2$. The next even number is once again twice an odd number and only has one factor of $2$; and so forth.
$k^2-1=(k+1)(k-1)$ and $(k+1),(k-1)$ are two consecutive even numbers ($k$ is odd and their difference is $2$). Thus one of them can be represented as $2r$ and the other as $2^js$, where $r,s$ are odd and $jge 2$ (we can't know which is represented which way without knowing the value of $k$). Thus $k^2-1=(k+1)(k-1)=2^{j+1}rs$.
$gcd(2^3,2^{j+1}rs)=2^{min(3,(j+1))}$; for $jge 2, min(3,(j+1))=3$. Substituting back, we get $gcd(8,(k^2-1)=8 $QED.
answered Jan 19 at 16:49
Keith BackmanKeith Backman
1,3701812
answered Jan 19 at 16:49
Keith BackmanKeith Backman
1,3701812
answered Jan 19 at 16:49
Keith BackmanKeith Backman
1,3701812
answered Jan 19 at 16:49
Keith BackmanKeith Backman
1,3701812
1,3701812
add a comment |
add a comment |
$begingroup$
I don't know if this is what you are looking for, but I have another approach without using congruences. Since $k$ is odd integer and if $k = 1$, we have $k^2-1 = 0$ is divisible by $8$, I will assume $k ge 3$. Then, $k^2-1 = (k+1)(k-1)$. Now, if $k ge 3$,
$k+1 ge 4$ and $k-1 ge 2$. Then the product will be always greater than or equal to $8$. Hence, there will always be a factor of $8$ in $k^2 -1$.
answered Jan 17 at 18:03
RickRick
868
$endgroup$
$begingroup$
This is a nice approach, but would definitely like to reward the student for actually reading the book and trying to use something that they previously learned to their advantage, even if it is related to memorizing a formula. I wish I remembered what exactly the student wrote, but they definitely tried to use the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
$endgroup$
– TheSodesa
Jan 17 at 18:10
add a comment |
$begingroup$
I don't know if this is what you are looking for, but I have another approach without using congruences. Since $k$ is odd integer and if $k = 1$, we have $k^2-1 = 0$ is divisible by $8$, I will assume $k ge 3$. Then, $k^2-1 = (k+1)(k-1)$. Now, if $k ge 3$,
$k+1 ge 4$ and $k-1 ge 2$. Then the product will be always greater than or equal to $8$. Hence, there will always be a factor of $8$ in $k^2 -1$.
answered Jan 17 at 18:03
RickRick
868
$endgroup$
$begingroup$
This is a nice approach, but would definitely like to reward the student for actually reading the book and trying to use something that they previously learned to their advantage, even if it is related to memorizing a formula. I wish I remembered what exactly the student wrote, but they definitely tried to use the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
$endgroup$
– TheSodesa
Jan 17 at 18:10
add a comment |
$begingroup$
I don't know if this is what you are looking for, but I have another approach without using congruences. Since $k$ is odd integer and if $k = 1$, we have $k^2-1 = 0$ is divisible by $8$, I will assume $k ge 3$. Then, $k^2-1 = (k+1)(k-1)$. Now, if $k ge 3$,
$k+1 ge 4$ and $k-1 ge 2$. Then the product will be always greater than or equal to $8$. Hence, there will always be a factor of $8$ in $k^2 -1$.
answered Jan 17 at 18:03
RickRick
868
$endgroup$
I don't know if this is what you are looking for, but I have another approach without using congruences. Since $k$ is odd integer and if $k = 1$, we have $k^2-1 = 0$ is divisible by $8$, I will assume $k ge 3$. Then, $k^2-1 = (k+1)(k-1)$. Now, if $k ge 3$,
$k+1 ge 4$ and $k-1 ge 2$. Then the product will be always greater than or equal to $8$. Hence, there will always be a factor of $8$ in $k^2 -1$.
answered Jan 17 at 18:03
RickRick
868
answered Jan 17 at 18:03
RickRick
868
answered Jan 17 at 18:03
RickRick
868
answered Jan 17 at 18:03
RickRick
868
868
$begingroup$
This is a nice approach, but would definitely like to reward the student for actually reading the book and trying to use something that they previously learned to their advantage, even if it is related to memorizing a formula. I wish I remembered what exactly the student wrote, but they definitely tried to use the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
$endgroup$
– TheSodesa
Jan 17 at 18:10
add a comment |
$begingroup$
This is a nice approach, but would definitely like to reward the student for actually reading the book and trying to use something that they previously learned to their advantage, even if it is related to memorizing a formula. I wish I remembered what exactly the student wrote, but they definitely tried to use the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
$endgroup$
– TheSodesa
Jan 17 at 18:10
$begingroup$
This is a nice approach, but would definitely like to reward the student for actually reading the book and trying to use something that they previously learned to their advantage, even if it is related to memorizing a formula. I wish I remembered what exactly the student wrote, but they definitely tried to use the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
$endgroup$
– TheSodesa
Jan 17 at 18:10
$begingroup$
This is a nice approach, but would definitely like to reward the student for actually reading the book and trying to use something that they previously learned to their advantage, even if it is related to memorizing a formula. I wish I remembered what exactly the student wrote, but they definitely tried to use the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $gcd(a,b) = gcd(b,d)$.
$endgroup$
– TheSodesa
Jan 17 at 18:10
add a comment |
$begingroup$
You can use it and make an induction to solve the problem.
$(k+2)^2 - 1 - (k^2 - 1) = 4k+4$ is a multiple of $8$ ($k$ is odd) so $gcd ((k+2)^2 -1, 8) = gcd (k^2 -1, 8)$
And the result is trivial for $k = 1$.
answered Jan 17 at 19:06
DLeMeurDLeMeur
3148
$endgroup$
add a comment |
$begingroup$
You can use it and make an induction to solve the problem.
$(k+2)^2 - 1 - (k^2 - 1) = 4k+4$ is a multiple of $8$ ($k$ is odd) so $gcd ((k+2)^2 -1, 8) = gcd (k^2 -1, 8)$
And the result is trivial for $k = 1$.
answered Jan 17 at 19:06
DLeMeurDLeMeur
3148
$endgroup$
add a comment |
$begingroup$
You can use it and make an induction to solve the problem.
$(k+2)^2 - 1 - (k^2 - 1) = 4k+4$ is a multiple of $8$ ($k$ is odd) so $gcd ((k+2)^2 -1, 8) = gcd (k^2 -1, 8)$
And the result is trivial for $k = 1$.
answered Jan 17 at 19:06
DLeMeurDLeMeur
3148
$endgroup$
You can use it and make an induction to solve the problem.
$(k+2)^2 - 1 - (k^2 - 1) = 4k+4$ is a multiple of $8$ ($k$ is odd) so $gcd ((k+2)^2 -1, 8) = gcd (k^2 -1, 8)$
And the result is trivial for $k = 1$.
answered Jan 17 at 19:06
DLeMeurDLeMeur
3148
answered Jan 17 at 19:06
DLeMeurDLeMeur
3148
answered Jan 17 at 19:06
DLeMeurDLeMeur
3148
answered Jan 17 at 19:06
DLeMeurDLeMeur
3148
3148
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%2f3077284%2fcheck-divisibility-by-using-gcd%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
