Number theoryDifficulty 7.6National Olympiad, round 2Prove itIran
a) Consider n coprime natural numbers greater than 1 like d1,d2,…,dn and arbitrary natural numbers r1,r2,…,rn. Prove that there exists a natural number x, 1≤x≤3n, that satisfies the following system of modular inequalities: x≡r1(modd1)x≡r2(modd2)⋮x≡rn(moddn)
b) For each real number ϵ>0, prove that there exists a number N such that for each natural number n>N and natural numbers d1,d2,…,dn and r1,r2,…,rn, where di's (1≤i≤n) are coprime, the above system of inequalities has a solution x that 1≤x≤(2+ϵ)n.
Solution
a) Without loss of generality, we may suppose that 1<d1<⋯<dn. First, suppose that d1>2. For each subset I={i1<⋯<ik}⊆{1,2,…,n}, we define dI to be equal to the product di1di2…dik. By the Chinese Remainder Theorem, we know that the modular equalities x≡ri1(moddi1),…,x≡rik(moddik)(∗) have a unique solution modulo dI. Let rI be one of its solutions (If I=∅ there is no equation and so all integers are solutions. In this case, we set rI=1). So x≡rI(moddI) is equivalent to the system (∗).
Now suppose that M is an arbitrary integer. According to the Inclusion-Exclusion Principle, the number of solutions of modular inequalities x≡r1(modd1),…,x≡rn(moddn) which are greater than M is I⊆{1,…,n}∑(−1)∣I∣∣{1≤x≤M∣x≡rI(moddI)}∣. It is easy to see that the number of solutions of each modular equality like x≡r(modd) in [1,M] is ⌊dM⌋ or ⌈dM⌉. In each case, the difference of the number of solutions and dM is at most one, so the number of solutions is greater than I⊆{1,…,n}∑(−1)∣I∣dIM−2n=M(1−d11−⋯−dn1+d1d21+…)−2n=M(1−d11)…(1−dn1)−2n.
Now, if M=3n and di≥3 for all i, this number is at least 3n(1−31)n−2n=0. And so in this case the number of solutions of inequalities is not zero. For the case d1=2, parity of x is determined by the parity of r1. Thus, we can use one of substitutions x=2y or x=2y−1. This substitution changes the other inequalities to some new ones in terms of y y≡s2(modd2),…,y≡sn(moddn) Since 3≤d2<⋯<dn, these inequalities have a solution y0≤3n−1. Hence, we can find a solution for the main inequalities (x) not greater than 2×3n−1<3n. So the proof is complete.
b) Similar to the previous part, we assume that d1<d2<⋯<dn. Therefore, for each i, we have di≥i. Furthermore, suppose that ϵ>0 has been given. We choose a real number a∈(2+ϵ2,1). Obviously, there is some N1 such that 1−N11>a. On the other hand, since 2(2+ϵ)a>1, there is N2 such that (2(2+ϵ)a)N2>2N1. Now we set N=N1+N2. We will show that for each n>N the number of solutions of the system of modular inequalities is at most (2+ϵ)n. According to part (a), we know that the number of solutions of these inequalities in [1,(2+ϵ)n] is more than (2+ϵ)n(1−d11)⋯(1−dn1)−2n. But for n>N we have (2+ϵ)n(1−d11)⋯(1−dn1)≥(2+ϵ)n(1−21)⋯(1−n+11)≥(2+ϵ)n(1−21)N1(1−N11)n−N1≥(2+ϵ)n2−N1an−N1≥(2+ϵ)n2−N1(2+ϵ2)n−N1(2(2+ϵ)a)n−N1. Note that 2+ϵ2<1, 2(2+ϵ)a>1 and n−N1>N2. Therefore, (2+ϵ)n2−N1(2+ϵ2)n−N1(2(2+ϵ)a)n−N1>(2+ϵ)n2−N1(2+ϵ2)n(2(2+ϵ)a)N2>(2+ϵ)n2−N1(2+ϵ2)n2N1=2n. And finally, we get (2+ϵ)n(1−d11)⋯(1−dn1)−2n>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.