2009 Indonesia MO Problems/Problem 1

Revision as of 16:02, 23 December 2020 by Nounzero (talk | contribs) (Solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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