Maths Olympiad Prep

Library / /315 of 348

Number theory Difficulty 5.2 AIME, harder Find the answer

Find the number of pairs of integers (a,b)(a, b) with 1a<b571 \leq a<b \leq 57 such that a2a^{2} has a smaller remainder than b2b^{2} when divided by 57.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

There are no such pairs when b=57b=57, so we may only consider pairs with 1a<b561 \leq a<b \leq 56. The key idea is that unless a2mod57=b2mod57,(a,b)a^{2} \bmod 57=b^{2} \bmod 57,(a, b) can be paired with (57b,57a)(57-b, 57-a) and exactly one of them satisfies a2mod57<b2mod57a^{2} \bmod 57<b^{2} \bmod 57. Hence if XX is the number of pairs (a,b)(a, b) with 1a<b561 \leq a<b \leq 56 and a2b2(mod57)a^{2} \equiv b^{2}(\bmod 57), then the answer is 12((562)X)\frac{1}{2}\left(\binom{56}{2}-X\right). To count XX, let's first count the number of pairs (a,b)(a, b) with 1a,b571 \leq a, b \leq 57 and a2b2(mod57)a^{2} \equiv b^{2}(\bmod 57). By the Chinese Remainder Theorem, the condition is equivalent to (ab)(a+b)0(mod3)(a-b)(a+b) \equiv 0(\bmod 3) and (ab)(a+b)0(mod19)(a-b)(a+b) \equiv 0(\bmod 19). There are 231=52 \cdot 3-1=5 pairs of residues modulo 3 where (ab)(a+b)0(a-b)(a+b) \equiv 0 (mod3)(\bmod 3), namely (0,0),(1,1),(2,2),(1,2),(2,1)(0,0),(1,1),(2,2),(1,2),(2,1). Similarly, there are 2191=372 \cdot 19-1=37 pairs of residues modulo 19 where (ab)(a+b)0(mod19)(a-b)(a+b) \equiv 0(\bmod 19). By the Chinese Remainder Theorem, each choice of residues modulo 3 for aa and bb and residues modulo 19 for aa and bb corresponds to unique residues modulo 57 for aa and bb. It follows that there are 537=1855 \cdot 37=185 such pairs. To get the value of XX, we need to subtract the 57 pairs where a=ba=b and divide by 2 for the pairs with a>ba>b, for a value of X=12(18557)=64X=\frac{1}{2}(185-57)=64. Therefore the final answer is 12((562)64)=738\frac{1}{2}\left(\binom{56}{2}-64\right)=738.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.