A set of five different positive integers is called virtual if the greatest common divisor of any three of its elements is greater than $1$, but the greatest common divisor of any four of its elements is equal to $1$. Prove that, in any virtual set, the product of its elements has at least $2020$ distinct positive divisors. Proposed by Víctor Almendra
Problem
Source: Mexico National Olympiad 2020 P1
Tags: combinatorics, number theory, greatest common divisor, vector
12.11.2020 05:12
Let $A=\{a_1,a_2,a_3,a_4,a_5\}$ be the elements. For each permutation of three numbers $a_i$ we have a prime which divides all three elements, we claim this primes are distinct. For the sake of contradiction suppose $p$ is a prime such that divides two permutations $B=\{b_1,b_2,b_3\}$ and $C=\{c_1,c_2,c_3\}$. So in fact $p\mid b_1,b_2,b_3$ and $p\mid c_1,c_2,c_3$. But by the condition this prime can't divides any element of $A\setminus B$ and $A\setminus C$, moreover $A\setminus B\cap A\setminus C\neq \emptyset$ so this $p$ in fact can't divides either an element of $B$ or $C$, contradiction. So $\prod a_i$ has at least $\binom{5}{3}$ distinct prime divisors, that is $2^{10}$ distinct positive divisors. Finally fix an element $a_k$ so following by the three permutations we have $a_k$ has at least $3$ distinct prime divisors. So $\prod a_i$ is a product of $15$ primes where at least $10$ are distinct so we clearly have it is greater than $2^{10}\cdot 2=2^11>2020$.
12.11.2020 05:16
plagueis wrote: A set of five different positive integers is called virtual if the greatest common divisor of any three of its elements is greater than $1$, but the greatest common divisor of any four of its elements is equal to $1$. Prove that, in any virtual set, the product of its elements has at least $2020$ distinct positive divisors. Proposed by Víctor Almendra Exactly. I think by the way the bound $2020$ can be strengthened. Find $10$ distinct primes $p_i$, $1\le i\le 10$. Note that each $p_i$ divides three of numbers. Hence in the product $\prod_{1\le j\le 5}a_j$, the exponent of each such $p_i$ is at least $3$, thus it appears the number of divisors of this number is at least $4^{10}\gg 2020$.
30.10.2022 20:52
Let $B = \{ b_{1}, b_{2}, ..., b_{5}\}$ be a virtual set. Since the gcd of any three numbers is greater than $1$ but the gcd of any four numbers is exactly 1 then the gcd of any combination of 3 numbers from $B$ is different, to see this, suppose WLOG that $\gcd({b_{1}, b_{2}, b_{3}}) = d = \gcd({b_{1}, b_{2}, b_{4}}) $ then $\gcd({b_{1}, b_{2}, b_{3}, b_{4}}) = d >1$ a contradiction. So since there are exactly $\binom{5}{3} =10$ ways of express a different gcd out of 3 numbers from $B$ now, suppose the worst possible case for the product $\prod_{1\le j\le 5}b_j$ which happens when every of the $10$ gcd's are a prime. In order for the condition of the problem to hold every gcd appears actually 3 times in the PPF of the 5 numbers in $B$. So ($d(n)$ is the divisor count function) $$ d\left(\prod_{1\le j\le 5}b_j \right) = 4^{10} > 2020 $$