Find if a given number must be in a set that is closed under gcd and lcm with some given elements

Question

Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated).

There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ and $\text{lcm}(A, B)$ are also in $S$.

You are given $n$ positive integers $a_1$, $a_2$, ..., $a_n$, which are elements of $S$ and a positive integer $k$. Find whether $k$ must be an element of $S$.

For example, for 2 integers $45$ and $75$ and $k=15$, the answer is "YES" since $\gcd(45,75)=15$.
For example, for 2 integers $45$ and $75$ and $k=9$, the answer is "NO" since $S$ can be $\{1, 15, 45, 75, 225\}$, which does not contain $9$.

I stumbled into it and lost an entire afternoon to it. Does anyone have an idea how to start? I could theoretically run a brute-force that lasts forever, but that seems to just defeat the purpose of the question.

Answer 1

The idea

Without listing all elements in $S$, we can, following a usual approach, try checking whether $k$ is in $S$ "from the perspective of each distinct prime factor" of $k$. The subtlety and the difficulty is how and what we can do at each distinct prime factor.

A simple and fast algorithm

1. If $k=1$, return "YES" if all $a_i$'s are relatively prime and "NO" otherwise.
2. Now $k$ has at least one prime factor. Factorize $k$ to obtain $k=\prod_{j=1}^\ell{p_j}^{e_j}$, where $\ell\ge1$, $p_j$ is a prime, $e_j\ge1$ for all $j=1, \cdots, \ell$.
3. For $j$ from $1$ to $\ell$, do the following.
   1. Find all multiples of ${p_j}^{e_j}$ among $a_i$'s. If there is none, return "NO".
   2. If $k$ is not a multiple of the greatest common divisor of those multiples, return "NO".
4. Return "YES".

Time-complexity and space complexity

The algorithm runs in $O(\sqrt{M}+\max(n,\log M)\max(1, \log M))$ time, where $M=\max(a_1,\cdots, a_n)$.

It can be implemented with $O(1)$ auxiliary space.

An implementation in Python runs well within half a second for each test case at the online judge, where $n\le 50000$ and $M\le10^{12}$. Of course, your mileage might vary.

Proof of Correctness.

Call a set of positive integers dm-closed if it is closed under gcd and lcm.

Let $U$ be the set of all factors of the least common multiples of all $a_i$'s. Verify that $U$ is a dm-closed set that contain all $a_i$'s.

Let us prove that the algorithm returns 'NO' $\implies$ $k$ is not in some dm-closed set that contains all $a_i$'s. There are three cases.

1. The algorithm returns 'NO' at step 1.1. That means there is a number $h>1$ such that all $a_i$'s are multiples of $h$. Consider the set of all numbers in $U$ that are multiples of $h$.
   That set is a dm-closed set that contains all $a_i$'s but does not contain $k=1$.
2. The algorithm returns 'NO' at step 3.1. That means for some $j$, no $a_i$ is a multiple of ${p_j}^{e_j}$. Consider the set of all numbers in $U$ that are not multiples of ${p_j}^{e_j}$.
   That set is a dm-closed set that contains all $a_i$'s, which does not contain $k$, since $k$ is a multiple of ${p_j}^{e_j}$.
3. The algorithm returns 'NO' at step 3.2. That means for some $j$, $k$ is not a multiple of $g_j$, the greatest common divisor of all $a_i$'s that are multiples of ${p_j}^{e_j}$. Consider set $$D=\{u\in U\mid \text{either }u\text{ is not a multiple of }{p_j}^{e_j}\text{ or }u\text{ is a multiple of }g_j\}.$$ $D$ is a dm-closed set that contains all $a_i$'s, which does not contain $k$, since $k$ is a multiple of ${p_j}^{e_j}$ but not a multiple of $g_j$.

Let us prove that the algorithm returns 'YES' $\implies$ $k$ is in every dm-closed set that contains all $a_i$'s. Let $S$ be an arbitrary dm-closed set that contains all $a_i$'s. There are two cases.

1. The algorithm returns 'YES' at step 1.1. That means the greatest common divisor of all $a_i$'s is 1. Since $S$ is closed under gcd and $S$ contains all $a_i$'s, $S$ must contain 1.

2. The algorithm returns 'YES' at step 4. That means the algorithm does not return at step 3.1 nor at step 3.2. So, for all $j$, $k$ is a multiple of $g_j$, the greatest common divisor of all $a_i$'s that are multiples of ${p_j}^{e_j}$. Note that $g_j$ is a multiple of ${p_j}^{e_j}$. Let $h$ be the least common multiple of all $g_j$. Note that all $g_j$ are in $S$, and hence so is $h$.

   • Since for all $j$, $k$ is a multiple of $g_j$, $k$ is a multiple of $h$.
   • Since for all $j$, $g_j$ is a multiple of ${p_j}^{e_j}$, so is $h$. Since ${p_j}^{e_j}$'s are pairwise relatively prime, $h$ is a multiple of $k$, the product of all ${p_j}^{e_j}$'s.

   So $k$ and $h$ are multiples to each other. Hence $k=h$. Since $h$ is in $S$, so is $k$. $\quad\checkmark$

Answer 2

Take John’s answer. However, we don’t actually need a prime factorisation. Let’s say we have a large x which might be prime or composite (and finding out takes a long time). Instead of trying to factor x, we calculate the gcd with the other numbers. A gcd ≠ 1 means we found a factor. If all gcds are = 1 then it doesn’t matter whether x is composite or not.

With this incomplete information we can determine if k has to be an element of S.