Maths Olympiad Prep

Library / /47 of 136

Number theory Difficulty 7.7 National Olympiad, round 2 Prove it Hong Kong

Given that aa and bb are natural numbers, when a2+b2a^2 + b^2 is divided by a+ba+b, the quotient is QQ and the remainder is RR, where R<a+bR < a+b. Find all possible pairs of numbers aa and bb such that Q2+R=2010Q^2 + R = 2010.

Solution

We are given that
a2+b2=Q(a+b)+R. a^2 + b^2 = Q(a + b) + R.
Since R<a+bR < a + b, we have
(a+b)22(a2+b2)<2(Q+1)(a+b), (a+b)^2 \le 2(a^2+b^2) < 2(Q+1)(a+b),
which implies a+b<2(Q+1)a + b < 2(Q + 1), and hence R<2(Q+1)R < 2(Q + 1). Thus, we have
Q2Q2+RQ2+2Q+1=(Q+1)2. Q^2 \le Q^2 + R \le Q^2 + 2Q + 1 = (Q + 1)^2.
Since Q2+R=2010Q^2 + R = 2010, we must have Q=2010=44Q = \lfloor\sqrt{2010}\rfloor = 44, and so R=2010442=74R = 2010 - 44^2 = 74.
It remains to solve the equation
a2+b2=44(a+b)+74. a^2 + b^2 = 44(a + b) + 74.
This can be rewritten as
(a22)2+(b22)2=1042. (a - 22)^2 + (b - 22)^2 = 1042.

Let x=(a22)2x = (a - 22)^2 and y=(b22)2y = (b - 22)^2. WLOG assume xyx \ge y. Then we have 521x1042521 \le x \le 1042. So it suffices to check 232x32223^2 \le x \le 32^2. Also, xx and yy must be odd since x2+y22(mod4)x^2 + y^2 \equiv 2 \pmod 4. We compute the values as follows.

x529625729841961
y51341731320181

Among these values, only y=81y = 81 is a perfect square. Therefore, we can only have (a22,b22)=(±31,±9)(a - 22, b - 22) = (\pm 31, \pm 9). Since a,bZ+a, b \in \mathbb{Z}^+, this implies (a,b)=(53,13),(53,31)(a, b) = (53, 13), (53, 31). However, we need a+b>R=74a + b > R = 74. Therefore, only (a,b)=(53,31)(a, b) = (53, 31) is possible. We check that when (a,b)=(53,31)(a, b) = (53, 31), we have
a2+b2=3770=44(53+31)+74. a^2 + b^2 = 3770 = 44(53 + 31) + 74.
Therefore, this is the only solution up to permutation.

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.