IMO 1974 SL 7

Problem

II 1 (POL 2) Let ai, bi be coprime positive integers for i = 1, 2, . . . , k, and m the least common multiple of b1, . . . , bk. Prove that the greatest common divisor of a1 m b1 , . . . , ak m bk equals the greatest common divisor of a1, . . . , ak.

Solution

Consider an arbitrary prime number p. If p | m, then there exists bi that is divisible by the same power of p as m. Then p divides neither ai m bi nor ai, because (ai, bi) = 1. If otherwise p ∤m, then m bi is not divisible by p for any i, hence p divides ai and ai m bi to the same power. Therefore (a1, . . . , ak) and  a1 m b1 , . . . , ak m bk

have the same factorization; hence they are equal. Second solution. For k = 2 we easily verify the formula  m a1 b1 , m a2 b2

= m b1b2 (a1b2, a2b1) = b1b2 [b1, b2](a1, a2)(b1, b2) = (a1, a2), since [b1, b2] \cdot (b1, b2) = b1b2. We proceed by induction:  a1 m b1 , . . . , ak m bk , ak+1 m bk+1 

 m [b1, . . . , bk](a1, . . . , ak), ak+1 m bk+1  = (a1, . . . , ak, ak+1).