Maths Olympiad Prep

Library / /471 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Let a1,a2,a_{1}, a_{2}, \ldots be an infinite sequence of integers such that aia_{i} divides ai+1a_{i+1} for all i1i \geq 1, and let bib_{i} be the remainder when aia_{i} is divided by 210. What is the maximal number of distinct terms in the sequence b1,b2,b_{1}, b_{2}, \ldots?

A number or a short expression. Spacing and $ signs are ignored.

Solution

It is clear that the sequence {ai}\{a_{i}\} will be a concatenation of sequences of the form {vi}i=1N0,{wip1}i=1N1,{xip1p2}i=1N2,{yip1p2p3}i=1N3\{v_{i}\}_{i=1}^{N_{0}},\{w_{i} \cdot p_{1}\}_{i=1}^{N_{1}},\{x_{i} \cdot p_{1} p_{2}\}_{i=1}^{N_{2}},\{y_{i} \cdot p_{1} p_{2} p_{3}\}_{i=1}^{N_{3}}, and {zip1p2p3p4}i=1N4\{z_{i} \cdot p_{1} p_{2} p_{3} p_{4}\}_{i=1}^{N_{4}}, for some permutation (p1,p2,p3,p4)(p_{1}, p_{2}, p_{3}, p_{4}) of (2,3,5,7)(2,3,5,7) and some sequences of integers {vi}{wi}{xi}{yi}{zi}\{v_{i}\} \cdot\{w_{i}\} \cdot\{x_{i}\} \cdot\{y_{i}\} \cdot\{z_{i}\}, each coprime with 210. In {vi}i=1N0\{v_{i}\}_{i=1}^{N_{0}}, there are a maximum of ϕ(210)\phi(210) distinct terms mod210\bmod 210. In {wip1}i=1N1\{w_{i} \cdot p_{1}\}_{i=1}^{N_{1}}, there are a maximum of ϕ(210p1)\phi\left(\frac{210}{p_{1}}\right) distinct terms mod 210. In {xip1p2}i=1N2\{x_{i} \cdot p_{1} p_{2}\}_{i=1}^{N_{2}}, there are a maximum of ϕ(210p1p2)\phi\left(\frac{210}{p_{1} p_{2}}\right) distinct terms mod210\bmod 210. In {yip1p2p3}i=1N3\{y_{i} \cdot p_{1} p_{2} p_{3}\}_{i=1}^{N_{3}}, there are a maximum of ϕ(210p1p2p3)\phi\left(\frac{210}{p_{1} p_{2} p_{3}}\right) distinct terms mod210\bmod 210. In {zip1p2p3p4}i=1N4\{z_{i} \cdot p_{1} p_{2} p_{3} p_{4}\}_{i=1}^{N_{4}}, there can only be one distinct term mod210\bmod 210. Therefore we wish to maximize ϕ(210)+ϕ(210p1)+ϕ(210p1p2)+ϕ(210p1p2p3)+1\phi(210)+\phi\left(\frac{210}{p_{1}}\right)+\phi\left(\frac{210}{p_{1} p_{2}}\right)+\phi\left(\frac{210}{p_{1} p_{2} p_{3}}\right)+1 over all permutations (p1,p2,p3,p4)(p_{1}, p_{2}, p_{3}, p_{4}) of (2,3,5,7)(2,3,5,7). It's easy to see that the maximum occurs when we take p1=2,p2=3,p3=5,p4=7p_{1}=2, p_{2}=3, p_{3}=5, p_{4}=7 for an answer of ϕ(210)+ϕ(105)+ϕ(35)+ϕ(7)+1=127\phi(210)+\phi(105)+\phi(35)+\phi(7)+1=127. This upper bound is clearly attainable by having the viv_{i}'s cycle through the ϕ(210)\phi(210) integers less than 210 coprime to 210, the wiw_{i}'s cycle through the ϕ(210p1)\phi\left(\frac{210}{p_{1}}\right) integers less than 210p1\frac{210}{p_{1}} coprime to 210p1\frac{210}{p_{1}}, etc.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.