Maths Olympiad Prep

Library / /271 of 348

Number theory Difficulty 5.1 AIME, harder Find the answer

Compute the number of ordered pairs of positive integers (a,b)(a, b) satisfying the equation gcd(a,b)a+b2=10000\operatorname{gcd}(a, b) \cdot a+b^{2}=10000

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let gcd(a,b)=d,a=da,b=db\operatorname{gcd}(a, b)=d, a=d a^{\prime}, b=d b^{\prime}. Then, d2(a+b2)=1002d^{2}\left(a^{\prime}+b^{\prime 2}\right)=100^{2}. Consider each divisor dd of 100. Then, we need to find the number of solutions in coprime integers to a+b2=1002d2a^{\prime}+b^{\prime 2}=\frac{100^{2}}{d^{2}}. Note that every b<100/db^{\prime}<100 / d coprime to 1002d2\frac{100^{2}}{d^{2}} satisfies this equation, which is equivalent to being coprime to 100d\frac{100}{d}, so then there are φ(100d)\varphi\left(\frac{100}{d}\right) choices for each dd, except for d=100d=100, which would count the solution (0,100)(0,100). Then we just need dnφ(100d)1=1001=99\sum_{d \mid n} \varphi\left(\frac{100}{d}\right)-1=100-1=99.

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.