Maths Olympiad Prep

Library / /729 of 860

Number theory Difficulty 5.5 AIME, harder Find the answer

Find all pairs (a,b)(a, b) of positive integers such that a2017+ba^{2017}+b is a multiple of aba b.

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

Solution

We want aba2017+ba b \mid a^{2017}+b. This gives that aba \mid b. Therefore, we can set b=b2017ab=b_{2017} a. Substituting this gives b2017a2a2017+b2017ab_{2017} a^{2} \mid a^{2017}+b_{2017} a, so b2017aa2016+b2017b_{2017} a \mid a^{2016}+b_{2017}. Once again, we get ab2017a \mid b_{2017}, so we can set b2017=b2016ab_{2017}=b_{2016} a. Continuing this way, if we have bi+1aai+bi+1b_{i+1} a \mid a^{i}+b_{i+1}, then abi+1a \mid b_{i+1}, so we can set bi+1=biab_{i+1}=b_{i} a and derive biaai1+bib_{i} a \mid a^{i-1}+b_{i}. Continuing down to i=1i=1, we would have b=b1a2017b=b_{1} a^{2017} so ab11+b1a b_{1} \mid 1+b_{1}. If a3a \geq 3, then ab1>1+b1a b_{1}>1+b_{1} for all b11b_{1} \geq 1, so we need either a=1a=1 or a=2a=2. If a=1a=1, then bb+1b \mid b+1, so b=1b=1. This gives the pair (1,1)(1,1). If a=2a=2, we need 2bb+220172 b \mid b+2^{2017}. Therefore, we get b22017b \mid 2^{2017}, so we can write b=2kb=2^{k} for 0k20170 \leq k \leq 2017. Then we need 2k+12k+220172^{k+1} \mid 2^{k}+2^{2017}. As k2017k \leq 2017, we need 21+22017k2 \mid 1+2^{2017-k}. This can only happen is k=2017k=2017. This gives the pair \left(2,2^{2017}\right).

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.