2009 Indonesia MO Problems/Problem 1

Problem

Find all positive integers $n\in\{1,2,3,\ldots,2009\}$ such that \[4n^6 + n^3 + 5\] is divisible by $7$.

Solution

First, if $n \equiv 0 \pmod{7}$, then $4n^6 + n^3 + 5 \equiv 5 \pmod{7}$, so $n$ is relatively prime to 7.


Since $n$ is relatively prime to 7, by Euler's Totient Theorem, $n^6 \equiv 1 \pmod{7}$, so $4n^6 + n^3 + 5 \equiv n^3 + 2 \pmod{7}$. This means $n^3 \equiv 5 \pmod{7}$ if $4n^6 + n^3 + 5$ is divisible by 7.


However, testing out all the residues from 1 to 6 reveals that $n^3$ is congruent to 1 or 6 modulo 7, so there are no positive integers such that $4n^6 + n^3 + 5$ is divisible by 7.

See Also

2009 Indonesia MO (Problems)
Preceded by
First Problem
1 2 3 4 5 6 7 8 Followed by
Problem 2
All Indonesia MO Problems and Solutions
Invalid username
Login to AoPS