Tessellate S.T.E.M.S (2019) - Mathematics - Category C - Set 2 - Objective Problem 5

So we have a rule to add elements to a set. So we need to find sets for which this rule does not add any other elements. Let's start with the three sets (which we can show they do not contain any other elements), and then show there can be no other:

First set :

Start with $S = \lbrace 2 \rbrace$ . If there were another element of this set, it should be written as $\frac{a+b}{\mathrm{gcd}(a,b)}$ . Since only 2 belongs to the set so far, then the only other element we can add is $\frac{2+2}{2} = 2$ . Hence this set is a possible set with the property.

Second set :

Clearly the set $\mathbb{N}$ has this property.

Third set :

Consider the set $\mathbb{N} \setminus \lbrace 1 \rbrace$ . To show that 1 cannot be obtained we need to prove that $\frac{a+b}{\mathrm{gcd}(a,b)} \neq 1$ . This follows from $a+b > \mathrm{gcd}(a,b)$ .

No other sets?

Assume $S$ is such a non-empty set which is not the set with only 2 as an element. Then there is some integer $n \in S$ different from 2. Hence $\frac{n+n}{\mathrm{gcd}(n,n)} = 2$ belongs to the set too. From there on, we distinguish two cases:

First case ( $n$ is odd)

If $n$ is odd, then all odd number above $n$ also belong to $S$ : for any odd number $o$ , one has $\frac{o+2}{\mathrm{gcd}(o,2)} = o+2$ . Consider some odd number $i$ and the odd number $3i$ . Then $\frac{i+3i}{\mathrm{gcd}(i,3i)} = 4$ . So 4 belongs to $S$ . But then $\frac{4+2}{\mathrm{gcd}(4,2)} = 3$ . So 3 belongs to $S$ . So all odd numbers (except 1) belong to $S$ . Since any even number larger than 7 is the sum of two distinct prime numbers (yes, I know, this is the Goldbach conjecture), any even number will belong to the set too. You can get 6 using 10 and 2 (10 you can get out 7 and 3).

Second case ( $n$ is even and not 2)

If $n$ is even, then $\frac{n+2}{\mathrm{gcd}(n,2)} = \frac{n}{2} +1$ . Let $n_1 = \frac{n}{2} +1$ and $n_0=n$ . Note that $n_1$ cannot be 2 (because we excluded that $n_0$ is 2) and that $n_1 <n_0$ . If $n_1$ is odd, go to the first case. Else look at $n_2 := \frac{n_1+2}{\mathrm{gcd}(n_1,2)} = \frac{n_1}{2} +1$ . If $n_2$ is odd, go to the first case. Else note that $n_2<n_1$ (and $n_2$ cannot be 2). Repeat for $n_3$ , $n_4$ , ... until you get an odd number. Note the process cannot go on forever since $n_k < n_{k+1}$ and $n_k$ is never 2.

Once you have an odd number, you have all integers $\geq 2$ (see first case).