2012 Indonesia MO Problems/Problem 1

Revision as of 18:50, 30 August 2018 by Rockmanex3 (talk | contribs) (Solution to Problem 1 -- LCM and GCD)
(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 by
First Problem
1 2 3 4 5 6 7 8 Followed by
Problem 2
All Indonesia MO Problems and Solutions
Invalid username
Login to AoPS