Let $n\geq 1$ be a positive integer. We say that an integer $k$ is a fan of $n$ if $0\leq k\leq n-1$ and there exist integers $x,y,z\in\mathbb{Z}$ such that \begin{align*} x^2+y^2+z^2 &\equiv 0 \pmod n;\\ xyz &\equiv k \pmod n. \end{align*}Let $f(n)$ be the number of fans of $n$. Determine $f(2020)$.
Problem
Source: Baltic Way 2020, Problem 18
Tags: number theory, number theory proposed, AZE CMO TST, AZE EGMO TST
14.11.2020 18:59
My solution during the contest: The prime factorisation of $2020$ is $2020=2^2\cdot5\cdot101$. It's easy to check that $x^2+y^2+z^2\equiv 0\pmod{2^2\cdot5\cdot101}$ implies $xyz\equiv 0\pmod{2^2\cdot5}$. The are at most $101$ $\emph{fans}$ of $2020$. Take the triples $(x,y,z)=(10t,60t,80t)$ for $0\leq t\leq100$. We have \[ x^2+y^2+z^2=100t^2(1^2+6^2+8^2)=2020\cdot5t^2\equiv0\pmod{2020} \]and \[ xyz=10^3\cdot6\cdot8\cdot t^3 \]If $10^3\cdot6\cdot8\cdot t^3\equiv10^3\cdot6\cdot8\cdot t'^3\pmod{2020}$, we have \begin{align*} 10^3\cdot6\cdot8\cdot t^3\equiv10^3\cdot6\cdot8\cdot t'^3\pmod{101}\\ t^3\equiv t'^3\pmod{101}\\ t\equiv t^{201}=(t^3)^{67}\equiv(t'^3)^{67}=t'^{201}\equiv t'\pmod{101} \end{align*}For each $0\leq t\leq100$ the triple $(x,y,z)=(10t,60t,80t)$ gives us a different $\emph{fan}$ of $2020$. Thus $f(2020)=101$.
15.11.2020 00:58
If you don't see the tricky factorization above (like myself), you can do the following long but more technical round for $f(101)$. We claim that for every $k\in\mathbb{Z}_{101}$, there is a triple $(x,y,z)$ such that $101\mid x^2+y^2+z^2$ and $xyz\equiv k\pmod{101}$. For $k=0$, this is immediate by taking $x=y=z=0$, hence suppose $k\ne 0$ in the remainder. Our goal is to show, for every $1\le k\le 100$, there exists a $1\le a\le 100$ such that for some $y,z$ the following holds: \[ y^2+z^2\equiv -a^2\pmod{101}\quad\text{and}\quad yz\equiv \frac{k}{a}\pmod{101}. \]Now, since $101\equiv 1\pmod{4}$, $-1$ is a quadratic residue, modulo $101$. Let $u\in\mathbb{Z}_{101}$ be such that $u^2\equiv -1\pmod{101}$, and let $y\equiv t_y\cdot u\cdot a\pmod{101}$ and $z\equiv t_z\cdot u\cdot a\pmod{101}$. Note that if such a $t_y,t_z$ can be found, one can also find $y,z$ and conclude the case. Now, in terms of these objects, it suffices to show there exists $a$ such that the following holds for some $t_y,t_z$: \[ t_y^2+t_z^2\equiv 1\pmod{101}\quad\text{and}\quad t_yt_z\equiv -\frac{k}{a^3}\pmod{101}. \]Since $101\equiv 2\pmod{3}$, it follows $a\mapsto -\frac{1}{a^3}\pmod{101}$ is injective, except $a\ne 0$. Hence, it suffices to show, there exists an $a'$ for which for some $t_y,t_z$ it holds: \[ t_y^2+t_z^2\equiv 1\pmod{101}\quad\text{and}\quad t_yt_z\equiv a'k\pmod{101}. \]Observing $t_y^2+t_z^2+2t_yt_z=\left(t_y+t_z\right)^2$ and $t_y^2+t_z^2-2t_yt_z=\left(t_y-t_z\right)^2$, it suffices to show for some $a'$, the objects \[ 1+2a'k \quad\text{and}\quad 1-2a'k \]are both quadratic residues, modulo $p$. Now, we observe that both $6$ and $-4$ are quadratic residues, modulo $101$. Hence, setting $2a'k\equiv 5\pmod{101}$ works. Namely, for any {\bf fixed} $k$, taking \[ a'\equiv \frac{5}{2k}\pmod{101} \]works. Hence, the claim is complete, and that, $f(101)=101$. Remark. I am fairly confident that a reverse engineering of what I did above gives (something very similar to) the slick solution above.
10.10.2024 22:11
İt's like $x^2=(2^2)*5*a$ $y^2=(2^2)*5*b$ $z^2=(2^2)*5*c$ And $a+b+c=101$ also they're squares of some integers. We can easily have the answer with these.