Maths Olympiad Prep

Library / /12 of 38

Number theory Difficulty 6.5 National olympiad Prove it China

Let n>1n > 1 be a given integer and AA be an infinite set of positive integers satisfying: for any prime pnp \nmid n, there exist infinitely many elements of AA not divisible by pp. Prove that for any integer m>1m > 1, (m,n)=1(m, n) = 1, there exists a finite subset of AA whose sum of elements, say SS, satisfies S1(modm)S \equiv 1 \pmod m and S0(modn)S \equiv 0 \pmod n.

Solution

Suppose a prime pp satisfies pamp^a \mid m. Then from the given conditions, there exists an infinite subset A1A_1 of AA such that pp is coprime to every element in A1A_1.
By the pigeonhole principle, there is an infinite subset A2A_2 of A1A_1, such that xa(modmn)x \equiv a \pmod{mn}, for each element xA2x \in A_2, where aa is a positive integer and pap \nmid a.
Since (m,n)=1(m, n) = 1, we have (pa,mnpa)=1(p^a, \frac{mn}{p^a}) = 1. By the Chinese Remainder Theorem, we know that
{xa1(modpa),x0(modmnpa) \begin{cases} x \equiv a^{-1} \pmod{p^a}, \\ x \equiv 0 \pmod{\frac{mn}{p^a}} \end{cases} \quad ①
have infinitely many solutions. Among them we take one as xx. Next define BpB_p as the set of the first xx elements in A2A_2, and SpS_p as the sum of all elements in BpB_p. Then we have Spax(modmn)S_p \equiv a x \pmod{mn}. By ① we have
Spax1(modpa),Sp0(modmnpa). S_p \equiv a x \equiv 1 \pmod{p^a}, \quad S_p \equiv 0 \pmod{\frac{mn}{p^a}}.

Suppose that m=p1a1pkakm = p_1^{a_1} \cdots p_k^{a_k}, and for every pip_i (1ik1 \le i \le k) select a finite subset BiB_i of AA, where BiA(B1Bi1)B_i \subset A \setminus (B_1 \cup \cdots \cup B_{i-1}), such that SpiS_{p_i}, the sum of all the elements in BiB_i, satisfies
Spi1(modpiai),Spi0(modmnpiai).2 S_{p_i} \equiv 1 \pmod{p_i^{a_i}}, \quad S_{p_i} \equiv 0 \pmod{\frac{mn}{p_i^{a_i}}}. \qquad \textcircled{2}
Let B=i=1kBiB = \bigcup_{i=1}^k B_i, whose sum of elements then satisfies S=i=1kSiS = \sum_{i=1}^k S_i. According to ②, we have S1(modpiai)S \equiv 1 \pmod{p_i^{a_i}} (1ik1 \le i \le k), and S0(modn)S \equiv 0 \pmod{n}. So BB is the required subset, and the proof is complete.

Solution 2:

Divide every element in AA by mnmn, and let the remainders which occur infinitely be (in order) α1,α2,,αk\alpha_1, \alpha_2, \dots, \alpha_k. We claim that
(α1,α2,,αk,m)=1.3 (\alpha_1, \alpha_2, \dots, \alpha_k, m) = 1. \qquad \textcircled{3}
Otherwise, assume that p(α1,α2,,αk,m)p \mid (\alpha_1, \alpha_2, \dots, \alpha_k, m). Then pnp \nmid n, since (m,n)=1(m,n) = 1. By the given conditions we know that there exist infinitely many elements of AA not divisible by pp. But by the definition of α1,α2,,αk\alpha_1, \alpha_2, \dots, \alpha_k, the number of such elements are finite. Then by contradiction, ③ holds. Consequently, there are x1,x2,,xk,yx_1, x_2, \dots, x_k, y, satisfying α1x1+α2x2++αkxkym=1\alpha_1 x_1 + \alpha_2 x_2 + \dots + \alpha_k x_k - y m = 1. Choose a suitable positive integer rr such that rn1(modm)r n \equiv 1 \pmod{m}. Then
α1(rnx1)+α2(rnx2)++αk(rnxk)=rn+rmny. \alpha_1(r n x_1) + \alpha_2(r n x_2) + \dots + \alpha_k(r n x_k) = r n + r m n y.
We select in order rxir x_i elements from AA such that the remainders by mnmn are αi\alpha_i (i=1,2,,ki = 1, 2, \dots, k). The set of all these elements is acquired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.