Find all pairs $(a, b)$ of positive integers such that $a \le b$ and $$ \gcd(x, a) \gcd(x, b) = \gcd(x, 20) \gcd(x, 22) $$holds for every positive integer $x$.
Problem
Source: Baltic Way 2022, Problem 18
Tags: number theory, greatest common divisor
12.11.2022 22:59
I claim the answer are $(2,220),(4,110), (10,44)$ and $(20,22)$. I'll prove this via series of claims. Claim 1: If $p\mid ab$ is a prime then $p\in\{2,5,11\}$.. Indeed, if $q\mid ab$ with $q\notin\{2,5,11\}$ then taking $x=q$ we see that LHS is divisible by $q$ but RHS isn't, a contradiction. Claim 2: $ab=440$. I'll prove $v_p(ab)=v_p(440)$ for $p\in\{2,5,11\}$. Let $p=5$ (also applies to $p=11$). If $v_5(ab)=0$, we clearly have $5\nmid {\rm LHS}$. Now if $v_5(ab)\ge 2$ then taking $x=125$, we see that $25\mid {\rm LHS}$ but $25\nmid {\rm LHS}$. Now I prove $v_2(ab)=3$. If $v_2(ab)\le 2$ then taking $x=8$ we get a clear contradiction. Likewise if $v_2(ab)\ge 4$ is also impossible by taking $x=2^k$ for some large $k$. Hence $ab=440$. Now I show $a,b$ are simultaneously even. Assume $2\nmid a$. Taking $x=4$ we get $v_2({\rm LHS})=2$ whereas $v_2({\rm RHS})=3$, not possible. This leaves $(2,220),(4,110),(10,44)$ and $(20,22)$; all of which easily seen to work.
13.11.2022 17:28
Hm, what about $(10,44)$? In general, it is easy to see that $ \gcd(x, a) \gcd(x, b) = \gcd(x, c) \gcd(x, d) $ holds for all $x$ iff $\{v_p(a),v_p(b)\}=\{v_p(c),v_p(d)\}$ for all primes $p$.