# 2003 Indonesia MO Problems/Problem 1

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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$ 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$ 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 byFirst Problem 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed byProblem 2 All Indonesia MO Problems and Solutions
Invalid username
Login to AoPS