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$ 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.$

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

Page

Toolbox

Search

2003 Indonesia MO Problems/Problem 1

Contents

Problem

Solutions

Solution 1

Solution 2

See Also