Maths Olympiad Prep

Library / /3 of 7

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 n2(mod(n+2))n \equiv -2 \pmod{(n+2)} and thus 3(n+3)(n2+9)3113=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(n24+13)=3(n+2)(n2)+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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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