Problem

Source: MEMO 2022 I4

Tags: number theory



Initially, two distinct positive integers $a$ and $b$ are written on a blackboard. At each step, Andrea picks two distinct numbers $x$ and $y$ on the blackboard and writes the number $gcd(x, y) + lcm(x, y)$ on the blackboard as well. Let $n$ be a positive integer. Prove that, regardless of the values of $a$ and $b$, Andrea can perform a finite number of steps such that a multiple of $n$ appears on the blackboard.