16th APMO 2004 Problem 1 Find all non-empty finite sets S of positive integers such that if m,n ∈ S, then (m+n)/gcd(m,n) ∈ S.
Problem 827
Official solution
{2} Solution Let k ∈ S. Then (k+k)/gcd(k,k) = 2 ∈ S. Let M be the largest odd element of S. Then (M+2)/gcd(M,2) = M+2 ∈ S. Contradiction. So all elements of S are even. Let m = 2n be the smallest element of S greater than 2. Then (m+2)/2 = n+1 ∈ S. But n must be > 1 (or m = 2), so 2n > n+1. Hence 2n = 2 (by minimality of m), so n = 1. Contradiction. So S has no elements apart from 2. 16th APMO 2004 © John Scholes [email protected] 22 Mar 2004 Last corrected/updated 22 Mar 04