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

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

Contents

Problem

Solution 1

Solution 2

See Also