Maths Olympiad Prep

Library / /52 of 155

Number theory Difficulty 5.7 AIME, harder Prove it Saudi Arabia

Let nn be a given positive integer. Prove that there are infinitely many pairs of positive integers (a,b)(a, b) with a,b>na, b > n such that
i=12015(a+i)b(b+2016);i=12015(a+i)b;i=12015(a+i)(b+2016). \prod_{i=1}^{2015}(a+i) \mid b(b+2016) ; \quad \prod_{i=1}^{2015}(a+i) \nmid b ; \quad \prod_{i=1}^{2015}(a+i) \nmid(b+2016) .

Solution

The given problem can be generalized as follows:
Given three positive integers k,m,nk, m, n. Let k1,k2,,kmk_{1}, k_{2}, \ldots, k_{m} be any positive integer. Prove that there are infinitely many pair of positive integers (a,b)(a, b) such that
k=1m(a+ki)b(b+k) but k=1m(a+ki)b and k=1m(a+ki)b+k. \prod_{k=1}^{m}\left(a+k_{i}\right) \mid b(b+k) \text{ but } \prod_{k=1}^{m}\left(a+k_{i}\right) \nmid b \text{ and } \prod_{k=1}^{m}\left(a+k_{i}\right) \nmid b+k .
Proof. Let k<p1<p2<<pmk < p_{1} < p_{2} < \ldots < p_{m} be any mm distinct primes and denote
M=k=1m(a+ki). M = \prod_{k=1}^{m}\left(a+k_{i}\right) .
By Chinese remainder theorem, there are infinitely many positive integers a>na > n such that
aki(modpi),i=1,,m. a \equiv -k_{i} \pmod{p_{i}}, \forall i = 1, \ldots, m .
Hence M0(modp1p2pm)M \equiv 0 \pmod{p_{1} p_{2} \ldots p_{m}}.
Then we write
M=p1α1p2α2pmαmq1β1q2β2qsβs M = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{m}^{\alpha_{m}} q_{1}^{\beta_{1}} q_{2}^{\beta_{2}} \ldots q_{s}^{\beta_{s}}
with αi1,i=1,,m;βj1,j=1,,s\alpha_{i} \geq 1, i = 1, \ldots, m ; \beta_{j} \geq 1, j = 1, \ldots, s and q1,q2,,qsq_{1}, q_{2}, \ldots, q_{s} are ss prime divisors of MM which are different from p1,p2,,pmp_{1}, p_{2}, \ldots, p_{m}.
By Chinese remainder theorem, there exist infinitely many positive integers b>mb > m such that
{b0(modMpmαm)bk(modpmαm) \begin{cases} b \equiv 0 \pmod{\frac{M}{p_{m}^{\alpha_{m}}}} \\ b \equiv -k \pmod{p_{m}^{\alpha_{m}}} \end{cases}
This implies that
Mb,Mb+k and Mb(b+k). M \nmid b, \quad M \nmid b+k \text{ and } M \mid b(b+k) .
\square

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.