Maths Olympiad Prep

Library / /795 of 860

Number theory Difficulty 5.6 AIME, harder Find the answer

For positive integers aa and bb, let M(a,b)=lcm(a,b)gcd(a,b)M(a, b)=\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)}, and for each positive integer n2n \geq 2, define xn=M(1,M(2,M(3,,M(n2,M(n1,n)))))x_{n}=M(1, M(2, M(3, \ldots, M(n-2, M(n-1, n)) \ldots))) Compute the number of positive integers nn such that 2n20212 \leq n \leq 2021 and 5xn2+5xn+12=26xnxn+15 x_{n}^{2}+5 x_{n+1}^{2}=26 x_{n} x_{n+1}.

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

Solution

The desired condition is that xn=5xn+1x_{n}=5 x_{n+1} or xn+1=5xnx_{n+1}=5 x_{n}. Note that for any prime pp, we have νp(M(a,b))=νp(a)νp(b)\nu_{p}(M(a, b))=\left|\nu_{p}(a)-\nu_{p}(b)\right|. Furthermore, νp(M(a,b))νp(a)+νp(b)mod2\nu_{p}(M(a, b)) \equiv \nu_{p}(a)+\nu_{p}(b) \bmod 2. So, we have that νp(xn)νp(1)+νp(2)++νp(n)mod2\nu_{p}\left(x_{n}\right) \equiv \nu_{p}(1)+\nu_{p}(2)+\cdots+\nu_{p}(n) \bmod 2 Subtracting gives that νp(xn+1)νp(xn)νp(n+1)mod2\nu_{p}\left(x_{n+1}\right)-\nu_{p}\left(x_{n}\right) \equiv \nu_{p}(n+1) \bmod 2. In particular, for p5,νp(n+1)p \neq 5, \nu_{p}(n+1) must be even, and ν5(n+1)\nu_{5}(n+1) must be odd. So n+1n+1 must be a 5 times a perfect square. There are 20215=20\left\lfloor\sqrt{\frac{2021}{5}}\right\rfloor=20 such values of nn in the interval [2, 2021]. Now we show that it is sufficient for n+1n+1 to be 5 times a perfect square. The main claim is that if B>0B>0 and a sequence a1,a2,,aBa_{1}, a_{2}, \ldots, a_{B} of nonnegative real numbers satisfies anB+i<naia_{n} \leq B+\sum_{i<n} a_{i} for all 1nN1 \leq n \leq N, then a1a2aN1aNB\left|a_{1}-\right| a_{2}-|\cdots-| a_{N-1}-a_{N}|| \cdots|| \leq B This can be proved by a straightforward induction on NN. We then apply this claim, with B=1B=1, to the sequence ai=νp(i)a_{i}=\nu_{p}(i); it is easy to verify that this sequence satisfies the condition. This gives νp(xn)=νp(1)νp(2)νp(n1)νp(n)1\nu_{p}\left(x_{n}\right)=\left|\nu_{p}(1)-\right| \nu_{p}(2)-|\cdots-| \nu_{p}(n-1)-\nu_{p}(n)|| \cdots|| \leq 1 so νp(xn)\nu_{p}\left(x_{n}\right) must be equal to (νp(1)++νp(n))mod2\left(\nu_{p}(1)+\cdots+\nu_{p}(n)\right) \bmod 2. Now suppose n+1=5k2n+1=5 k^{2} for some kk; then νp(n+1)0mod2\nu_{p}(n+1) \equiv 0 \bmod 2 for p5p \neq 5 and ν5(n+1)1mod2\nu_{5}(n+1) \equiv 1 \bmod 2. Therefore νp(xn+1)=νp(xn)\nu_{p}\left(x_{n+1}\right)=\nu_{p}\left(x_{n}\right) for p5p \neq 5, and ν5(xn+1)=(ν5(xn)+1)mod2\nu_{5}\left(x_{n+1}\right)=\left(\nu_{5}\left(x_{n}\right)+1\right) \bmod 2, and this implies xn+1/xn{1/5,5}x_{n+1} / x_{n} \in\{1 / 5,5\} as we wanted.

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.