Mixing
If $x_1, x_2$ are roots of $P(x)=x^2-6x+1$, prove that $5 nmid x_1^n+x_2^n$
$begingroup$
Given $x_1$ and $x_2$ are roots of $P(x)=x^2-6x+1$ prove using Binomial expansion that $x_1^n+x_2^n$ is not divisible by 5 if $nin Bbb Nsetminus{0}$.
Source: list of problems for the preparation for math contests.
Notice: this problem is different from other SE question, as it requires a specific proof that was suggested by @DeepSea in a comment in that post, but not developed.
My attempt: By solving the roots of $P(x)$ it is easy to see that
$$x_1=3+2sqrt{2} text{and} x_2=3-2sqrt{2}$$
and, using the Binomial expansion,
$$x_1^n+x_2^n=(x_1+x_2)^n-sum_{k=1}^{n-1}{{n-1}choose {k}} x_1^{n-k}x_2^k=6^n-sum_{k=1}^{n-1} {{n-1}choose {k}}x_1^{n-k}x_2^k$$
It is easy to see that $6^nequiv 1pmod{5}$ for all possible $n$. Therefore the problem is showing that for $$A(n)=sum_{k=1}^{n-1}{{n-1}choose {k}}x_1^{n-k}x_2^k, A(n)notequiv 1pmod{5}, forall nin Bbb Nsetminus{0}.$$
My problem is on how to proceed with the proof of this last statement. Hints and answers are welcomed.
algebra-precalculus contest-math
edited Jan 20 at 11:02
rtybase
11.2k21533
asked Nov 6 '18 at 13:56
bluemasterbluemaster
1,653519
$endgroup$
add a comment |
$begingroup$
Given $x_1$ and $x_2$ are roots of $P(x)=x^2-6x+1$ prove using Binomial expansion that $x_1^n+x_2^n$ is not divisible by 5 if $nin Bbb Nsetminus{0}$.
Source: list of problems for the preparation for math contests.
Notice: this problem is different from other SE question, as it requires a specific proof that was suggested by @DeepSea in a comment in that post, but not developed.
My attempt: By solving the roots of $P(x)$ it is easy to see that
$$x_1=3+2sqrt{2} text{and} x_2=3-2sqrt{2}$$
and, using the Binomial expansion,
$$x_1^n+x_2^n=(x_1+x_2)^n-sum_{k=1}^{n-1}{{n-1}choose {k}} x_1^{n-k}x_2^k=6^n-sum_{k=1}^{n-1} {{n-1}choose {k}}x_1^{n-k}x_2^k$$
It is easy to see that $6^nequiv 1pmod{5}$ for all possible $n$. Therefore the problem is showing that for $$A(n)=sum_{k=1}^{n-1}{{n-1}choose {k}}x_1^{n-k}x_2^k, A(n)notequiv 1pmod{5}, forall nin Bbb Nsetminus{0}.$$
My problem is on how to proceed with the proof of this last statement. Hints and answers are welcomed.
algebra-precalculus contest-math
edited Jan 20 at 11:02
rtybase
11.2k21533
asked Nov 6 '18 at 13:56
bluemasterbluemaster
1,653519
$endgroup$
$begingroup$
You forgot the binomial coefficients
$endgroup$
– Bruno Andrades
Nov 6 '18 at 14:00
$begingroup$
Sure, will correct.
$endgroup$
– bluemaster
Nov 6 '18 at 14:03
add a comment |
$begingroup$
Given $x_1$ and $x_2$ are roots of $P(x)=x^2-6x+1$ prove using Binomial expansion that $x_1^n+x_2^n$ is not divisible by 5 if $nin Bbb Nsetminus{0}$.
Source: list of problems for the preparation for math contests.
Notice: this problem is different from other SE question, as it requires a specific proof that was suggested by @DeepSea in a comment in that post, but not developed.
My attempt: By solving the roots of $P(x)$ it is easy to see that
$$x_1=3+2sqrt{2} text{and} x_2=3-2sqrt{2}$$
and, using the Binomial expansion,
$$x_1^n+x_2^n=(x_1+x_2)^n-sum_{k=1}^{n-1}{{n-1}choose {k}} x_1^{n-k}x_2^k=6^n-sum_{k=1}^{n-1} {{n-1}choose {k}}x_1^{n-k}x_2^k$$
It is easy to see that $6^nequiv 1pmod{5}$ for all possible $n$. Therefore the problem is showing that for $$A(n)=sum_{k=1}^{n-1}{{n-1}choose {k}}x_1^{n-k}x_2^k, A(n)notequiv 1pmod{5}, forall nin Bbb Nsetminus{0}.$$
My problem is on how to proceed with the proof of this last statement. Hints and answers are welcomed.
algebra-precalculus contest-math
edited Jan 20 at 11:02
rtybase
11.2k21533
asked Nov 6 '18 at 13:56
bluemasterbluemaster
1,653519
$endgroup$
Given $x_1$ and $x_2$ are roots of $P(x)=x^2-6x+1$ prove using Binomial expansion that $x_1^n+x_2^n$ is not divisible by 5 if $nin Bbb Nsetminus{0}$.
Source: list of problems for the preparation for math contests.
Notice: this problem is different from other SE question, as it requires a specific proof that was suggested by @DeepSea in a comment in that post, but not developed.
My attempt: By solving the roots of $P(x)$ it is easy to see that
$$x_1=3+2sqrt{2} text{and} x_2=3-2sqrt{2}$$
and, using the Binomial expansion,
$$x_1^n+x_2^n=(x_1+x_2)^n-sum_{k=1}^{n-1}{{n-1}choose {k}} x_1^{n-k}x_2^k=6^n-sum_{k=1}^{n-1} {{n-1}choose {k}}x_1^{n-k}x_2^k$$
It is easy to see that $6^nequiv 1pmod{5}$ for all possible $n$. Therefore the problem is showing that for $$A(n)=sum_{k=1}^{n-1}{{n-1}choose {k}}x_1^{n-k}x_2^k, A(n)notequiv 1pmod{5}, forall nin Bbb Nsetminus{0}.$$
My problem is on how to proceed with the proof of this last statement. Hints and answers are welcomed.
algebra-precalculus contest-math
algebra-precalculus contest-math
edited Jan 20 at 11:02
rtybase
11.2k21533
asked Nov 6 '18 at 13:56
bluemasterbluemaster
1,653519
edited Jan 20 at 11:02
rtybase
11.2k21533
asked Nov 6 '18 at 13:56
bluemasterbluemaster
1,653519
edited Jan 20 at 11:02
rtybase
11.2k21533
edited Jan 20 at 11:02
rtybase
11.2k21533
edited Jan 20 at 11:02
rtybase
11.2k21533
11.2k21533
asked Nov 6 '18 at 13:56
bluemasterbluemaster
1,653519
asked Nov 6 '18 at 13:56
bluemasterbluemaster
1,653519
asked Nov 6 '18 at 13:56
bluemasterbluemaster
1,653519
1,653519
$begingroup$
You forgot the binomial coefficients
$endgroup$
– Bruno Andrades
Nov 6 '18 at 14:00
$begingroup$
Sure, will correct.
$endgroup$
– bluemaster
Nov 6 '18 at 14:03
add a comment |
$begingroup$
You forgot the binomial coefficients
$endgroup$
– Bruno Andrades
Nov 6 '18 at 14:00
$begingroup$
Sure, will correct.
$endgroup$
– bluemaster
Nov 6 '18 at 14:03
$begingroup$
You forgot the binomial coefficients
$endgroup$
– Bruno Andrades
Nov 6 '18 at 14:00
$begingroup$
You forgot the binomial coefficients
$endgroup$
– Bruno Andrades
Nov 6 '18 at 14:00
$begingroup$
Sure, will correct.
$endgroup$
– bluemaster
Nov 6 '18 at 14:03
$begingroup$
Sure, will correct.
$endgroup$
– bluemaster
Nov 6 '18 at 14:03
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
I think you misinterpreted the suggestion by @DeepSea. He probably meant expanding $(3pm2sqrt{2})^n$ instead of $(x_1+x_2)^n$.
So if we follow this and binomial expand $(3pm 2sqrt{2})^n$, we have
$$
x_1^n+x_2^n=sum_{k=0}^nbinom{n}{k}3^{n-k} (2sqrt{2})^k underbrace{[1+(-1)^k]}_{=begin{cases}2&ktext{ even}\0&ktext{ odd}end{cases}}
$$
So we cancel the odd $k$ terms and are left with
$$
x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k}
equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{-k}pmod{5}.
$$
Hence we want to prove
$$
sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}(-3)^knotequiv 0pmod{5}
$$
which I don't see a way without
Cheating
So we look at an equivalent problem with roots $1pmsqrt{-3}pmod{5}$, which if we take out a common factor of $2$ (doesn't change mod 5 nonzero) becomes a problem with roots $y_pm=frac12(1pmsqrt{-3})$ (which are of course the roots of $y^2-y+1$, what you get from reducing coefficients of $P$ mod $5$). Now these roots are sixth roots of unity, so $y_+^n+y_-^n$ only take values $pm 1,pm 2$.
This leaves the question: why not reduce $P$ mod 5 right at the start and be done with it?
answered Nov 10 '18 at 2:35
user10354138user10354138
7,4322925
$endgroup$
$begingroup$
There is a little flaw in your argument. Specifically $$ x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k} equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^kpmod{5}. $$ if $n$ is even, the last term doesn't contain a multiplier of $3$. Try with $(3+2sqrt{2})^2 + (3-2sqrt{2})^2$ for example.
$endgroup$
– rtybase
Nov 10 '18 at 12:53
1
$begingroup$
Thanks. Now fixed.
$endgroup$
– user10354138
Nov 10 '18 at 13:15
add a comment |
$begingroup$
Here is a solution inspired by Pell's equations, which tangentially is related to Binomial expansion. $(3,2)$ is a solution for
$$x^2-2y^2=1 tag{1}$$
but then any $(x,y)$ of the form
$$x=frac{left(3+2sqrt{2}right)^n+left(3-2sqrt{2}right)^n}{2} spacespacespacetext{ and }spacespacespace
y=frac{left(3+2sqrt{2}right)^n-left(3-2sqrt{2}right)^n}{2sqrt{2}}$$
where
$$x+ysqrt{2}=left(3+2sqrt{2}right)^n spacespacespacetext{ and }spacespacespace
x-ysqrt{2}=left(3-2sqrt{2}right)^n$$
is also a solution. Using binomial expansion it is easy to check $x,y in mathbb{Z}$ and
$$2x=x_1^n+x_2^n tag{2}$$
Now, proof by contradiction. If $5 mid x_1^n+x_2^n overset{color{red}{(2)}}{Rightarrow} 5 mid x$, this is from Euclid's lemma. But then
$$5mid x^2 overset{color{red}{(1)}}{Rightarrow} 5 mid 2y^2+1$$
However $2y^2+1$ is never divisible by $5$. This is easy to see from $y^4 equiv 1 pmod{5}$ (LFT) or $5 mid left(y^2-1right)left(y^2+1right)$ (applying the same Euclid's lemma)
- if $5 mid y^2+1 Rightarrow 5 nmid 2y^2+1$
- if $5 mid y^2-1 Rightarrow 5 nmid y^2-1+2=2y^2+1$
Alternatively, it's easy to check that $2y^2+1$ never has $0$ or $5$ as the last digit.
$$2cdot color{blue}{0}^2+1=1 text{, }spacespace
2cdot color{blue}{1}^2+1=3 text{, }spacespace
2cdot color{blue}{2}^2+1=9 text{, }spacespace
2cdot color{blue}{3}^2+1=19 text{,}\
2cdot color{blue}{4}^2+1=33 text{, }spacespace
2cdot color{blue}{5}^2+1=51 text{, }spacespace
2cdot color{blue}{6}^2+1=73 text{, }spacespace
2cdot color{blue}{7}^2+1=99 text{,}\
2cdot color{blue}{8}^2+1=129 text{, }spacespace
2cdot color{blue}{9}^2+1=163$$
So we have a contradiction.
answered Jan 19 at 18:27
rtybasertybase
11.2k21533
$endgroup$
add a comment |
$begingroup$
Let $a_n = x_1^n+x_2^n$. Then modulo $5$, $a_1 =1, a_2= 2, a_n = a_{n-1}-a_{n-2}$
We can see that the terms of the sequence are periodic. They go 1,2,1,-1,-2,-1,1 and the cycle continues so that no term is $0$ modulo 5
answered Nov 10 '18 at 3:02
Hari ShankarHari Shankar
2,294139
$endgroup$
$begingroup$
This is what the OP specifically said he was NOT after
$endgroup$
– user10354138
Nov 10 '18 at 13:16
$begingroup$
Realized that long after I posted :)
$endgroup$
– Hari Shankar
Nov 10 '18 at 17:28
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%2f2987204%2fif-x-1-x-2-are-roots-of-px-x2-6x1-prove-that-5-nmid-x-1nx-2n%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$
I think you misinterpreted the suggestion by @DeepSea. He probably meant expanding $(3pm2sqrt{2})^n$ instead of $(x_1+x_2)^n$.
So if we follow this and binomial expand $(3pm 2sqrt{2})^n$, we have
$$
x_1^n+x_2^n=sum_{k=0}^nbinom{n}{k}3^{n-k} (2sqrt{2})^k underbrace{[1+(-1)^k]}_{=begin{cases}2&ktext{ even}\0&ktext{ odd}end{cases}}
$$
So we cancel the odd $k$ terms and are left with
$$
x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k}
equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{-k}pmod{5}.
$$
Hence we want to prove
$$
sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}(-3)^knotequiv 0pmod{5}
$$
which I don't see a way without
Cheating
So we look at an equivalent problem with roots $1pmsqrt{-3}pmod{5}$, which if we take out a common factor of $2$ (doesn't change mod 5 nonzero) becomes a problem with roots $y_pm=frac12(1pmsqrt{-3})$ (which are of course the roots of $y^2-y+1$, what you get from reducing coefficients of $P$ mod $5$). Now these roots are sixth roots of unity, so $y_+^n+y_-^n$ only take values $pm 1,pm 2$.
This leaves the question: why not reduce $P$ mod 5 right at the start and be done with it?
answered Nov 10 '18 at 2:35
user10354138user10354138
7,4322925
$endgroup$
$begingroup$
There is a little flaw in your argument. Specifically $$ x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k} equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^kpmod{5}. $$ if $n$ is even, the last term doesn't contain a multiplier of $3$. Try with $(3+2sqrt{2})^2 + (3-2sqrt{2})^2$ for example.
$endgroup$
– rtybase
Nov 10 '18 at 12:53
1
$begingroup$
Thanks. Now fixed.
$endgroup$
– user10354138
Nov 10 '18 at 13:15
add a comment |
$begingroup$
I think you misinterpreted the suggestion by @DeepSea. He probably meant expanding $(3pm2sqrt{2})^n$ instead of $(x_1+x_2)^n$.
So if we follow this and binomial expand $(3pm 2sqrt{2})^n$, we have
$$
x_1^n+x_2^n=sum_{k=0}^nbinom{n}{k}3^{n-k} (2sqrt{2})^k underbrace{[1+(-1)^k]}_{=begin{cases}2&ktext{ even}\0&ktext{ odd}end{cases}}
$$
So we cancel the odd $k$ terms and are left with
$$
x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k}
equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{-k}pmod{5}.
$$
Hence we want to prove
$$
sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}(-3)^knotequiv 0pmod{5}
$$
which I don't see a way without
Cheating
So we look at an equivalent problem with roots $1pmsqrt{-3}pmod{5}$, which if we take out a common factor of $2$ (doesn't change mod 5 nonzero) becomes a problem with roots $y_pm=frac12(1pmsqrt{-3})$ (which are of course the roots of $y^2-y+1$, what you get from reducing coefficients of $P$ mod $5$). Now these roots are sixth roots of unity, so $y_+^n+y_-^n$ only take values $pm 1,pm 2$.
This leaves the question: why not reduce $P$ mod 5 right at the start and be done with it?
answered Nov 10 '18 at 2:35
user10354138user10354138
7,4322925
$endgroup$
$begingroup$
There is a little flaw in your argument. Specifically $$ x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k} equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^kpmod{5}. $$ if $n$ is even, the last term doesn't contain a multiplier of $3$. Try with $(3+2sqrt{2})^2 + (3-2sqrt{2})^2$ for example.
$endgroup$
– rtybase
Nov 10 '18 at 12:53
1
$begingroup$
Thanks. Now fixed.
$endgroup$
– user10354138
Nov 10 '18 at 13:15
add a comment |
$begingroup$
I think you misinterpreted the suggestion by @DeepSea. He probably meant expanding $(3pm2sqrt{2})^n$ instead of $(x_1+x_2)^n$.
So if we follow this and binomial expand $(3pm 2sqrt{2})^n$, we have
$$
x_1^n+x_2^n=sum_{k=0}^nbinom{n}{k}3^{n-k} (2sqrt{2})^k underbrace{[1+(-1)^k]}_{=begin{cases}2&ktext{ even}\0&ktext{ odd}end{cases}}
$$
So we cancel the odd $k$ terms and are left with
$$
x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k}
equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{-k}pmod{5}.
$$
Hence we want to prove
$$
sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}(-3)^knotequiv 0pmod{5}
$$
which I don't see a way without
Cheating
So we look at an equivalent problem with roots $1pmsqrt{-3}pmod{5}$, which if we take out a common factor of $2$ (doesn't change mod 5 nonzero) becomes a problem with roots $y_pm=frac12(1pmsqrt{-3})$ (which are of course the roots of $y^2-y+1$, what you get from reducing coefficients of $P$ mod $5$). Now these roots are sixth roots of unity, so $y_+^n+y_-^n$ only take values $pm 1,pm 2$.
This leaves the question: why not reduce $P$ mod 5 right at the start and be done with it?
answered Nov 10 '18 at 2:35
user10354138user10354138
7,4322925
$endgroup$
I think you misinterpreted the suggestion by @DeepSea. He probably meant expanding $(3pm2sqrt{2})^n$ instead of $(x_1+x_2)^n$.
So if we follow this and binomial expand $(3pm 2sqrt{2})^n$, we have
$$
x_1^n+x_2^n=sum_{k=0}^nbinom{n}{k}3^{n-k} (2sqrt{2})^k underbrace{[1+(-1)^k]}_{=begin{cases}2&ktext{ even}\0&ktext{ odd}end{cases}}
$$
So we cancel the odd $k$ terms and are left with
$$
x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k}
equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{-k}pmod{5}.
$$
Hence we want to prove
$$
sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}(-3)^knotequiv 0pmod{5}
$$
which I don't see a way without
Cheating
So we look at an equivalent problem with roots $1pmsqrt{-3}pmod{5}$, which if we take out a common factor of $2$ (doesn't change mod 5 nonzero) becomes a problem with roots $y_pm=frac12(1pmsqrt{-3})$ (which are of course the roots of $y^2-y+1$, what you get from reducing coefficients of $P$ mod $5$). Now these roots are sixth roots of unity, so $y_+^n+y_-^n$ only take values $pm 1,pm 2$.
This leaves the question: why not reduce $P$ mod 5 right at the start and be done with it?
answered Nov 10 '18 at 2:35
user10354138user10354138
7,4322925
edited Nov 10 '18 at 13:14
answered Nov 10 '18 at 2:35
user10354138user10354138
7,4322925
answered Nov 10 '18 at 2:35
user10354138user10354138
7,4322925
answered Nov 10 '18 at 2:35
user10354138user10354138
7,4322925
7,4322925
$begingroup$
There is a little flaw in your argument. Specifically $$ x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k} equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^kpmod{5}. $$ if $n$ is even, the last term doesn't contain a multiplier of $3$. Try with $(3+2sqrt{2})^2 + (3-2sqrt{2})^2$ for example.
$endgroup$
– rtybase
Nov 10 '18 at 12:53
1
$begingroup$
Thanks. Now fixed.
$endgroup$
– user10354138
Nov 10 '18 at 13:15
add a comment |
$begingroup$
There is a little flaw in your argument. Specifically $$ x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k} equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^kpmod{5}. $$ if $n$ is even, the last term doesn't contain a multiplier of $3$. Try with $(3+2sqrt{2})^2 + (3-2sqrt{2})^2$ for example.
$endgroup$
– rtybase
Nov 10 '18 at 12:53
1
$begingroup$
Thanks. Now fixed.
$endgroup$
– user10354138
Nov 10 '18 at 13:15
$begingroup$
There is a little flaw in your argument. Specifically $$ x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k} equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^kpmod{5}. $$ if $n$ is even, the last term doesn't contain a multiplier of $3$. Try with $(3+2sqrt{2})^2 + (3-2sqrt{2})^2$ for example.
$endgroup$
– rtybase
Nov 10 '18 at 12:53
$begingroup$
There is a little flaw in your argument. Specifically $$ x_1^n+x_2^n=2sum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^{n-2k} (2sqrt{2})^{2k} equiv 2cdot3^nsum_{k=0}^{lfloor n/2rfloor}binom{n}{2k}3^kpmod{5}. $$ if $n$ is even, the last term doesn't contain a multiplier of $3$. Try with $(3+2sqrt{2})^2 + (3-2sqrt{2})^2$ for example.
$endgroup$
– rtybase
Nov 10 '18 at 12:53
1
1
$begingroup$
Thanks. Now fixed.
$endgroup$
– user10354138
Nov 10 '18 at 13:15
$begingroup$
Thanks. Now fixed.
$endgroup$
– user10354138
Nov 10 '18 at 13:15
add a comment |
$begingroup$
Here is a solution inspired by Pell's equations, which tangentially is related to Binomial expansion. $(3,2)$ is a solution for
$$x^2-2y^2=1 tag{1}$$
but then any $(x,y)$ of the form
$$x=frac{left(3+2sqrt{2}right)^n+left(3-2sqrt{2}right)^n}{2} spacespacespacetext{ and }spacespacespace
y=frac{left(3+2sqrt{2}right)^n-left(3-2sqrt{2}right)^n}{2sqrt{2}}$$
where
$$x+ysqrt{2}=left(3+2sqrt{2}right)^n spacespacespacetext{ and }spacespacespace
x-ysqrt{2}=left(3-2sqrt{2}right)^n$$
is also a solution. Using binomial expansion it is easy to check $x,y in mathbb{Z}$ and
$$2x=x_1^n+x_2^n tag{2}$$
Now, proof by contradiction. If $5 mid x_1^n+x_2^n overset{color{red}{(2)}}{Rightarrow} 5 mid x$, this is from Euclid's lemma. But then
$$5mid x^2 overset{color{red}{(1)}}{Rightarrow} 5 mid 2y^2+1$$
However $2y^2+1$ is never divisible by $5$. This is easy to see from $y^4 equiv 1 pmod{5}$ (LFT) or $5 mid left(y^2-1right)left(y^2+1right)$ (applying the same Euclid's lemma)
- if $5 mid y^2+1 Rightarrow 5 nmid 2y^2+1$
- if $5 mid y^2-1 Rightarrow 5 nmid y^2-1+2=2y^2+1$
Alternatively, it's easy to check that $2y^2+1$ never has $0$ or $5$ as the last digit.
$$2cdot color{blue}{0}^2+1=1 text{, }spacespace
2cdot color{blue}{1}^2+1=3 text{, }spacespace
2cdot color{blue}{2}^2+1=9 text{, }spacespace
2cdot color{blue}{3}^2+1=19 text{,}\
2cdot color{blue}{4}^2+1=33 text{, }spacespace
2cdot color{blue}{5}^2+1=51 text{, }spacespace
2cdot color{blue}{6}^2+1=73 text{, }spacespace
2cdot color{blue}{7}^2+1=99 text{,}\
2cdot color{blue}{8}^2+1=129 text{, }spacespace
2cdot color{blue}{9}^2+1=163$$
So we have a contradiction.
answered Jan 19 at 18:27
rtybasertybase
11.2k21533
$endgroup$
add a comment |
$begingroup$
Here is a solution inspired by Pell's equations, which tangentially is related to Binomial expansion. $(3,2)$ is a solution for
$$x^2-2y^2=1 tag{1}$$
but then any $(x,y)$ of the form
$$x=frac{left(3+2sqrt{2}right)^n+left(3-2sqrt{2}right)^n}{2} spacespacespacetext{ and }spacespacespace
y=frac{left(3+2sqrt{2}right)^n-left(3-2sqrt{2}right)^n}{2sqrt{2}}$$
where
$$x+ysqrt{2}=left(3+2sqrt{2}right)^n spacespacespacetext{ and }spacespacespace
x-ysqrt{2}=left(3-2sqrt{2}right)^n$$
is also a solution. Using binomial expansion it is easy to check $x,y in mathbb{Z}$ and
$$2x=x_1^n+x_2^n tag{2}$$
Now, proof by contradiction. If $5 mid x_1^n+x_2^n overset{color{red}{(2)}}{Rightarrow} 5 mid x$, this is from Euclid's lemma. But then
$$5mid x^2 overset{color{red}{(1)}}{Rightarrow} 5 mid 2y^2+1$$
However $2y^2+1$ is never divisible by $5$. This is easy to see from $y^4 equiv 1 pmod{5}$ (LFT) or $5 mid left(y^2-1right)left(y^2+1right)$ (applying the same Euclid's lemma)
- if $5 mid y^2+1 Rightarrow 5 nmid 2y^2+1$
- if $5 mid y^2-1 Rightarrow 5 nmid y^2-1+2=2y^2+1$
Alternatively, it's easy to check that $2y^2+1$ never has $0$ or $5$ as the last digit.
$$2cdot color{blue}{0}^2+1=1 text{, }spacespace
2cdot color{blue}{1}^2+1=3 text{, }spacespace
2cdot color{blue}{2}^2+1=9 text{, }spacespace
2cdot color{blue}{3}^2+1=19 text{,}\
2cdot color{blue}{4}^2+1=33 text{, }spacespace
2cdot color{blue}{5}^2+1=51 text{, }spacespace
2cdot color{blue}{6}^2+1=73 text{, }spacespace
2cdot color{blue}{7}^2+1=99 text{,}\
2cdot color{blue}{8}^2+1=129 text{, }spacespace
2cdot color{blue}{9}^2+1=163$$
So we have a contradiction.
answered Jan 19 at 18:27
rtybasertybase
11.2k21533
$endgroup$
add a comment |
$begingroup$
Here is a solution inspired by Pell's equations, which tangentially is related to Binomial expansion. $(3,2)$ is a solution for
$$x^2-2y^2=1 tag{1}$$
but then any $(x,y)$ of the form
$$x=frac{left(3+2sqrt{2}right)^n+left(3-2sqrt{2}right)^n}{2} spacespacespacetext{ and }spacespacespace
y=frac{left(3+2sqrt{2}right)^n-left(3-2sqrt{2}right)^n}{2sqrt{2}}$$
where
$$x+ysqrt{2}=left(3+2sqrt{2}right)^n spacespacespacetext{ and }spacespacespace
x-ysqrt{2}=left(3-2sqrt{2}right)^n$$
is also a solution. Using binomial expansion it is easy to check $x,y in mathbb{Z}$ and
$$2x=x_1^n+x_2^n tag{2}$$
Now, proof by contradiction. If $5 mid x_1^n+x_2^n overset{color{red}{(2)}}{Rightarrow} 5 mid x$, this is from Euclid's lemma. But then
$$5mid x^2 overset{color{red}{(1)}}{Rightarrow} 5 mid 2y^2+1$$
However $2y^2+1$ is never divisible by $5$. This is easy to see from $y^4 equiv 1 pmod{5}$ (LFT) or $5 mid left(y^2-1right)left(y^2+1right)$ (applying the same Euclid's lemma)
- if $5 mid y^2+1 Rightarrow 5 nmid 2y^2+1$
- if $5 mid y^2-1 Rightarrow 5 nmid y^2-1+2=2y^2+1$
Alternatively, it's easy to check that $2y^2+1$ never has $0$ or $5$ as the last digit.
$$2cdot color{blue}{0}^2+1=1 text{, }spacespace
2cdot color{blue}{1}^2+1=3 text{, }spacespace
2cdot color{blue}{2}^2+1=9 text{, }spacespace
2cdot color{blue}{3}^2+1=19 text{,}\
2cdot color{blue}{4}^2+1=33 text{, }spacespace
2cdot color{blue}{5}^2+1=51 text{, }spacespace
2cdot color{blue}{6}^2+1=73 text{, }spacespace
2cdot color{blue}{7}^2+1=99 text{,}\
2cdot color{blue}{8}^2+1=129 text{, }spacespace
2cdot color{blue}{9}^2+1=163$$
So we have a contradiction.
answered Jan 19 at 18:27
rtybasertybase
11.2k21533
$endgroup$
Here is a solution inspired by Pell's equations, which tangentially is related to Binomial expansion. $(3,2)$ is a solution for
$$x^2-2y^2=1 tag{1}$$
but then any $(x,y)$ of the form
$$x=frac{left(3+2sqrt{2}right)^n+left(3-2sqrt{2}right)^n}{2} spacespacespacetext{ and }spacespacespace
y=frac{left(3+2sqrt{2}right)^n-left(3-2sqrt{2}right)^n}{2sqrt{2}}$$
where
$$x+ysqrt{2}=left(3+2sqrt{2}right)^n spacespacespacetext{ and }spacespacespace
x-ysqrt{2}=left(3-2sqrt{2}right)^n$$
is also a solution. Using binomial expansion it is easy to check $x,y in mathbb{Z}$ and
$$2x=x_1^n+x_2^n tag{2}$$
Now, proof by contradiction. If $5 mid x_1^n+x_2^n overset{color{red}{(2)}}{Rightarrow} 5 mid x$, this is from Euclid's lemma. But then
$$5mid x^2 overset{color{red}{(1)}}{Rightarrow} 5 mid 2y^2+1$$
However $2y^2+1$ is never divisible by $5$. This is easy to see from $y^4 equiv 1 pmod{5}$ (LFT) or $5 mid left(y^2-1right)left(y^2+1right)$ (applying the same Euclid's lemma)
- if $5 mid y^2+1 Rightarrow 5 nmid 2y^2+1$
- if $5 mid y^2-1 Rightarrow 5 nmid y^2-1+2=2y^2+1$
Alternatively, it's easy to check that $2y^2+1$ never has $0$ or $5$ as the last digit.
$$2cdot color{blue}{0}^2+1=1 text{, }spacespace
2cdot color{blue}{1}^2+1=3 text{, }spacespace
2cdot color{blue}{2}^2+1=9 text{, }spacespace
2cdot color{blue}{3}^2+1=19 text{,}\
2cdot color{blue}{4}^2+1=33 text{, }spacespace
2cdot color{blue}{5}^2+1=51 text{, }spacespace
2cdot color{blue}{6}^2+1=73 text{, }spacespace
2cdot color{blue}{7}^2+1=99 text{,}\
2cdot color{blue}{8}^2+1=129 text{, }spacespace
2cdot color{blue}{9}^2+1=163$$
So we have a contradiction.
answered Jan 19 at 18:27
rtybasertybase
11.2k21533
edited Jan 20 at 11:39
answered Jan 19 at 18:27
rtybasertybase
11.2k21533
answered Jan 19 at 18:27
rtybasertybase
11.2k21533
answered Jan 19 at 18:27
rtybasertybase
11.2k21533
11.2k21533
add a comment |
add a comment |
$begingroup$
Let $a_n = x_1^n+x_2^n$. Then modulo $5$, $a_1 =1, a_2= 2, a_n = a_{n-1}-a_{n-2}$
We can see that the terms of the sequence are periodic. They go 1,2,1,-1,-2,-1,1 and the cycle continues so that no term is $0$ modulo 5
answered Nov 10 '18 at 3:02
Hari ShankarHari Shankar
2,294139
$endgroup$
$begingroup$
This is what the OP specifically said he was NOT after
$endgroup$
– user10354138
Nov 10 '18 at 13:16
$begingroup$
Realized that long after I posted :)
$endgroup$
– Hari Shankar
Nov 10 '18 at 17:28
add a comment |
$begingroup$
Let $a_n = x_1^n+x_2^n$. Then modulo $5$, $a_1 =1, a_2= 2, a_n = a_{n-1}-a_{n-2}$
We can see that the terms of the sequence are periodic. They go 1,2,1,-1,-2,-1,1 and the cycle continues so that no term is $0$ modulo 5
answered Nov 10 '18 at 3:02
Hari ShankarHari Shankar
2,294139
$endgroup$
$begingroup$
This is what the OP specifically said he was NOT after
$endgroup$
– user10354138
Nov 10 '18 at 13:16
$begingroup$
Realized that long after I posted :)
$endgroup$
– Hari Shankar
Nov 10 '18 at 17:28
add a comment |
$begingroup$
Let $a_n = x_1^n+x_2^n$. Then modulo $5$, $a_1 =1, a_2= 2, a_n = a_{n-1}-a_{n-2}$
We can see that the terms of the sequence are periodic. They go 1,2,1,-1,-2,-1,1 and the cycle continues so that no term is $0$ modulo 5
answered Nov 10 '18 at 3:02
Hari ShankarHari Shankar
2,294139
$endgroup$
Let $a_n = x_1^n+x_2^n$. Then modulo $5$, $a_1 =1, a_2= 2, a_n = a_{n-1}-a_{n-2}$
We can see that the terms of the sequence are periodic. They go 1,2,1,-1,-2,-1,1 and the cycle continues so that no term is $0$ modulo 5
answered Nov 10 '18 at 3:02
Hari ShankarHari Shankar
2,294139
answered Nov 10 '18 at 3:02
Hari ShankarHari Shankar
2,294139
answered Nov 10 '18 at 3:02
Hari ShankarHari Shankar
2,294139
answered Nov 10 '18 at 3:02
Hari ShankarHari Shankar
2,294139
2,294139
$begingroup$
This is what the OP specifically said he was NOT after
$endgroup$
– user10354138
Nov 10 '18 at 13:16
$begingroup$
Realized that long after I posted :)
$endgroup$
– Hari Shankar
Nov 10 '18 at 17:28
add a comment |
$begingroup$
This is what the OP specifically said he was NOT after
$endgroup$
– user10354138
Nov 10 '18 at 13:16
$begingroup$
Realized that long after I posted :)
$endgroup$
– Hari Shankar
Nov 10 '18 at 17:28
$begingroup$
This is what the OP specifically said he was NOT after
$endgroup$
– user10354138
Nov 10 '18 at 13:16
$begingroup$
This is what the OP specifically said he was NOT after
$endgroup$
– user10354138
Nov 10 '18 at 13:16
$begingroup$
Realized that long after I posted :)
$endgroup$
– Hari Shankar
Nov 10 '18 at 17:28
$begingroup$
Realized that long after I posted :)
$endgroup$
– Hari Shankar
Nov 10 '18 at 17:28
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%2f2987204%2fif-x-1-x-2-are-roots-of-px-x2-6x1-prove-that-5-nmid-x-1nx-2n%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$
You forgot the binomial coefficients
$endgroup$
– Bruno Andrades
Nov 6 '18 at 14:00
$begingroup$
Sure, will correct.
$endgroup$
– bluemaster
Nov 6 '18 at 14:03