2006 Indonesia MO Problems/Problem 2

Problem

Let $a,b,c$ be positive integers. If $30|a+b+c$ , prove that $30|a^5+b^5+c^5$ .

Solution

To prove that $a^5+b^5+c^5$ is a multiple of 30, we need to prove that $a^5 + b^5 + c^5$ is a multiple of 2, 3, and 5 given that $a+b+c$ is a multiple of 2, 3, and 5.

Lemma 1: $a^5 + b^5 + c^5$ is a multiple of 2 if $a+b+c$ is a multiple of 2
The cases where $a+b+c$ is even is either when all are even or exactly one of the variables are even.

Let $a,b,c$ be even. That makes $a^5+b^5+c^5$ even as well.
WLOG, let $a$ be the only even number. That means $a^5 \equiv 0 \pmod{0}$ and $b^5 + c^5 \equiv 0 \pmod{2}$ , making $a^5 + b^5 + c^5$ even as well.

From all the cases, $a^5 + b^5 + c^5$ is a multiple of 2 if $a+b+c$ is even.

Lemma 2: $a^5 + b^5 + c^5$ is a multiple of 3 if $a+b+c$ is a multiple of 3
The cases where $a+b+c$ is even is either when all are congruent to 0 modulo 3, when all are congruent to 1 modulo 3, or when one is congruent to 1, one is congruent to 2, and one is congruent to 0 modulo 3.

Let $a,b,c$ be a multiple of 3. That makes $a^5 + b^5 + c^5$ a multiple of 3 as well.
Let $a,b,c$ be congruent to 1 modulo 3. That means $a^5, b^5, c^5 \equiv 1 \pmod{3}$ , making $a^5 + b^5 + c^5$ a multiple of 3 as well.
WLOG, let $a \equiv 0 \pmod{3}$ , $b \equiv 1 \pmod{3}$ , and $c \equiv 2 \pmod{3}$ . That means $a^5 \equiv 0 \pmod{3}$ , $b^5 \equiv 1 \pmod{3}$ , and $c^5 \equiv 2 \pmod{3}$ , making $a^5 + b^5 + c^5$ a multiple of 3 as well.

From all the cases, $a^5 + b^5 + c^5$ is a multiple of 3 if $a+b+c$ is a multiple of 3.

Lemma 3: $a^5 + b^5 + c^5$ is a multiple of 5 if $a+b+c$ is a multiple of 5
We split the case where either exactly zero, one, two, or three of $a,b,c$ are a multiple of 5.

Let $a,b,c$ be relatively prime to 5. By Fermat's Little Theorem, $a^5 \equiv a \pmod{5}$ , $b^5 \equiv b \pmod{5}$ , and $c^5 \equiv c \pmod{5}$ . Since $a+b+c \equiv 0 \pmod{5}$ , $a^5 + b^5 + c^5$ must be a multiple of 5.
WLOG, let $a$ be a multiple of 5 and $b,c$ be relatively prime to 5. That means $b+c \equiv 0 \pmod{5}$ . By Fermat's Little Theorem, $b^5 \equiv b \pmod{5}$ and $c^5 \equiv c \pmod{5}$ , so $a^5 + b^5 + c^5 \equiv 0 \pmod{5}$ .
WLOG, let $a,b$ be a multiple of 5 and $c$ be relatively prime to 5. Since $a+b+c \equiv 0 \pmod{5}$ and $a,b \equiv 0 \pmod{5}$ , $c \equiv 0 \pmod{5}$ , so this case can not happen.
Let all of $a,b,c$ be a multiple of 5. That means $a^5 + b^5 + c^5$ is a multiple of 5 as well.

From all the valid cases, $a^5 + b^5 + c^5$ is a multiple of 5 if $a+b+c$ is a multiple of 5.

From Lemmas 1, 2, and 3, $a^5 + b^5 + c^5$ is a multiple of 30 since $a^5 + b^5 + c^5$ is a multiple of 2, 3, 5 if $a+b+c$ is a multiple of 30.

2006 Indonesia MO (Problems)
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8	Followed by Problem 3
All Indonesia MO Problems and Solutions

Page

Toolbox

Search

2006 Indonesia MO Problems/Problem 2

Problem

Solution

See Also