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.
Best Answer
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$.