Maths Olympiad Prep

Track / Stage 5 / 307 of 400 #1547 of 2604

Problem 1547

AIME late
Number theory Difficulty 5.7 Prove it Saudi Arabian Mathematical Competitions · 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) .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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
a≡−ki(modpi),∀i=1,…,m. a \equiv -k_{i} \pmod{p_{i}}, \forall i = 1, \ldots, m .
Hence M≡0(modp1p2…pm)M \equiv 0 \pmod{p_{1} p_{2} \ldots p_{m}}.
Then we write
M=p1α1p2α2…pmαmq1β1q2β2…qsβ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 αi≥1,i=1,…,m;βj≥1,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
{b≡0(modMpmαm)b≡−k(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
M∤b,M∤b+k and M∣b(b+k). M \nmid b, \quad M \nmid b+k \text{ and } M \mid b(b+k) .
□\square

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.