2013 Indonesia MO Problems/Problem 1

Problem

Show that for any positive integers $a$ and $b$ , the number $n=\mathrm{LCM}(a,b)+\mathrm{GCD}(a,b)-a-b$ is an even non-negative integer.

We will prove that $n$ is even and that $n$ is nonnegative separately because each part has its own specific casework.

Lemma 1: $n$ is nonnegative

If $a$ and $b$ are relatively prime, then $n = ab + 1 - a - b = (a-1)(b-1)$ . Since $a,b \ge 1$ , we know that $n \ge 0$ , making $n$ nonnegative.
If $a$ and $b$ are not relatively prime, then let $g$ be the GCD of $a$ and $b$ . Since $\mathrm{LCM}(a,b) \cdot \mathrm{GCD}(a,b) = ab$ , we find that $\mathrm{LCM}(a,b) = \tfrac{ab}{g}$ . This means that $n = \tfrac{ab}{g} + g - a - b = (\tfrac{a}{g} - 1)(b - g)$ . Because $a,b \ge g$ , we know that $\tfrac{a}{g} - 1 \ge 0$ and $b \ge 0$ , making $n$ nonnegative.

Lemma 2: $n$ is even

If $a$ and $b$ are even, then $\mathrm{LCM}(a,b)$ and $\mathrm{GCD}(a,b)$ are both even since $a$ and $b$ share a factor of 2. That means $n$ must be even as well since only even numbers are being added or subtracted.
If $a$ is even and $b$ is odd, then $\mathrm{LCM}(a,b) \equiv 0 \pmod{2}$ because $a$ has a factor of 2 and $\mathrm{GCD}(a,b) \equiv 1 \pmod{2}$ because $b$ does not have a factor of $2$ . That means $n \equiv 0 + 1 - 0 - 1 \equiv 0 \pmod{2}$ , making $n$ even once again. By symmetry, $n$ is even when $a$ is odd and $b$ is even.
If $a$ and $b$ are odd, then $\mathrm{LCM}(a,b)$ and $\mathrm{GCD}(a,b)$ are both odd since $a$ and $b$ do not have a factor of 2. That means $n \equiv 1 + 1 - 1 - 1 \equiv 0 \pmod{2}$ , making $n$ even.

By combining Lemmas 1 and 2, we find that for all scenarios, $n$ is nonnegative and even.

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