A set $X$ of positive integers is said to be iberic if $X$ is a subset of $\{2, 3, \dots, 2018\}$, and whenever $m, n$ are both in $X$, $\gcd(m, n)$ is also in $X$. An iberic set is said to be olympic if it is not properly contained in any other iberic set. Find all olympic iberic sets that contain the number $33$.
Problem
Source: Iberoamerican 2018 Problem 4
Tags: number theory, greatest common divisor
CatalinBordea
26.09.2018 21:44
Note, in first instance, that all elements of an iberic set must be divisible by the same prime. Otherwise, there would exist two numbers in it whose $ \text{gcd} $ would be $ 1, $ but this cannot be an element of an iberic set. Since $ 33 $ is an element of an iberic set, all elements must be divisible by $ 3 $ or $ 11. $ Assume all elements are divisible by $ 3. $ We want to build the largest iberic set containing $ 3. $ It is easy to verify that $ \{ 3,6,9,...,2016\} $ is the only olympic set whose elements are divisible by $ 3. $ Likewise, $ \{ 11,22,33,...,2013\} $ is the only olympic set whose elements are divisible by $ 11. $ So, the answer is $ \{ 3,6,9,...,2016\} $ and $ \{ 11,22,33,...,2013\} . $
trying_to_solve_br
27.07.2021 21:34
mehhhhh First note that $X_1=\{ 3,6,9,12,...,2016\}$ and $X_2={11,22,33,...,2013}$ work. Then note that $gcd(33,x)=\{ 1,3,11,33\}$, but it can't be $1$, otherwise $1$ would belong to $X$, but then $X$ would not be a subset of $\{ 2,3,4...,2018 \}$. If it was $33$, then it would be contained in $X_1$ and $X_2$. Thus, for all $x$ in the iberic set should be either a multiple of 3 or 11. But notice also that $x<2018$ and that if we have a olympic and iberic set $a_1,a_2,...,a_N$ with multiples of 3, that doesn't cover all the multiples of 3 less than 2016, then it is contained in one that has. The same for multiples of 11. Hence $X_1,X_2$ are our only possibilities.