Initially, two positive integers a and b with a=b are written on a blackboard. At each step, Andrea picks two numbers x and y on the blackboard with x=y 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.
Remark. If x and y are two positive integers, then gcd(x,y) denotes their greatest common divisor and lcm(x,y) their least common multiple.