2006 Indonesia MO Problems/Problem 2
Problem
Let be positive integers. If , prove that .
Solution
To prove that is a multiple of 30, we need to prove that is a multiple of 2, 3, and 5 given that is a multiple of 2, 3, and 5.
Lemma 1: is a multiple of 2 if is a multiple of 2
The cases where is even is either when all are even or exactly one of the variables are even.
- Let be even. That makes even as well.
- WLOG, let be the only even number. That means and , making even as well.
From all the cases, is a multiple of 2 if is even.
Lemma 2: is a multiple of 3 if is a multiple of 3
The cases where 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 be a multiple of 3. That makes a multiple of 3 as well.
- Let be congruent to 1 modulo 3. That means , making a multiple of 3 as well.
- WLOG, let , , and . That means , , and , making a multiple of 3 as well.
From all the cases, is a multiple of 3 if is a multiple of 3.
Lemma 3: is a multiple of 5 if is a multiple of 5
We split the case where either exactly zero, one, two, or three of are a multiple of 5.
- Let be relatively prime to 5. By Fermat's Little Theorem, , , and . Since , must be a multiple of 5.
- WLOG, let be a multiple of 5 and be relatively prime to 5. That means . By Fermat's Little Theorem, and , so .
- WLOG, let be a multiple of 5 and be relatively prime to 5. Since and , , so this case can not happen.
- Let all of be a multiple of 5. That means is a multiple of 5 as well.
From all the valid cases, is a multiple of 5 if is a multiple of 5.
From Lemmas 1, 2, and 3, is a multiple of 30 since is a multiple of 2, 3, 5 if 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 |