2003 Indonesia MO Problems/Problem 1

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