Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 Indonesia MO Problems/Problem 1"

(Solution to Problem 1 -- basic NT)
 
(→‎Solution)
 
Line 5: Line 5:
 
is divisible by <math> 7</math>.
 
is divisible by <math> 7</math>.
  
−
==Solution==
+
==Solution 1==
  
 
First, if <math>n \equiv 0 \pmod{7}</math>, then <math>4n^6 + n^3 + 5 \equiv 5 \pmod{7}</math>, so <math>n</math> is relatively prime to 7.
 
First, if <math>n \equiv 0 \pmod{7}</math>, then <math>4n^6 + n^3 + 5 \equiv 5 \pmod{7}</math>, so <math>n</math> is relatively prime to 7.
Line 13: Line 13:
  
 
<br>
 
<br>
−
However, testing out all the residues from 1 to 6 reveals that <math>n^3</math> is congruent to 1 or 6 modulo 7, so there are no positive integers such that <math>4n^6 + n^3 + 5</math> is divisible by 7.  
+
However, testing out all the residues from 1 to 6 reveals that <math>n^3</math> is congruent to 1 or 6 modulo 7, so there are no positive integers such that <math>4n^6 + n^3 + 5</math> is divisible by 7.
 +
 
 +
==Solution 2==
 +
 
 +
First, we let <math>x = n^3</math> so that the given equation becomes: <math>4x^2 + x +5 \equiv 0 \pmod{7}</math>.
 +
 
 +
<br>
 +
 
 +
By easily checking each of the 7 possible values of <math>x</math> we find that only <math>x \equiv 5 \pmod{7}</math> satisfy the equation above. But we can also easily check that there's no <math>n</math> such that <math>n^3 \equiv 5 \pmod{7}</math>. Therefore no integer can satisfy our equation.
 +
 
 +
~NounZero
  
 
==See Also==
 
==See Also==

Latest revision as of 16:02, 23 December 2020

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_Indonesia_MO_Problems/Problem_1&oldid=140391"