Maths Olympiad Prep

Library / AIME II /3 of 6

AIME II

Number theory Difficulty 4.7 AIME Prove it United States

Find the sum of all positive integers nn such that n+2n + 2 divides the product 3(n+3)(n2+9)3(n + 3)(n^2 + 9).

Solution

Solution:
Note that n≡−2(mod(n+2))n \equiv -2 \pmod{(n+2)} and thus 3(n+3)(n2+9)≡3⋅1⋅13=39(mod(n+2))3(n+3)(n^2+9) \equiv 3 \cdot 1 \cdot 13 = 39 \pmod{(n+2)}. Therefore nn is a positive solution if and only if n+2n+2 is a divisor of 3939 that is at least 33. Those divisors are 33, 1313, and 3939, and the corresponding values of nn are 11, 1111, and 3737, respectively. The requested sum is 1+11+37=491 + 11 + 37 = 49.

OR
Note that gcd⁡(n+2,n+3)=1\gcd(n+2, n+3) = 1, so n+2n+2 must divide the product 3(n2+9)3(n^2+9). This product can be rewritten as
3(n2+9)=3(n2−4+13)=3(n+2)(n−2)+39. 3(n^2 + 9) = 3(n^2 - 4 + 13) = 3(n + 2)(n - 2) + 39.
Therefore n+2n+2 must be a divisor of 3939 that is at least 33, as in the first solution.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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