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 "2003 Indonesia MO Problems/Problem 1"

(Solution to Problem 1 -- Fermat makes it faster)
 
m (→‎Solution 2)
 
Line 14: Line 14:
  
 
<br>
 
<br>
−
'''Lemma 1: <math>a</math> is divisible by <math>2</math>'''<br>
+
'''Lemma 1: <math>a^9 - a</math> is divisible by <math>2</math>'''<br>
 
Obviously if <math>a \equiv 0 \pmod{2},</math> since <math>a</math> is a factor of <math>a^9 - a,</math> the expression is divisible by <math>2.</math>  If <math>a \equiv 1 \pmod{2},</math> then <math>a-1 \equiv 0 \pmod{2},</math> making <math>a^9 - a</math> divisible by <math>2.</math>
 
Obviously if <math>a \equiv 0 \pmod{2},</math> since <math>a</math> is a factor of <math>a^9 - a,</math> the expression is divisible by <math>2.</math>  If <math>a \equiv 1 \pmod{2},</math> then <math>a-1 \equiv 0 \pmod{2},</math> making <math>a^9 - a</math> divisible by <math>2.</math>
  
 
<br>
 
<br>
−
'''Lemma 2: <math>a</math> is divisible by <math>3</math>'''<br>
+
'''Lemma 2: <math>a^9 - a</math> is divisible by <math>3</math>'''<br>
 
Obviously if <math>a \equiv 0 \pmod{3},</math> since <math>a</math> is a factor of <math>a^9 - a,</math> the expression is divisible by <math>3.</math>  If <math>a \equiv 1 \pmod{3},</math> then <math>a-1 \equiv 0 \pmod{3},</math> making <math>a^9 - a</math> divisible by <math>3</math>.  Also, if <math>a \equiv 2 \pmod{3},</math> then <math>a+1 \equiv 0 \pmod{3},</math> making <math>a^9 - a</math> divisible by <math>3</math>.
 
Obviously if <math>a \equiv 0 \pmod{3},</math> since <math>a</math> is a factor of <math>a^9 - a,</math> the expression is divisible by <math>3.</math>  If <math>a \equiv 1 \pmod{3},</math> then <math>a-1 \equiv 0 \pmod{3},</math> making <math>a^9 - a</math> divisible by <math>3</math>.  Also, if <math>a \equiv 2 \pmod{3},</math> then <math>a+1 \equiv 0 \pmod{3},</math> making <math>a^9 - a</math> divisible by <math>3</math>.
  

Latest revision as of 20:10, 7 August 2018

Problem

Prove that $a^9 - a$ is divisible by $6$ for every integers $a$.

Solutions

Solution 1

By Fermat's Little Theorem, $a^2 \equiv a \pmod{2},$ so $a^9 \equiv (a^2)^4 \cdot a \equiv a \pmod{2}.$ Also, $a^3 \equiv a \pmod{3},$ so $a^9 \equiv (a^3)^3 \equiv a \pmod{3}.$ That means $a^9 - a$ is divisible by $2$ and $3,$ so $a^9 - a$ is divisible by $6$ for every integer $a.$

Solution 2

The expression $a^9 - a$ can be factored into $a(a^4+1)(a^2+1)(a+1)(a-1).$ In order to show that $a^9 - a$ is divisible by $6,$ we need to show that $a$ is divisible by $2$ and $3.$


Lemma 1: $a^9 - a$ is divisible by $2$
Obviously if $a \equiv 0 \pmod{2},$ since $a$ is a factor of $a^9 - a,$ the expression is divisible by $2.$ If $a \equiv 1 \pmod{2},$ then $a-1 \equiv 0 \pmod{2},$ making $a^9 - a$ divisible by $2.$


Lemma 2: $a^9 - a$ is divisible by $3$
Obviously if $a \equiv 0 \pmod{3},$ since $a$ is a factor of $a^9 - a,$ the expression is divisible by $3.$ If $a \equiv 1 \pmod{3},$ then $a-1 \equiv 0 \pmod{3},$ making $a^9 - a$ divisible by $3$. Also, if $a \equiv 2 \pmod{3},$ then $a+1 \equiv 0 \pmod{3},$ making $a^9 - a$ divisible by $3$.


Since we've shown that $a^9 - a$ is divisible by $2$ and $3$ for all $a,$ the value $a^9 - a$ is divisible by $6.$

See Also

2003 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=2003_Indonesia_MO_Problems/Problem_1&oldid=96849"