Mixing
Prove that $2019^{2018}+2020$ is divisible by at least three primes.
$begingroup$
Prove that $2019^{2018}+2020$ is divisible by at least three primes.
I try to use modular arithmetic, but I believe the only prime I can find is 11. This means I have to find one more factor, but I'm not quite sure if this approach is correct.
Any help would be appreciated.
modular-arithmetic contest-math recreational-mathematics
asked Jan 20 at 5:33
Hubert LioniHubert Lioni
233
$endgroup$
add a comment |
$begingroup$
Prove that $2019^{2018}+2020$ is divisible by at least three primes.
I try to use modular arithmetic, but I believe the only prime I can find is 11. This means I have to find one more factor, but I'm not quite sure if this approach is correct.
Any help would be appreciated.
modular-arithmetic contest-math recreational-mathematics
asked Jan 20 at 5:33
Hubert LioniHubert Lioni
233
$endgroup$
1
$begingroup$
The next one is $397$, a ways off.
$endgroup$
– Ross Millikan
Jan 20 at 6:11
$begingroup$
In addition to those found by WA, $221203$ is a factor.
$endgroup$
– Robert Israel
Jan 20 at 6:20
$begingroup$
And $536314783$
$endgroup$
– Josh B.
Jan 20 at 6:34
add a comment |
$begingroup$
Prove that $2019^{2018}+2020$ is divisible by at least three primes.
I try to use modular arithmetic, but I believe the only prime I can find is 11. This means I have to find one more factor, but I'm not quite sure if this approach is correct.
Any help would be appreciated.
modular-arithmetic contest-math recreational-mathematics
asked Jan 20 at 5:33
Hubert LioniHubert Lioni
233
$endgroup$
Prove that $2019^{2018}+2020$ is divisible by at least three primes.
I try to use modular arithmetic, but I believe the only prime I can find is 11. This means I have to find one more factor, but I'm not quite sure if this approach is correct.
Any help would be appreciated.
modular-arithmetic contest-math recreational-mathematics
modular-arithmetic contest-math recreational-mathematics
asked Jan 20 at 5:33
Hubert LioniHubert Lioni
233
asked Jan 20 at 5:33
Hubert LioniHubert Lioni
233
asked Jan 20 at 5:33
Hubert LioniHubert Lioni
233
asked Jan 20 at 5:33
Hubert LioniHubert Lioni
233
asked Jan 20 at 5:33
Hubert LioniHubert Lioni
233
233
1
$begingroup$
The next one is $397$, a ways off.
$endgroup$
– Ross Millikan
Jan 20 at 6:11
$begingroup$
In addition to those found by WA, $221203$ is a factor.
$endgroup$
– Robert Israel
Jan 20 at 6:20
$begingroup$
And $536314783$
$endgroup$
– Josh B.
Jan 20 at 6:34
add a comment |
1
$begingroup$
The next one is $397$, a ways off.
$endgroup$
– Ross Millikan
Jan 20 at 6:11
$begingroup$
In addition to those found by WA, $221203$ is a factor.
$endgroup$
– Robert Israel
Jan 20 at 6:20
$begingroup$
And $536314783$
$endgroup$
– Josh B.
Jan 20 at 6:34
1
1
$begingroup$
The next one is $397$, a ways off.
$endgroup$
– Ross Millikan
Jan 20 at 6:11
$begingroup$
The next one is $397$, a ways off.
$endgroup$
– Ross Millikan
Jan 20 at 6:11
$begingroup$
In addition to those found by WA, $221203$ is a factor.
$endgroup$
– Robert Israel
Jan 20 at 6:20
$begingroup$
In addition to those found by WA, $221203$ is a factor.
$endgroup$
– Robert Israel
Jan 20 at 6:20
$begingroup$
And $536314783$
$endgroup$
– Josh B.
Jan 20 at 6:34
$begingroup$
And $536314783$
$endgroup$
– Josh B.
Jan 20 at 6:34
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Quick scan with modular arithmetic - no other prime factors less than $100$. I suspect the next one after $11$ is large enough that it would be impractical even if I went to the trouble of writing a program for it. Time for another approach.
Edit: as the next prime factor is $397$, found below - it wouldn't have been impractical with the program. Implementing smart modular exponentiation would have taken some time, but looping through a hundred primes is nothing once I've got that part.
And no, there's nothing wrong with trying something, getting less than the full problem, and returning with a different approach. There's nothing theoretically wrong with the modular arithmetic, and we did find a factor that way.
What's the new approach? Polynomial factorization. Split that $2020$ as $2019+1$. That gives us $n^{2018}+n+1$, evaluated at $n=2019$. Now, add and subtract $n^2$; we get $(n^{2018}-n^2)+(n^2+n+1)$. Both of those terms are divisible by $n^2+n+1$, since $2018equiv 2mod 3$. That means that $2019^2+2019+1=4078381$ is a factor of the big number we're looking at. The other factor is $n^{2016}-n^{2015}+n^{2013}-n^{2012}+cdots+n^3-n^2+1$, which is equivalent to $673-672n^2equiv 672n+1345mod n^2+n+1$. Evaluated at $n=2019$ - that's $1358113$, which is relatively prime to $4078381$ (Euclidean algorithm - very easy to run). We have split $2019^{2018}+2019+1$ as a product of two factors that are relatively prime. It's equivalent to $88$ mod $121$, so there's exactly one factor of $11$ in there; as both terms from the polynomial factorization are much larger than $11$, one of them is a product of $11$ and at least one other prime. The other has at least one prime factor, not on the list of what we've already found, and we have at least three distinct prime factors. Done.
Incidentally, I happened to have a sieve lying around, so I tested that factor $4078381$ against primes up to $30000$. It splits as $397cdot 10273$, and both of those are prime. So that's three not-too-huge prime factors we've found, plus whatever else is in the big factor $2019^{2016}-2019^{2015}+2019^{2013}-2019^{2012}+cdots+2019^3-2019^2+1$.
answered Jan 20 at 6:29
jmerryjmerry
11.8k1528
$endgroup$
$begingroup$
In the last expression, I haven’t checked, but is there supposed to be a + 2019 as ($2019^1$) towards the end?
$endgroup$
– L. McDonald
Jan 20 at 8:09
$begingroup$
No, that last term you're thinking of is the +1.
$endgroup$
– jmerry
Jan 20 at 8:34
$begingroup$
So it is all the powers of 2019, except the first power, but including the zeroeth power.
$endgroup$
– L. McDonald
Jan 21 at 21:28
$begingroup$
No, it isn't - it's a 3-cycle, alternating coefficients $1,0,-1$ as we increase. Everything that's $1$ mod $3$ is out.
$endgroup$
– jmerry
Jan 21 at 21:35
$begingroup$
Oh, sorry. My mistake. Thanks for the clarification.
$endgroup$
– L. McDonald
Jan 22 at 18:36
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%2f3080229%2fprove-that-201920182020-is-divisible-by-at-least-three-primes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Quick scan with modular arithmetic - no other prime factors less than $100$. I suspect the next one after $11$ is large enough that it would be impractical even if I went to the trouble of writing a program for it. Time for another approach.
Edit: as the next prime factor is $397$, found below - it wouldn't have been impractical with the program. Implementing smart modular exponentiation would have taken some time, but looping through a hundred primes is nothing once I've got that part.
And no, there's nothing wrong with trying something, getting less than the full problem, and returning with a different approach. There's nothing theoretically wrong with the modular arithmetic, and we did find a factor that way.
What's the new approach? Polynomial factorization. Split that $2020$ as $2019+1$. That gives us $n^{2018}+n+1$, evaluated at $n=2019$. Now, add and subtract $n^2$; we get $(n^{2018}-n^2)+(n^2+n+1)$. Both of those terms are divisible by $n^2+n+1$, since $2018equiv 2mod 3$. That means that $2019^2+2019+1=4078381$ is a factor of the big number we're looking at. The other factor is $n^{2016}-n^{2015}+n^{2013}-n^{2012}+cdots+n^3-n^2+1$, which is equivalent to $673-672n^2equiv 672n+1345mod n^2+n+1$. Evaluated at $n=2019$ - that's $1358113$, which is relatively prime to $4078381$ (Euclidean algorithm - very easy to run). We have split $2019^{2018}+2019+1$ as a product of two factors that are relatively prime. It's equivalent to $88$ mod $121$, so there's exactly one factor of $11$ in there; as both terms from the polynomial factorization are much larger than $11$, one of them is a product of $11$ and at least one other prime. The other has at least one prime factor, not on the list of what we've already found, and we have at least three distinct prime factors. Done.
Incidentally, I happened to have a sieve lying around, so I tested that factor $4078381$ against primes up to $30000$. It splits as $397cdot 10273$, and both of those are prime. So that's three not-too-huge prime factors we've found, plus whatever else is in the big factor $2019^{2016}-2019^{2015}+2019^{2013}-2019^{2012}+cdots+2019^3-2019^2+1$.
answered Jan 20 at 6:29
jmerryjmerry
11.8k1528
$endgroup$
$begingroup$
In the last expression, I haven’t checked, but is there supposed to be a + 2019 as ($2019^1$) towards the end?
$endgroup$
– L. McDonald
Jan 20 at 8:09
$begingroup$
No, that last term you're thinking of is the +1.
$endgroup$
– jmerry
Jan 20 at 8:34
$begingroup$
So it is all the powers of 2019, except the first power, but including the zeroeth power.
$endgroup$
– L. McDonald
Jan 21 at 21:28
$begingroup$
No, it isn't - it's a 3-cycle, alternating coefficients $1,0,-1$ as we increase. Everything that's $1$ mod $3$ is out.
$endgroup$
– jmerry
Jan 21 at 21:35
$begingroup$
Oh, sorry. My mistake. Thanks for the clarification.
$endgroup$
– L. McDonald
Jan 22 at 18:36
add a comment |
$begingroup$
Quick scan with modular arithmetic - no other prime factors less than $100$. I suspect the next one after $11$ is large enough that it would be impractical even if I went to the trouble of writing a program for it. Time for another approach.
Edit: as the next prime factor is $397$, found below - it wouldn't have been impractical with the program. Implementing smart modular exponentiation would have taken some time, but looping through a hundred primes is nothing once I've got that part.
And no, there's nothing wrong with trying something, getting less than the full problem, and returning with a different approach. There's nothing theoretically wrong with the modular arithmetic, and we did find a factor that way.
What's the new approach? Polynomial factorization. Split that $2020$ as $2019+1$. That gives us $n^{2018}+n+1$, evaluated at $n=2019$. Now, add and subtract $n^2$; we get $(n^{2018}-n^2)+(n^2+n+1)$. Both of those terms are divisible by $n^2+n+1$, since $2018equiv 2mod 3$. That means that $2019^2+2019+1=4078381$ is a factor of the big number we're looking at. The other factor is $n^{2016}-n^{2015}+n^{2013}-n^{2012}+cdots+n^3-n^2+1$, which is equivalent to $673-672n^2equiv 672n+1345mod n^2+n+1$. Evaluated at $n=2019$ - that's $1358113$, which is relatively prime to $4078381$ (Euclidean algorithm - very easy to run). We have split $2019^{2018}+2019+1$ as a product of two factors that are relatively prime. It's equivalent to $88$ mod $121$, so there's exactly one factor of $11$ in there; as both terms from the polynomial factorization are much larger than $11$, one of them is a product of $11$ and at least one other prime. The other has at least one prime factor, not on the list of what we've already found, and we have at least three distinct prime factors. Done.
Incidentally, I happened to have a sieve lying around, so I tested that factor $4078381$ against primes up to $30000$. It splits as $397cdot 10273$, and both of those are prime. So that's three not-too-huge prime factors we've found, plus whatever else is in the big factor $2019^{2016}-2019^{2015}+2019^{2013}-2019^{2012}+cdots+2019^3-2019^2+1$.
answered Jan 20 at 6:29
jmerryjmerry
11.8k1528
$endgroup$
$begingroup$
In the last expression, I haven’t checked, but is there supposed to be a + 2019 as ($2019^1$) towards the end?
$endgroup$
– L. McDonald
Jan 20 at 8:09
$begingroup$
No, that last term you're thinking of is the +1.
$endgroup$
– jmerry
Jan 20 at 8:34
$begingroup$
So it is all the powers of 2019, except the first power, but including the zeroeth power.
$endgroup$
– L. McDonald
Jan 21 at 21:28
$begingroup$
No, it isn't - it's a 3-cycle, alternating coefficients $1,0,-1$ as we increase. Everything that's $1$ mod $3$ is out.
$endgroup$
– jmerry
Jan 21 at 21:35
$begingroup$
Oh, sorry. My mistake. Thanks for the clarification.
$endgroup$
– L. McDonald
Jan 22 at 18:36
add a comment |
$begingroup$
Quick scan with modular arithmetic - no other prime factors less than $100$. I suspect the next one after $11$ is large enough that it would be impractical even if I went to the trouble of writing a program for it. Time for another approach.
Edit: as the next prime factor is $397$, found below - it wouldn't have been impractical with the program. Implementing smart modular exponentiation would have taken some time, but looping through a hundred primes is nothing once I've got that part.
And no, there's nothing wrong with trying something, getting less than the full problem, and returning with a different approach. There's nothing theoretically wrong with the modular arithmetic, and we did find a factor that way.
What's the new approach? Polynomial factorization. Split that $2020$ as $2019+1$. That gives us $n^{2018}+n+1$, evaluated at $n=2019$. Now, add and subtract $n^2$; we get $(n^{2018}-n^2)+(n^2+n+1)$. Both of those terms are divisible by $n^2+n+1$, since $2018equiv 2mod 3$. That means that $2019^2+2019+1=4078381$ is a factor of the big number we're looking at. The other factor is $n^{2016}-n^{2015}+n^{2013}-n^{2012}+cdots+n^3-n^2+1$, which is equivalent to $673-672n^2equiv 672n+1345mod n^2+n+1$. Evaluated at $n=2019$ - that's $1358113$, which is relatively prime to $4078381$ (Euclidean algorithm - very easy to run). We have split $2019^{2018}+2019+1$ as a product of two factors that are relatively prime. It's equivalent to $88$ mod $121$, so there's exactly one factor of $11$ in there; as both terms from the polynomial factorization are much larger than $11$, one of them is a product of $11$ and at least one other prime. The other has at least one prime factor, not on the list of what we've already found, and we have at least three distinct prime factors. Done.
Incidentally, I happened to have a sieve lying around, so I tested that factor $4078381$ against primes up to $30000$. It splits as $397cdot 10273$, and both of those are prime. So that's three not-too-huge prime factors we've found, plus whatever else is in the big factor $2019^{2016}-2019^{2015}+2019^{2013}-2019^{2012}+cdots+2019^3-2019^2+1$.
answered Jan 20 at 6:29
jmerryjmerry
11.8k1528
$endgroup$
Quick scan with modular arithmetic - no other prime factors less than $100$. I suspect the next one after $11$ is large enough that it would be impractical even if I went to the trouble of writing a program for it. Time for another approach.
Edit: as the next prime factor is $397$, found below - it wouldn't have been impractical with the program. Implementing smart modular exponentiation would have taken some time, but looping through a hundred primes is nothing once I've got that part.
And no, there's nothing wrong with trying something, getting less than the full problem, and returning with a different approach. There's nothing theoretically wrong with the modular arithmetic, and we did find a factor that way.
What's the new approach? Polynomial factorization. Split that $2020$ as $2019+1$. That gives us $n^{2018}+n+1$, evaluated at $n=2019$. Now, add and subtract $n^2$; we get $(n^{2018}-n^2)+(n^2+n+1)$. Both of those terms are divisible by $n^2+n+1$, since $2018equiv 2mod 3$. That means that $2019^2+2019+1=4078381$ is a factor of the big number we're looking at. The other factor is $n^{2016}-n^{2015}+n^{2013}-n^{2012}+cdots+n^3-n^2+1$, which is equivalent to $673-672n^2equiv 672n+1345mod n^2+n+1$. Evaluated at $n=2019$ - that's $1358113$, which is relatively prime to $4078381$ (Euclidean algorithm - very easy to run). We have split $2019^{2018}+2019+1$ as a product of two factors that are relatively prime. It's equivalent to $88$ mod $121$, so there's exactly one factor of $11$ in there; as both terms from the polynomial factorization are much larger than $11$, one of them is a product of $11$ and at least one other prime. The other has at least one prime factor, not on the list of what we've already found, and we have at least three distinct prime factors. Done.
Incidentally, I happened to have a sieve lying around, so I tested that factor $4078381$ against primes up to $30000$. It splits as $397cdot 10273$, and both of those are prime. So that's three not-too-huge prime factors we've found, plus whatever else is in the big factor $2019^{2016}-2019^{2015}+2019^{2013}-2019^{2012}+cdots+2019^3-2019^2+1$.
answered Jan 20 at 6:29
jmerryjmerry
11.8k1528
edited Jan 20 at 6:37
answered Jan 20 at 6:29
jmerryjmerry
11.8k1528
answered Jan 20 at 6:29
jmerryjmerry
11.8k1528
answered Jan 20 at 6:29
jmerryjmerry
11.8k1528
11.8k1528
$begingroup$
In the last expression, I haven’t checked, but is there supposed to be a + 2019 as ($2019^1$) towards the end?
$endgroup$
– L. McDonald
Jan 20 at 8:09
$begingroup$
No, that last term you're thinking of is the +1.
$endgroup$
– jmerry
Jan 20 at 8:34
$begingroup$
So it is all the powers of 2019, except the first power, but including the zeroeth power.
$endgroup$
– L. McDonald
Jan 21 at 21:28
$begingroup$
No, it isn't - it's a 3-cycle, alternating coefficients $1,0,-1$ as we increase. Everything that's $1$ mod $3$ is out.
$endgroup$
– jmerry
Jan 21 at 21:35
$begingroup$
Oh, sorry. My mistake. Thanks for the clarification.
$endgroup$
– L. McDonald
Jan 22 at 18:36
add a comment |
$begingroup$
In the last expression, I haven’t checked, but is there supposed to be a + 2019 as ($2019^1$) towards the end?
$endgroup$
– L. McDonald
Jan 20 at 8:09
$begingroup$
No, that last term you're thinking of is the +1.
$endgroup$
– jmerry
Jan 20 at 8:34
$begingroup$
So it is all the powers of 2019, except the first power, but including the zeroeth power.
$endgroup$
– L. McDonald
Jan 21 at 21:28
$begingroup$
No, it isn't - it's a 3-cycle, alternating coefficients $1,0,-1$ as we increase. Everything that's $1$ mod $3$ is out.
$endgroup$
– jmerry
Jan 21 at 21:35
$begingroup$
Oh, sorry. My mistake. Thanks for the clarification.
$endgroup$
– L. McDonald
Jan 22 at 18:36
$begingroup$
In the last expression, I haven’t checked, but is there supposed to be a + 2019 as ($2019^1$) towards the end?
$endgroup$
– L. McDonald
Jan 20 at 8:09
$begingroup$
In the last expression, I haven’t checked, but is there supposed to be a + 2019 as ($2019^1$) towards the end?
$endgroup$
– L. McDonald
Jan 20 at 8:09
$begingroup$
No, that last term you're thinking of is the +1.
$endgroup$
– jmerry
Jan 20 at 8:34
$begingroup$
No, that last term you're thinking of is the +1.
$endgroup$
– jmerry
Jan 20 at 8:34
$begingroup$
So it is all the powers of 2019, except the first power, but including the zeroeth power.
$endgroup$
– L. McDonald
Jan 21 at 21:28
$begingroup$
So it is all the powers of 2019, except the first power, but including the zeroeth power.
$endgroup$
– L. McDonald
Jan 21 at 21:28
$begingroup$
No, it isn't - it's a 3-cycle, alternating coefficients $1,0,-1$ as we increase. Everything that's $1$ mod $3$ is out.
$endgroup$
– jmerry
Jan 21 at 21:35
$begingroup$
No, it isn't - it's a 3-cycle, alternating coefficients $1,0,-1$ as we increase. Everything that's $1$ mod $3$ is out.
$endgroup$
– jmerry
Jan 21 at 21:35
$begingroup$
Oh, sorry. My mistake. Thanks for the clarification.
$endgroup$
– L. McDonald
Jan 22 at 18:36
$begingroup$
Oh, sorry. My mistake. Thanks for the clarification.
$endgroup$
– L. McDonald
Jan 22 at 18:36
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%2f3080229%2fprove-that-201920182020-is-divisible-by-at-least-three-primes%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
1
$begingroup$
The next one is $397$, a ways off.
$endgroup$
– Ross Millikan
Jan 20 at 6:11
$begingroup$
In addition to those found by WA, $221203$ is a factor.
$endgroup$
– Robert Israel
Jan 20 at 6:20
$begingroup$
And $536314783$
$endgroup$
– Josh B.
Jan 20 at 6:34