The largest one of numbers $ p_1^{\alpha_1}, p_2^{\alpha_2}, \cdots, p_t^{\alpha_t}$ is called a $ \textbf{Good Number}$ of positive integer $ n$, if $ \displaystyle n= p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_t^{\alpha_t}$, where $ p_1$, $ p_2$, $ \cdots$, $ p_t$ are pairwisely different primes and $ \alpha_1, \alpha_2, \cdots, \alpha_t$ are positive integers. Let $ n_1, n_2, \cdots, n_{10000}$ be $ 10000$ distinct positive integers such that the $ \textbf{Good Numbers}$ of $ n_1, n_2, \cdots, n_{10000}$ are all equal. Prove that there exist integers $ a_1, a_2, \cdots, a_{10000}$ such that any two of the following $ 10000$ arithmetical progressions $ \{ a_i, a_i + n_i, a_i + 2n_i, a_i + 3n_i, \cdots \}$($ i=1,2, \cdots 10000$) have no common terms.
Problem
Source: China TST 2004 Quiz
Tags: number theory unsolved, number theory
24.08.2019 18:40
Much easier than #2? We'll show that for any set $S = \{s_1, s_2, \cdots, s_n\}$ of distinct positive integers sharing the same Good Number $t$, there exist disjoint arithmetic progressions of common differences $s_1, s_2, \cdots, s_n$ which are pairwise disjoint. This would clearly suffice. By convention, let's set the Good Number of $1$ to be $1.$ Before proving this, observe that if there exist pairwise disjoint arithmetic progressions of common differences $d_1, d_2, \cdots, d_k$, then there exist pairwise disjoint arithmetic progressions of common differences $xd_1, xd_2, \cdots, xd_k$ which are all contained in $x \mathbb{Z} + y$ for any $x, y \in \mathbb{N}.$ Let's now proceed by strong induction on the Good Number $t$ of the positive integers in $S$. When $t = 1$, $\mathbb{Z}$ is an arithmetic progression that works. Suppose the result holds when $t < z.$ When $t = z$, consider the set $T = \{\frac{s}{z} | s \in S\}.$ Notice that every number in $T$ has a Good Number which is strictly less than $z$. Therefore, we can let $T_1, T_2, \cdots, T_{z-1}$ be pairwise disjoint sets such that $T = T_1 \cup T_2 \cup \cdots \cup T_{z-1}$ and each number in $T_i$ has Good Number $i$ for each $1 \le i < z.$ By our observation in the second paragraph, there exists pairwise disjoint arithmetic progressions with common differences $z \cdot T_i$ which are all contained in $z \cdot \mathbb{Z} + i,$ for each $1 \le i < z.$ Taking the union of all these progressions over $1 \le i < z$ finishes. The induction is complete, and hence so is the problem. $\square$