Library / Ukrainian National Mathematical Olympiad, 3rd Round /12 of 24

Ukrainian National Mathematical Olympiad, 3rd Round

Number theory Difficulty 5.2 AIME, harder Prove it Ukraine

Suppose that for two natural numbers $m, n$ the following equality holds
$m+n = [m,n] + (m,n),$
Where $[m,n]$ and $(m,n)$ are the least common multiple and the greatest common divisor of $m,n$ respectively. Prove that one number is divisible by another.

Solution

Let $d = (m,n)$ , then $m = ad$ , $n = bd$ , and using the formula $mn = [m,n] \cdot (m,n)$ we get, that $[m,n] = abd$ . This implies that $abd + d = ad + bd \Leftrightarrow d(a-1)(b-1) = 0$ , which is possible if either $a=1$ or $b=1$ and the result follows.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.