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 $k$, denote by $S_k$ the set of all visible lattice points $(x, y)$ such that $x^2 + y^2 = k^2$. Let $D$ denote the set of all positive divisors of $2021 \cdot 2025$. Compute the sum \[ \sum_{d \in D} |S_d| \]Here, a lattice point is a point $(x, y)$ on the plane where both $x$ and $y$ are integers, and $|A|$ denotes the number of elements of the set $A$.
Problem
Source: Philippine MO 2022/3
Tags: algebra, number theory
18.03.2022 09:02
We can note that the visible condition rewrites to $(x,y)$ is visible if and only if $\gcd(x,y)=1$. Thus, we're asked to find the number of primitive solutions to $x^2+y^2=k^2$ as $k$ ranges over the divisors of $2021\cdot 2025$. We first assume $x=0$ (where the case $y=0$ is identical, and both are not possible at the same time). In this case, we get 2 values for each value of $k$ (which are $(\pm k,0)$), which leads to 4 additional elements of $S_k$. Now, we assume $x$ and $y$ are positive integers. In particular, we want to find, by the Pythagorean characterization of such triples, the number of solutions to \[m^2+n^2=k\qquad \gcd(m,n)=1\]where $m>n$ in the positive integers. We pull out a few useful lemmas from the bag: Lemma. $x^2+y^2=p$ has one solution for primes congruent to $1\pmod 4$ (up to multiplication by a unit and swapping). Primes congruent to $3\pmod 4$ have no such solutions. Proof. The classic Minkowski Proof is an overkill, but it works. $\square$ As the property of being a sum of squares is multiplicative (easily seen through the vectorspace $\mathbb R^2$), we only concern ourselves with multiples of $5$ or $25$. We know $5=2^2+1^2$ and $25=7^2+24^2$, and one can check that these are the only solutions. Thus, we get there are $20$ divisors of $2021\cdot 81$, implying this contributes $40$ to our count. We need to, however, include for all quadrants, which makes the count $160$. Thus the answer is $160+4\cdot 60=400$.
18.03.2022 15:08
InternetPerson10 wrote: 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 $k$, denote by $S_k$ the set of all visible lattice points $(x, y)$ such that $x^2 + y^2 = k^2$. Let $D$ denote the set of all positive divisors of $2021 \cdot 2025$. Compute the sum \[ \sum_{d \in D} |S_d| \]Here, a lattice point is a point $(x, y)$ on the plane where both $x$ and $y$ are integers, and $|A|$ denotes the number of elements of the set $A$. Easy to see that $(x,y)=1$. In the $x^2+y^2=k^2$ and there's a prime in the form $p=3(mod4)$ which devise $k$ then $p|x,y$ contradiction. This means that $k=5,25$
19.03.2022 10:01
If $(x, y)$ is a visible lattice point, then $x$ and $y$ are integers such that $gcd(x, y) = 1$. If $gcd(x, y) = 1$, then $gcd(x, k^2) = gcd(y, k^2) = 1$. So there exists an integer $m$ such that $y \equiv mx \pmod{k^2}$. Then $m^2 \equiv -1 \pmod{k^2} \implies m^2 \equiv -1 \pmod{k}$. If a prime number $p \equiv 3 \pmod{4}$ divides $k$, then $m^2 \equiv -1 \pmod{p}$. But $-1$ is not a quadratic residue modulo $p$, contradiction. Thus, if $k$ is odd, then $k$ must only contain prime divisors that are $1 \pmod {4}$. Note that $2021 \cdot 2025 = 3^4 \cdot 5^2 \cdot 43 \cdot 47$. The only prime factor that is $1 \pmod{4}$ is $5$. Thus, $\sum_{d \in D} |S_d| = |S_1| + |S_5| + |S_{25}|$. It's easy to check that the only solutions of $x^2 + y^2 = 1$ are $(1, 0), (-1, 0), (0, -1), (0, 1)$. Since $gcd(0, 1) = 1$, we have $|S_1| = 4$. For $k > 1$, $gcd(0, k) = k > 1$, so $x, y \ne 0, k$. It's easy to check that the only solutions of $x^2 + y^2 = 25$ are $(4, 3), (-4, 3), (4, -3), (-4, -3), (3, 4), (-3, 4), (3, -4), (-3, -4)$. Since $gcd(3, 4) = 1$, we have $|S_5| = 8$. It's easy to check that the only solutions of $x^2 + y^2 = 625$ are $(24, 7), (-24, 7), (24, -7), (-24, -7), (7, 24), (-7, 24), (7, -24), (-7, -24)$. Since $gcd(7, 24) = 1$, we have $|S_{25}| = 8$. Therefore, $\sum_{d \in D} |S_d| = |S_1| + |S_5| + |S_{25}| = 4 + 8 + 8 = \boxed{20}$.