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.