3
$\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.

$\endgroup$
3
  • 1
    $\begingroup$ The next one is $397$, a ways off. $\endgroup$ Commented Jan 20, 2019 at 6:11
  • $\begingroup$ In addition to those found by WA, $221203$ is a factor. $\endgroup$ Commented Jan 20, 2019 at 6:20
  • $\begingroup$ And $536314783$ $\endgroup$
    – Josh B.
    Commented Jan 20, 2019 at 6:34

2 Answers 2

7
$\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 $2018\equiv 2\mod 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^2\equiv 672n+1345\mod 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 $397\cdot 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$.

$\endgroup$
5
  • $\begingroup$ In the last expression, I haven’t checked, but is there supposed to be a + 2019 as ($2019^1$) towards the end? $\endgroup$
    – Logan M
    Commented Jan 20, 2019 at 8:09
  • $\begingroup$ No, that last term you're thinking of is the +1. $\endgroup$
    – jmerry
    Commented Jan 20, 2019 at 8:34
  • $\begingroup$ So it is all the powers of 2019, except the first power, but including the zeroeth power. $\endgroup$
    – Logan M
    Commented Jan 21, 2019 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
    Commented Jan 21, 2019 at 21:35
  • $\begingroup$ Oh, sorry. My mistake. Thanks for the clarification. $\endgroup$
    – Logan M
    Commented Jan 22, 2019 at 18:36
1
$\begingroup$

We know that,

$f(x)=\Sigma_{0≤i≤p-1} x^{a_i} $

where $a_i$ are non-negative integers and p is a prime. If they form a reduced residue system modulo p, then f(x) is divisible by

$g(x)=\Sigma_{0≤i≤p-1} x^{i} $

We can write $2019^{2018}+2020$ as $2019^{2018}+2019+1$

By the above lemma,

$x^2+x+1 $ is a factor of $x^{2018}+x+1$

Now, by doing a long divison you can find other two factors (which are prime).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .