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