Proof that if $4$ numbers (not necessarily distinct) are picked from $\{1, 2, \cdots, 20\}$, one can pick $3$ numbers among them and can label these $3$ as $a, b, c$ such that $ax \equiv b \;(\bmod\; c)$ has integral solutions.
Problem
Source: CGMO 2021 P5
Tags: number theory, Diophantine equation
Tintarn
14.08.2021 14:14
The condition is clearly equivalent with $\text{gcd}(a,c) \mid b$.
If two numbers are the same, we may just choose $a=b$.
If there is a prime power $p^k$ (allowing $k=0$) among our four numbers, we can choose $a=p^k$ and just choose $b,c$ with $v_p(c) \le v_p(b)$.
So we may assume that we are given four distinct numbers from $\{6,10,12,14,15,18,20\}$.
If $14$ is in our set, we may again choose $a=14$ and $v_2(c) \le v_2(b)$ (since no other number is divisible by $7$).
Hence we may assume that we are given four distinct numbers from $\{6,10,12,15,18,20\}$.
We may clearly also assume that no number divides another.
So at most one of $\{10,20\}$ and at most two of $\{6,12,18\}$ can be there. So $\{12,15,18\}$ must be there, but then we may choose $a=12, c=15, b=18$. Done.
hansu
19.09.2021 17:16
Here is a neater solution: It is well-known that $ax\equiv b\pmod c$ has a solution iff $\gcd(a,c)\mid b$. Now suppose the $4$ numbers we have picked are $r,s,t,u$. If any two of the numbers are relatively prime, then we are done. Now if $r\mid s$, we can simply choose $c=r$ and $b=s$ and then $x=0$ works. Thus no number from the chosen set of 4 numbers can divide any other. This also lets us assume that all of the 4 numbers are distinct from each other. Also notice that if $\gcd(r,s)=d\ge 7$, we must have $\{r,s\}=\{d,2d\}$, this forces $r\mid s$ or $s\mid r$. Thus $\gcd(r,s)\in \{2,3,4,5,6\}$. But there are $6$ possible pairs possible. Thus two pairs must have the same gcd; $\gcd(w,x)=\gcd(y,z)\implies \gcd(w,x)\mid y$, where $w,x,y,z\in\{p,q,r,s\}$ and $(w,x)\ne (y,z)$.