Given $N$ positive integers such that the greatest common divisors of all nonempty subsets of them are pairwise distinct. What is the smallest number of prime factors of the product of all $N$ numbers? Proposed by Aleksandr Golovanov
Problem
Source: Ukrainian mathematical olympiad 2018 10.7 and 11.7
Tags: number theory, GCD, greatest common divisor
22.07.2018 23:28
I assume that we don't care about the $\gcd$ of an empty set. In this case, the answer is $N$ for all $N \ge 2$, and $0$ for $N = 1$ (just pick our number to be $1$). For $N \ge 2$, assume that there is a solution with $N - 1$ prime factors. Let these be $p_1, p_2, \ldots p_{N-1}$. Let our numbers be $a_1, a_2, \ldots a_n$. We will now build a set $S$ as follows: for each $i = 1, 2, \ldots N -1$, we pick any integer $a_j$ satisfying the following conditions: $a_j$ does not belong to $S$. $v_{p_i}(a_j)$ is minimal of those $a_k$ not belonging to $S$. We add this $a_j$ to $S$. By the end of this algorithm we have $|S| = N-1$. Let the elements of $S$ be $s_1, s_2, \ldots$, and let $s$ be the number not in $S$. Now it is easy to see that $$\gcd(s_1, s_2, \ldots s_{N-1}) = \gcd(s_1, s_2, \ldots s_{N-1}, s)$$ contradicting the fact that all the gcds are distinct. Now we are left with a construction with $N$ prime factors. This is easy: let $P$ be the product of the first $N$ primes, and let $$a_i = \frac{P}{p_i}$$ for all $1 \le i \le N$, where $p_i$ is the $i$th prime. We can think of each number as a binary string of $N$ bits, with $1$ everywhere except in the $i$th place. Now the gcd of two or more numbers is just the AND of the strings, which is clearly unique.
22.07.2018 23:31
@above thanks, added nonemptiness of subsets
23.07.2018 16:22
In fact if we let the set be $S$, we only need that $gcd(S) \neq gcd(S-{a_i})$ for each i; this guarantees the existence of a prime $p_i$ such that $$v_{p_i} ( a_i ) < v_{p_i} (a_j )$$for all $j \neq i$. Clearly these $p_i$ are distinct and we are done.
16.10.2023 04:16
We claim that the answer is $N$. First, we prove the bound. Assume that there are $N-1$ primes factors. Let them be $p_1,p_2,\cdots, p_{N-1}$. Let $a_i=\prod_{j=1}^{N-1} p_j^{x_{i,j}}$ for each $i$. Let $f(j)=min\{v_{p_j}(a_1),v_{p_j}(a_2),\cdots,v_{p_j}(a_{N-1})\}$ and let $g(j)$ be the corresponding $i$ for each $j$ (that is, if $f(j)=v_{p_j}(a_i)$ then $g(j)=i$, if there are multiple $i$ satisfying, then take the smallest one.) Now we see that $\gcd(a_{g(1)},a_{g(2)},\cdots, a_{g(N-1)})=p_1^{f(1)}p_2^{f(2)}\cdots p_{N-1}^{f(N-1)}=\gcd(a_1,a_2,\cdots,a_N)$ This gives a contradiction, so $N-1$ prime factors is impossible. The construction for $N$ is just $a_i=\prod_{j\neq i} p_j$.