# 2012 Indonesia MO Problems/Problem 1

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

## Solution

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.

## See Also

 2012 Indonesia MO (Problems) Preceded byFirst Problem 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed byProblem 2 All Indonesia MO Problems and Solutions
Invalid username
Login to AoPS