Maths Olympiad Prep

Library / IMO Shortlist /200 of 365

IMO Shortlist, 2021

Number theory Difficulty 8.7 Shortlist Prove it IMO

Let SS be an infinite set of positive integers, such that there exist four pairwise distinct a,b,c,d∈Sa, b, c, d \in S with gcd⁡(a,b)≠gcd⁡(c,d)\operatorname{gcd}(a, b) \neq \operatorname{gcd}(c, d). Prove that there exist three pairwise distinct x,y,z∈Sx, y, z \in S such that gcd⁡(x,y)=gcd⁡(y,z)≠gcd⁡(z,x)\operatorname{gcd}(x, y)=\operatorname{gcd}(y, z) \neq \operatorname{gcd}(z, x).

Solution

There exists α∈S\alpha \in S so that {gcd⁡(α,s)∣s∈S,s≠α}\{\operatorname{gcd}(\alpha, s) \mid s \in S, s \neq \alpha\} contains at least two elements. Since α\alpha has only finitely many divisors, there is a d∣αd \mid \alpha such that the set B={β∈S∣gcd⁡(α,β)=d}B=\{\beta \in S \mid \operatorname{gcd}(\alpha, \beta)=d\} is infinite. Pick γ∈S\gamma \in S so that gcd⁡(α,γ)≠d\operatorname{gcd}(\alpha, \gamma) \neq d. Pick β1,β2∈B\beta_{1}, \beta_{2} \in B so that gcd⁡(β1,γ)=gcd⁡(β2,γ)=:d′\operatorname{gcd}\left(\beta_{1}, \gamma\right)=\operatorname{gcd}\left(\beta_{2}, \gamma\right)=: d'. If d=d′d=d', then gcd⁡(α,β1)=gcd⁡(γ,β1)≠gcd⁡(α,γ)\operatorname{gcd}\left(\alpha, \beta_{1}\right)=\operatorname{gcd}\left(\gamma, \beta_{1}\right) \neq \operatorname{gcd}(\alpha, \gamma). If d≠d′d \neq d', then either gcd⁡(α,β1)=gcd⁡(α,β2)=d\operatorname{gcd}\left(\alpha, \beta_{1}\right)=\operatorname{gcd}\left(\alpha, \beta_{2}\right)=d and gcd⁡(β1,β2)≠d\operatorname{gcd}\left(\beta_{1}, \beta_{2}\right) \neq d or gcd⁡(γ,β1)=gcd⁡(γ,β2)=d′\operatorname{gcd}\left(\gamma, \beta_{1}\right)=\operatorname{gcd}\left(\gamma, \beta_{2}\right)=d' and gcd⁡(β1,β2)≠d′\operatorname{gcd}\left(\beta_{1}, \beta_{2}\right) \neq d'.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.