Maths Olympiad Prep

Library / /12 of 35

Number theory Difficulty 5.0 AIME, harder Prove it Slovenia

Let aa, bb and cc be positive integers. Prove that a2+b2+c2a^2 + b^2 + c^2 is divisible by 44 if and only if aa, bb and cc are even.

Solution

First, let aa, bb and cc be even: a=2a1a = 2a_1, b=2b1b = 2b_1, c=2c1c = 2c_1. Then the number
a2+b2+c2=4(a12+b12+c12) a^2 + b^2 + c^2 = 4(a_1^2 + b_1^2 + c_1^2)
is divisible by 44.

Now, let us prove the converse. Assume that a2+b2+c2a^2 + b^2 + c^2 is divisible by 44. If exactly one of the numbers aa, bb and cc were odd or if all three were odd, then the sum a2+b2+c2a^2 + b^2 + c^2 would be odd. This is not the case.

Finally, assume that exactly two of the numbers aa, bb and cc are odd. We may assume that aa and bb are odd and cc is even. Let a=2a11a = 2a_1 - 1, b=2b11b = 2b_1 - 1 and c=2c1c = 2c_1 for some positive integers a1a_1, b1b_1 and c1c_1. In this case the number
a2+b2+c2=(2a11)2+(2b11)2+(2c1)2=4(a12a1+b12b1+c12)2 a^2 + b^2 + c^2 = (2a_1 - 1)^2 + (2b_1 - 1)^2 + (2c_1)^2 = 4(a_1^2 - a_1 + b_1^2 - b_1 + c_1^2) - 2
is not divisible by 44. This contradicts the assumption. The only remaining possibility is that all three numbers are even.

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.