2012 Indonesia MO Problems/Problem 1
Problem
Show that for any positive integers and , the number is an even non-negative integer.
Solution
We will prove that is even and that is nonnegative separately because each part has its own specific casework.
Lemma 1: is nonnegative
- If and are relatively prime, then . Since , we know that , making nonnegative.
- If and are not relatively prime, then let be the GCD of and . Since , we find that . This means that . Because , we know that and , making nonnegative.
Lemma 2: is even
- If and are even, then and are both even since and share a factor of 2. That means must be even as well since only even numbers are being added or subtracted.
- If is even and is odd, then because has a factor of 2 and because does not have a factor of . That means , making even once again. By symmetry, is even when is odd and is even.
- If and are odd, then and are both odd since and do not have a factor of 2. That means , making even.
By combining Lemmas 1 and 2, we find that for all scenarios, is nonnegative and even.
See Also
2012 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 |