Maths Olympiad Prep

Library / /14 of 39

Number theory Difficulty 5.1 AIME, harder Prove it Italy

How many positive integers nn are there for which (2022+12)n+(25+12)n\left(2022+\frac{1}{2}\right)^{n}+\left(25+\frac{1}{2}\right)^{n} is an integer?

Solution

The answer is 6. We will show that the desired integers nn are precisely the odd positive integers less than or equal to 11.

We observe that 2022+12=404522022+\frac{1}{2}=\frac{4045}{2} and 25+12=51225+\frac{1}{2}=\frac{51}{2}, so we are looking for the positive integers nn for which the fraction 4045n+51n2n\frac{4045^{n}+51^{n}}{2^{n}} is an integer.

We first observe that if n=2kn=2k is even this never happens: indeed the numerator is even, but not divisible by 4, since 40452k4045^{2k} and 512k51^{2k} both leave remainder 1 upon division by 4 (to prove this fact it suffices to observe that 40452k1=(4045k+1)(4045k1)4045^{2k}-1=\left(4045^{k}+1\right)\left(4045^{k}-1\right) is a product of two even numbers, and is therefore divisible by 4; similarly for 512k151^{2k}-1), and so their sum leaves remainder 2 upon division by 4.

When n=2k+1n=2k+1 is odd, instead, we can use the well-known factorization for a sum of two odd powers with the same exponent to obtain
40452k+1+512k+1=(4045+51)(40452k40452k151+4045512k1+512k) 4045^{2k+1}+51^{2k+1}=(4045+51) \cdot\left(4045^{2k}-4045^{2k-1} \cdot 51+\cdots-4045 \cdot 51^{2k-1}+51^{2k}\right)
The number in the second parenthesis is the algebraic sum of 2k+12k+1 odd terms, and is therefore odd. The product just written is therefore divisible by 22k+12^{2k+1} if and only if 4045+51=4096=2124045+51=4096=2^{12} is. This happens if and only if 2k+1122k+1 \leq 12, that is, for k=0,1,,5k=0,1, \ldots, 5, values which give the 6 desired solutions.

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 translated into English from it; metadata (topic, difficulty) added by this project.