Maths Olympiad Prep

Library / /14 of 31

Number theory Difficulty 8.2 Shortlist Prove it Baltic Way

An infinite set BB consisting of non-negative integers has the following property. For each a,bBa, b \in B (a>ba > b) the number ab(a,b)B\frac{a-b}{(a,b)} \in B. Prove that BB contains all non-negative integers. Here (a,b)(a, b) is the greatest common divisor of numbers aa and bb.

Solution

If dd is the greatest common divisor of all the numbers in set BB, let A={b/d:bB}A = \{b/d : b \in B\}. Then for each a,bAa, b \in A (a>ba > b) we have
abd(a,b)A.() \frac{a-b}{d(a,b)} \in A. \quad (*)
Observe that the greatest common divisor of the set AA equals 11, therefore we can find a finite subset A1AA_1 \subset A for which gcdA1=1\gcd A_1 = 1. We may think that the sum of elements of A1A_1 is minimal possible. Choose numbers a,bA1a, b \in A_1 (a>ba > b) and replace aa in the set A1A_1 with abd(a,b)\frac{a-b}{d(a,b)}. The greatest common divisor of the obtained set equals 11. But the sum of numbers decreases by this operation, which contradicts the minimality of A1A_1.

Thus, A1={1}A_1 = \{1\}. Therefore all the numbers in the set AA have residue 11 modulo dd. Take an arbitrary a=kd+1Aa = kd + 1 \in A and b=1b = 1. Then kAk \in A by ()(*) and hence k=ds+1k = ds + 1. But (k,kd+1)=1(k, kd + 1) = 1, therefore kd+1ds1d=ks=(d1)s+1A\frac{kd+1-ds-1}{d} = k - s = (d-1)s + 1 \in A, so ss is divisible by dd. But sAs \in A, therefore s1s-1 is also divisible by dd, hence d=1d = 1 (that means that B=AB = A). Thus we have checked that if a=kd+1=k+1Aa = kd + 1 = k + 1 \in A then a1=kAa-1 = k \in A. Then all non-negative integers belong to AA because it is infinite.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.