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 21: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
Invalid username
Login to AoPS