Maths Olympiad Prep

Library / /123 of 128

Number theory Difficulty 7.3 National Olympiad, round 2 Prove it Philippines

Problem:

Call a lattice point visible if the line segment connecting the point and the origin does not pass through another lattice point. Given a positive integer kk, denote by SkS_{k} the set of all visible lattice points (x,y)(x, y) such that x2+y2=k2x^{2}+y^{2}=k^{2}. Let DD denote the set of all positive divisors of 202120252021 \cdot 2025. Compute the sum
dDSd \sum_{d \in D}\left|S_{d}\right|
Here, a lattice point is a point (x,y)(x, y) on the plane where both xx and yy are integers, and A|A| denotes the number of elements of the set AA.

Solution

Solution:

We claim that the required sum is 2020.

Let TkT_{k} denote the set of all lattice points in the circle x2+y2=k2x^{2}+y^{2}=k^{2}. We claim that dkSd=Tk\sum_{d \mid k}\left|S_{d}\right|=\left|T_{k}\right|. Indeed, given a point (x,y)(x, y) in TkT_{k}, let g=gcd(x,y)g=\operatorname{gcd}(x, y). Then x/g,y/gx / g, y / g are necessarily coprime, and hence (x/g,y/g)(x / g, y / g) visible, and (x/g)2+(y/g)2=(k/g)2(x / g)^{2}+(y / g)^{2}=(k / g)^{2}. This implies (x/g,y/g)dkSd(x / g, y / g) \in \bigcup_{d \mid k} S_{d}. Next, note that the SdS_{d}'s are necessarily disjoint. Now if (x,y)(x', y') is a visible lattice point in SdS_{d} where dkd \mid k, then we can write k=gdk=g d so that (x,y)=(gx,gy)(x, y)=(g x', g y') is a lattice point in TkT_{k}. This establishes a bijection between dkSd\bigcup_{d \mid k} S_{d} and TkT_{k}, and since the SdS_{d}'s are disjoint, the claim follows.

From the claim, it suffices to find the number of lattice points in the circle x2+y2=(20212025)2x^{2}+y^{2}=(2021 \cdot 2025)^{2}. This is equivalent to
x2+y2=3854432472 x^{2}+y^{2}=3^{8} \cdot 5^{4} \cdot 43^{2} \cdot 47^{2}
Now it is well-known that if x2+y20(modp)x^{2}+y^{2} \equiv 0\pmod{p} where p3(mod4)p \equiv 3\pmod{4} is a prime, then xy0(modp)x \equiv y \equiv 0\pmod{p}. Thus, we must also have x,y0(mod344347)x, y \equiv 0\pmod{3^{4} \cdot 43 \cdot 47}. It then follows that the number of lattice points is the same as the number of lattice points in x2+y2=252x^{2}+y^{2}=25^{2}.

If x=0x=0 or y=0y=0, there are 44 solutions. Otherwise, assume WLOG that they are both positive. Now it is well-known that all solutions to x2+y2=z2x^{2}+y^{2}=z^{2} are in the form x=g(m2n2)x=g(m^{2}-n^{2}), y=2gmny=2 g m n, and z=g(m2+n2)z=g(m^{2}+n^{2}), where m>nm>n are coprime positive integers, and gg is a positive integer. Thus, we want g(m2+n2)=25g(m^{2}+n^{2})=25. Note that g25g \mid 25, so g=1,5,25g=1,5,25.

If g=25g=25, then m2+n2=1m^{2}+n^{2}=1, so n=0n=0, contradiction. If g=5g=5, then m2+n2=5m^{2}+n^{2}=5, which yields m=2m=2 and n=1n=1 and thus g(m2n2)=15g(m^{2}-n^{2})=15 and 2gmn=202 g m n=20, so (x,y)=(15,20),(20,15)(x, y)=(15,20),(20,15). If g=1g=1, then we get m2+n2=25m^{2}+n^{2}=25, from which we obtain m=4m=4 and n=3n=3. It then follows that (x,y)=(24,7),(7,24)(x, y)=(24,7),(7,24), and so we have 22 solutions when x,yx, y are both positive. This implies that there are 44=164 \cdot 4=16 solutions when x,yx, y are nonzero, and so there are 4+16=204+16=20 solutions in total.

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.