Maths Olympiad Prep

Library / /21 of 34

, 2014

Number theory Difficulty 6.0 AIME, harder Prove it Austria

For any integer nn, let M(n)={n,n+1,n+2,n+3,n+4}M(n) = \{n, n+1, n+2, n+3, n+4\}. Let S(n)S(n) denote the sum of the squares of all elements of M(n)M(n) and let P(n)P(n) denote the product of these squares. For which integers nn is S(n)S(n) a divisor of P(n)P(n)?

Solution

We substitute k=n+2k = n + 2 such that
S(n)=(k2)2+(k1)2+k2+(k+1)2+(k+2)2=5k2+10=5(k2+2).P(n)=(k2)2(k1)2k2(k+1)2(k+2)2=k2(k21)2(k24)2. \begin{aligned} S(n) &= (k-2)^2 + (k-1)^2 + k^2 + (k+1)^2 + (k+2)^2 = 5k^2 + 10 = 5(k^2 + 2). \\ P(n) &= (k-2)^2(k-1)^2 k^2 (k+1)^2 (k+2)^2 = k^2(k^2-1)^2(k^2-4)^2. \end{aligned}
As P(n)P(n) is the square of the product of 5 consecutive integers, it is divisible by 55. On the other hand, k2+2k^2 + 2 is not divisible by 55, because 2-2 is a quadratic non-residue modulo 55. Therefore, S(n)S(n) divides P(n)P(n) if and only if k2+2k^2 + 2 divides P(n)P(n). As k22(modk2+2)k^2 \equiv -2 \pmod{k^2+2},
P(n)2(21)2(24)22334(modk2+2). P(n) \equiv -2(-2-1)^2(-2-4)^2 \equiv -2^3 \cdot 3^4 \pmod{k^2+2}.
Therefore, the assertion is equivalent to k2+22334k^2 + 2 \mid 2^3 \cdot 3^4. However, k2+2k^2 + 2 is congruent to 22 or 33 modulo 44. In particular, 44 does not divide k2+2k^2 + 2. We conclude that the assertion is equivalent to k2+2234k^2 + 2 \mid 2 \cdot 3^4.
We now consider all positive divisors of 2342 \cdot 3^4:
k2+21236918275481162k21014716255279160k0±1±2±4±5 \begin{array}{c|cccccccccc} k^2+2 & 1 & 2 & 3 & 6 & 9 & 18 & 27 & 54 & 81 & 162 \\ k^2 & -1 & 0 & 1 & 4 & 7 & 16 & 25 & 52 & 79 & 160 \\ k & 0 & \pm 1 & \pm 2 & \pm 4 & \pm 5 & & & & & \end{array}
We conclude that n=k2{7,6,4,3,2,1,0,2,3}n = k - 2 \in \{-7, -6, -4, -3, -2, -1, 0, 2, 3\} are the only solutions. \square

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 and solution reproduced as published; topic and difficulty added by this site.