On the smallest size of a set of multiples in modular arithmetic Let $m$ be a positive integer. Let $X_m = \{1,\dots,m-1\}$ and $Y \subseteq X_m$. Let us say that $Y$ covers $X_m$ if all elements of $X_m$ have at least one multiple in $Y$ mod $m$. For example, if $m=6$, then $2$ is a multiple (mod $6$) of $1, 2, 4,$ and $5$. Likewise, $3$ is a multiple of $1, 3,$ and $5$. And since $\{1,2,4,5\}\cup\{1,2,5\} = X_m$, we have that $\{2,3\}$ covers $X_6$, which is the smallest possible choice (together with $\{3,4\}$). I am interested in bounding the size $\gamma(m)=|Y|$ of the smallest subset that covers $X_m$, as a function of $m$.
Clearly, $\gamma$ is not a monotone function, since $\gamma(p)=1$ for every prime $p$ (any number in $X_p$ is multiple of all others mod p). Nonetheless, the worst-case value for $\gamma$ seems to grow with some regularity. Experiments show that the first time that $\gamma(m)=2$ is at $m=6$, that $\gamma(m)=3$ is at $m=30$, and that $\gamma(m)=4$ is at $m=210$. From there, one may speculate that $\gamma(m)$ hits $k$ only when $m = p_k$, where $p_k$ is the $k^{th}$ primorial number (i.e., the product of the first $k$ prime numbers). In such case, the next milestone would be $\gamma(2310)=5$.
My question: Is there a known theorem in modular arithmetics that implies these observations? Now, even if $\gamma$ is unrelated to primorial numbers, I am actually interested in bounding $\gamma(m)$ by some function growing slowly in $m$ (typically, sublogarithmic). If these questions are more commonly formulated in different ways, please comment on this aspect as well.
 A: We have $\gamma(m) = \omega(m)$, the number of distinct prime factors of $m$, therefore we have
$$\limsup_{m \to \infty} \frac{\gamma(m)\log \log m}{\log m} = 1\,,$$
which is a wee bit better than a logarithmic bound.
To see that $\gamma(m) = \omega(m)$, let
$$m = \prod_{\kappa = 1}^{k} p_{\kappa}^{e_{\kappa}} \tag{1}$$
with the $p_{\kappa}$ being distinct primes, and $e_{\kappa} \geqslant 1$ for all $\kappa$.
For each $1 \leqslant r \leqslant k$, there is by the Chinese remainder theorem an $n_r$ such that
$$n_r \equiv 1 \pmod{p_r^{e_r}} \qquad\text{and}\qquad n_r \equiv 0 \pmod{p_{\kappa}^{e_{\kappa}}}$$
for all $\kappa \neq r$.
Since all multiples of $n_r$ are divisible by $p_{\kappa}^{e_{\kappa}}$ if $\kappa \neq r$, this means a $Y$ covering $X_m$ must contain a $y_r \in X_m$ with
$$\prod_{\kappa \neq r} p_{\kappa}^{e_{\kappa}} \mid y_r$$
for each $r \in \{1, \dotsc, k\}$. Thus $\gamma(m) \geqslant k = \omega(m)$.
On the other hand, the $k$-element set
$$Y = \{ p_r^{e_r-1}\cdot n_r : 1 \leqslant r \leqslant k\}$$
covers $X_m$.
Let $1 \leqslant a \leqslant m-1$, and let $r$ be the smallest $\kappa$ such that $p_{\kappa}^{e_{\kappa}}$ does not divide $a$. Then $p_r^{e_r-1}\cdot n_r$ is a multiple of $a$. First, by multiplying with suitable powers of the other primes dividing $m$, we find a multiple $a'$ of $a$ such that $p_r^{e_r}$ is the only prime power on the right hand side of $(1)$ that doesn't divide $a'$. Multiplying $a'$ with a suitable power of $p_r$ we obtain a multiple $a'' = b\cdot p_r^{e_r-1}\cdot n_r$, $p \nmid b$, of $a$. Multiplying with a modular inverse of $b$ modulo $p$ we see that $p_r^{e_r-1}\cdot n_r$ is indeed a multiple of $a$, so $Y$ covers $X_m$.
