# 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 1

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.

## Solution 2

First, we let $x = n^3$ so that the given equation becomes: $4x^2 + x +5 \equiv 0 \pmod{7}$.

By easily checking each of the 7 possible values of $x$ we find that only $x \equiv 5 \pmod{7}$ satisfy the equation above. But we can also easily check that there's no $n$ such that $n^3 \equiv 5 \pmod{7}$. Therefore no integer can satisfy our equation.

~NounZero