China Mathematical Olympiad

Suppose a prime $p$ satisfies $p^a\mid m$. Then from the given conditions, there exists an infinite subset $A_1$ of $A$ such that $p$ is coprime to every element in $A_1$. By the pigeonhole principle, there is an infinite subset $A_2$ of $A_1$, such that $x\equiv a(\mathrm{mod}mn)$, for each element $x\in A_2$, where $a$ is a positive integer and $p\nmid a$. Since $(m,n)=1$, we have $(p^a,\frac{mn}{p^a})=1$. By the Chinese Remainder Theorem, we know that $$\{\begin{array}{l}x\equiv a^{-1}(\mathrm{mod}{p}^a),\\ x\equiv 0(\mathrm{mod}\frac{mn}{p^a})\end{array}①$$ have infinitely many solutions. Among them we take one as $x$. Next define $B_p$ as the set of the first $x$ elements in $A_2$, and $S_p$ as the sum of all elements in $B_p$. Then we have $S_p\equiv ax(\mathrm{mod}mn)$. By ① we have $$S_p\equiv ax\equiv 1(\mathrm{mod}{p}^a),S_p\equiv 0(\mathrm{mod}\frac{mn}{p^a}).$$

Suppose that $m=p_1^{a_1}\cdots p_k^{a_k}$, and for every $p_i$ ($1\le i\le k$) select a finite subset $B_i$ of $A$, where $B_i\subset A\setminus (B_1\cup \cdots \cup B_{i-1})$, such that $S_{p_i}$, the sum of all the elements in $B_i$, satisfies $$S_{p_i}\equiv 1(\mathrm{mod}{p}_i^{a_i}),S_{p_i}\equiv 0(\mathrm{mod}\frac{mn}{p_i^{a_i}}).\stackrel{◯}{2}$$ Let $B={\bigcup }_{i=1}^k{B}_i$, whose sum of elements then satisfies $S={\sum }_{i=1}^k{S}_i$. According to ②, we have $S\equiv 1(\mathrm{mod}{p}_i^{a_i})$ ($1\le i\le k$), and $S\equiv 0(\mathrm{mod}n)$. So $B$ is the required subset, and the proof is complete.

Solution 2:

Divide every element in $A$ by $mn$, and let the remainders which occur infinitely be (in order) ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$. We claim that $$({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k,m)=1.\stackrel{◯}{3}$$ Otherwise, assume that $p\mid ({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k,m)$. Then $p\nmid n$, since $(m,n)=1$. By the given conditions we know that there exist infinitely many elements of $A$ not divisible by $p$. But by the definition of ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$, the number of such elements are finite. Then by contradiction, ③ holds. Consequently, there are $x_1,x_2,\dots ,x_k,y$, satisfying ${\alpha }_1{x}_1+{\alpha }_2{x}_2+\cdots +{\alpha }_k{x}_k-ym=1$. Choose a suitable positive integer $r$ such that $rn\equiv 1(\mathrm{mod}m)$. Then $${\alpha }_1(rn{x}_1)+{\alpha }_2(rn{x}_2)+\cdots +{\alpha }_k(rn{x}_k)=rn+rmny.$$ We select in order $r{x}_i$ elements from $A$ such that the remainders by $mn$ are ${\alpha }_i$ ($i=1,2,\dots ,k$). The set of all these elements is acquired.