Maths Olympiad Prep

Library / /284 of 299

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Iran

a) Consider nn coprime natural numbers greater than 11 like d1,d2,,dnd_1, d_2, \dots, d_n and arbitrary natural numbers r1,r2,,rnr_1, r_2, \dots, r_n. Prove that there exists a natural number xx, 1x3n1 \le x \le 3^n, that satisfies the following system of modular inequalities:
x≢r1(modd1)x≢r2(modd2)x≢rn(moddn) \begin{array}{l} x \not\equiv r_1 \pmod{d_1} \\ x \not\equiv r_2 \pmod{d_2} \\ \vdots \\ x \not\equiv r_n \pmod{d_n} \end{array}

b) For each real number ϵ>0\epsilon > 0, prove that there exists a number NN such that for each natural number n>Nn > N and natural numbers d1,d2,,dnd_1, d_2, \dots, d_n and r1,r2,,rnr_1, r_2, \dots, r_n, where did_i's (1in1 \le i \le n) are coprime, the above system of inequalities has a solution xx that 1x(2+ϵ)n1 \le x \le (2 + \epsilon)^n.

Solution

a) Without loss of generality, we may suppose that 1<d1<<dn1 < d_1 < \dots < d_n. First, suppose that d1>2d_1 > 2. For each subset I={i1<<ik}{1,2,,n}I = \{i_1 < \dots < i_k\} \subseteq \{1, 2, \dots, n\}, we define dId_I to be equal to the product di1di2dikd_{i_1} d_{i_2} \dots d_{i_k}. By the Chinese Remainder Theorem, we know that the modular equalities
xri1(moddi1),,xrik(moddik)() x \equiv r_{i_1} \pmod{d_{i_1}}, \dots, x \equiv r_{i_k} \pmod{d_{i_k}} \quad (*)
have a unique solution modulo dId_I. Let rIr_I be one of its solutions (If I=I = \emptyset there is no equation and so all integers are solutions. In this case, we set rI=1r_I = 1). So xrI(moddI)x \equiv r_I \pmod{d_I} is equivalent to the system ()(*).

Now suppose that MM is an arbitrary integer. According to the Inclusion-Exclusion Principle, the number of solutions of modular inequalities
x≢r1(modd1),,x≢rn(moddn) x \not\equiv r_1 \pmod{d_1}, \dots, x \not\equiv r_n \pmod{d_n}
which are greater than MM is
I{1,,n}(1)I{1xMxrI(moddI)}. \sum_{I \subseteq \{1, \dots, n\}} (-1)^{|I|} |\{1 \le x \le M \mid x \equiv r_I \pmod{d_I}\}|.
It is easy to see that the number of solutions of each modular equality like xr(modd)x \equiv r \pmod{d} in [1,M][1, M] is Md\lfloor \frac{M}{d} \rfloor or Md\lceil \frac{M}{d} \rceil. In each case, the difference of the number of solutions and Md\frac{M}{d} is at most one, so the number of solutions is greater than
(I{1,,n}(1)IMdI)2n=M(11d11dn+1d1d2+)2n=M(11d1)(11dn)2n. \left( \sum_{I \subseteq \{1, \dots, n\}} (-1)^{|I|} \frac{M}{d_I} \right) - 2^n = M \left( 1 - \frac{1}{d_1} - \dots - \frac{1}{d_n} + \frac{1}{d_1 d_2} + \dots \right) - 2^n \\ = M \left(1 - \frac{1}{d_1}\right) \dots \left(1 - \frac{1}{d_n}\right) - 2^n.

Now, if M=3nM = 3^n and di3d_i \ge 3 for all ii, this number is at least
3n(113)n2n=0. 3^n\left(1 - \frac{1}{3}\right)^n - 2^n = 0.
And so in this case the number of solutions of inequalities is not zero. For the case d1=2d_1 = 2, parity of xx is determined by the parity of r1r_1. Thus, we can use one of substitutions x=2yx = 2y or x=2y1x = 2y - 1. This substitution changes the other inequalities to some new ones in terms of yy
y≢s2(modd2),,y≢sn(moddn) y \not\equiv s_2 \pmod{d_2}, \dots, y \not\equiv s_n \pmod{d_n}
Since 3d2<<dn3 \le d_2 < \dots < d_n, these inequalities have a solution y03n1y_0 \le 3^{n-1}. Hence, we can find a solution for the main inequalities (x)(x) not greater than 2×3n1<3n2 \times 3^{n-1} < 3^n. So the proof is complete.

b) Similar to the previous part, we assume that d1<d2<<dnd_1 < d_2 < \dots < d_n. Therefore, for each ii, we have diid_i \ge i. Furthermore, suppose that ϵ>0\epsilon > 0 has been given. We choose a real number a(22+ϵ,1)a \in (\frac{2}{2+\epsilon}, 1). Obviously, there is some N1N_1 such that 11N1>a1 - \frac{1}{N_1} > a. On the other hand, since (2+ϵ)a2>1\frac{(2+\epsilon)a}{2} > 1, there is N2N_2 such that
((2+ϵ)a2)N2>2N1. \left(\frac{(2 + \epsilon)a}{2}\right)^{N_2} > 2^{N_1}.
Now we set N=N1+N2N = N_1 + N_2. We will show that for each n>Nn > N the number of solutions of the system of modular inequalities is at most (2+ϵ)n(2 + \epsilon)^n. According to part (a), we know that the number of solutions of these inequalities in [1,(2+ϵ)n][1, (2 + \epsilon)^n] is more than
(2+ϵ)n(11d1)(11dn)2n. (2 + \epsilon)^n \left(1 - \frac{1}{d_1}\right) \cdots \left(1 - \frac{1}{d_n}\right) - 2^n.
But for n>Nn > N we have
(2+ϵ)n(11d1)(11dn)(2+ϵ)n(112)(11n+1)(2+ϵ)n(112)N1(11N1)nN1(2+ϵ)n2N1anN1(2+ϵ)n2N1(22+ϵ)nN1((2+ϵ)a2)nN1. \begin{aligned} (2 + \epsilon)^n \left(1 - \frac{1}{d_1}\right) \cdots \left(1 - \frac{1}{d_n}\right) &\ge (2 + \epsilon)^n \left(1 - \frac{1}{2}\right) \cdots \left(1 - \frac{1}{n+1}\right) \\ &\ge (2 + \epsilon)^n \left(1 - \frac{1}{2}\right)^{N_1} \left(1 - \frac{1}{N_1}\right)^{n-N_1} \\ &\ge (2 + \epsilon)^n 2^{-N_1} a^{n-N_1} \\ &\ge (2 + \epsilon)^n 2^{-N_1} \left(\frac{2}{2+\epsilon}\right)^{n-N_1} \left(\frac{(2+\epsilon)a}{2}\right)^{n-N_1}. \end{aligned}
Note that 22+ϵ<1\frac{2}{2+\epsilon} < 1, (2+ϵ)a2>1\frac{(2+\epsilon)a}{2} > 1 and nN1>N2n - N_1 > N_2. Therefore,
(2+ϵ)n2N1(22+ϵ)nN1((2+ϵ)a2)nN1>(2+ϵ)n2N1(22+ϵ)n((2+ϵ)a2)N2>(2+ϵ)n2N1(22+ϵ)n2N1=2n. \begin{aligned} & (2 + \epsilon)^n 2^{-N_1} \left(\frac{2}{2+\epsilon}\right)^{n-N_1} \left(\frac{(2+\epsilon)a}{2}\right)^{n-N_1} > (2 + \epsilon)^n 2^{-N_1} \left(\frac{2}{2+\epsilon}\right)^n \left(\frac{(2+\epsilon)a}{2}\right)^{N_2} \\ & > (2 + \epsilon)^n 2^{-N_1} \left(\frac{2}{2+\epsilon}\right)^n 2^{N_1} \\ & = 2^n. \end{aligned}
And finally, we get
(2+ϵ)n(11d1)(11dn)2n>0 (2 + \epsilon)^n \left(1 - \frac{1}{d_1}\right) \cdots \left(1 - \frac{1}{d_n}\right) - 2^n > 0

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 reproduced verbatim; metadata (topic, difficulty) added by this project.