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.

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

Page

Toolbox

Search

2009 Indonesia MO Problems/Problem 1

Problem

Solution

See Also