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

## 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9537035,"math_prob":1.0000095,"size":1215,"snap":"2023-40-2023-50","text_gpt3_token_len":320,"char_repetition_ratio":0.15111478,"word_repetition_ratio":0.024691358,"special_character_ratio":0.26831275,"punctuation_ratio":0.13178295,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.000009,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106],"im_url_duplicate_count":[null,null,null,null,null,5,null,null,null,null,null,null,null,null,null,null,null,5,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,5,null,5,null,5,null,5,null,5,null,5,null,null,null,null,null,null,null,null,null,10,null,10,null,null,null,null,null,null,null,null,null,null,null,5,null,null,null,5,null,null,null,null,null,5,null,null,null,null,null,null,null,null,null,null,null,null,null,10,null,10,null,null,null,null,null,5,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-09-30T15:14:26Z\",\"WARC-Record-ID\":\"<urn:uuid:5bf6a1c1-de8b-49b8-a208-7c5846fad07e>\",\"Content-Length\":\"44233\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:654b15d3-e407-46ac-85e1-982a487c21ce>\",\"WARC-Concurrent-To\":\"<urn:uuid:a01c41c1-6233-4ddb-97ad-41b4b4a6cb80>\",\"WARC-IP-Address\":\"104.26.11.229\",\"WARC-Target-URI\":\"https://artofproblemsolving.com/wiki/index.php/2012_Indonesia_MO_Problems/Problem_1\",\"WARC-Payload-Digest\":\"sha1:YESB6YILJZOY5JTK5BY4I3PB6DMIMMY7\",\"WARC-Block-Digest\":\"sha1:QMP4VKCVZDJVJVGOYKYQO7DOJXKR6WJO\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233510697.51_warc_CC-MAIN-20230930145921-20230930175921-00101.warc.gz\"}"}