Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 Indonesia MO Problems/Problem 2"

(Solution to Problem 2 -- lotsa casework)
 
m (→‎Problem)
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
−
Let <math> a,b,c</math> be positive integers. If <math> 30|a+b+c</math>, prove that <math> 30|a^5+b^5+c^5</math>.
+
Let <math> a,b,c</math> be positive integers. If<math>30|a+b+c</math>,prove that <math> 30|a^5+b^5+c^5</math>.
  
 
==Solution==
 
==Solution==

Revision as of 12:58, 16 April 2024

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.

See Also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Indonesia_MO_Problems/Problem_2&oldid=218255"