International Mathematical Olympiad

Denote by $\mathbb{A}$ the set of all pairs of coprime positive integers. Notice that for every $(a,b)\in \mathbb{A}$ there exists a pair $(u,v)\in {\mathbb{Z}}^2$ with $ua+vb=1$. Moreover, if $(u_0,v_0)$ is one such pair, then all such pairs are of the form $(u,v)=\left(u_0+kb,v_0-ka\right)$, where $k\in \mathbb{Z}$. So there exists a unique such pair $(u,v)$ with $-b/2<u⩽b/2$; we denote this pair by $(u,v)=g(a,b)$.

Lemma. Let $(a,b)\in \mathbb{A}$ and $(u,v)=g(a,b)$. Then $f(a,b)=1⟺u>0$.

Proof. We induct on $a+b$. The base case is $a+b=2$. In this case, we have that $a=b=1$, $g(a,b)=g(1,1)=(0,1)$ and $f(1,1)=0$, so the claim holds.

Assume now that $a+b>2$, and so $a\ne b$, since $a$ and $b$ are coprime. Two cases are possible.

Case 1: $a>b$. Notice that $g(a-b,b)=(u,v+u)$, since $u(a-b)+(v+u)b=1$ and $u\in (-b/2,b/2]$. Thus $f(a,b)=1⟺f(a-b,b)=1⟺u>0$ by the induction hypothesis.

Case 2: $a<b$. (Then, clearly, $b⩾2$.) Now we estimate $v$. Since $vb=1-ua$, we have $$1+\frac{ab}{2}>vb⩾1-\frac{ab}{2},\text{ so }\frac{1+a}{2}⩾\frac{1}{b}+\frac{a}{2}>v⩾\frac{1}{b}-\frac{a}{2}>-\frac{a}{2}.$$ Thus $1+a>2v>-a$, so $a⩾2v>-a$, hence $a/2⩾v>-a/2$, and thus $g(b,a)=(v,u)$.

Observe that $f(a,b)=1⟺f(b,a)=0⟺f(b-a,a)=0$. We know from Case 1 that $g(b-a,a)=(v,u+v)$. We have $f(b-a,a)=0⟺v⩽0$ by the inductive hypothesis. Then, since $b>a⩾1$ and $ua+vb=1$, we have $v⩽0⟺u>0$, and we are done.

The Lemma proves that, for all $(a,b)\in \mathbb{A}$, $f(a,b)=1$ if and only if the inverse of $a$ modulo $b$, taken in $\{1,2,\dots ,b-1\}$, is at most $b/2$. Then, for any odd prime $p$ and integer $n$ such that $n\not\equiv 0(\mathrm{mod}p)$, $f\left(n^2,p\right)=1$ iff the inverse of $n^2\mathrm{mod}p$ is less than $p/2$. Since $\left\{n^2\mathrm{mod}p:1⩽n⩽p-1\right\}=\left\{n^{-2}\mathrm{mod}p:1⩽n⩽p-1\right\}$, including multiplicities (two for each quadratic residue in each set), we conclude that the desired sum is twice the number of quadratic residues that are less than $p/2$, i.e., $$\sum _{n=1}^{p-1}f\left(n^2,p\right)=2|\left\{k:1⩽k⩽\frac{p-1}{2}\text{ and }{k}^2\mathrm{mod}p<\frac{p}{2}\right\}|.$$ Since the number of perfect squares in the interval $[1,p/2)$ is $\lfloor \sqrt{p/2}\rfloor >\sqrt{p/2}-1$, we conclude that $$\sum _{n=1}^{p-1}f\left(n^2,p\right)>2\left(\sqrt{\frac{p}{2}}-1\right)=\sqrt{2p}-2.$$

---

Alternative solution.

We provide a different proof for the Lemma. For this purpose, we use continued fractions to find $g(a,b)=(u,v)$ explicitly.

The function $f$ is completely determined on $\mathbb{A}$ by the following

Claim. Represent $a/b$ as a continued fraction; that is, let $a_0$ be an integer and $a_1,\dots ,a_k$ be positive integers such that $a_k⩾2$ and $$\frac{a}{b}=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{\cdots +\frac{1}{a_k}}}}=\left[a_0;a_1,a_2,\dots ,a_k\right].$$ Then $f(a,b)=0⟺k$ is even.

Proof. We induct on $b$. If $b=1$, then $a/b=[a]$ and $k=0$. Then, for $a⩾1$, an easy induction shows that $f(a,1)=f(1,1)=0$.

Now consider the case $b>1$. Perform the Euclidean division $a=qb+r$, with $0⩽r<b$. We have $r\ne 0$ because $\gcd (a,b)=1$. Hence $$f(a,b)=f(r,b)=1-f(b,r),\frac{a}{b}=\left[q;a_1,\dots ,a_k\right],\text{ and }\frac{b}{r}=\left[a_1;a_2,\dots ,a_k\right].$$ Then the number of terms in the continued fraction representations of $a/b$ and $b/r$ differ by one. Since $r<b$, the inductive hypothesis yields $$f(b,r)=0⟺k-1\text{ is even, }$$ and thus $$f(a,b)=0⟺f(b,r)=1⟺k-1\text{ is odd }⟺k\text{ is even. }$$ $\square$

Now we use the following well-known properties of continued fractions to prove the Lemma: Let $p_i$ and $q_i$ be coprime positive integers with $\left[a_0;a_1,a_2,\dots ,a_i\right]=p_i/q_i$, with the notation borrowed from the Claim. In particular, $a/b=\left[a_0;a_1,a_2,\dots ,a_k\right]=p_k/q_k$. Assume that $k>0$ and define $q_{-1}=0$ if necessary. Then - $q_k=a_k{q}_{k-1}+q_{k-2}$, \quad and - $a{q}_{k-1}-b{p}_{k-1}=p_k{q}_{k-1}-q_k{p}_{k-1}=(-1{)}^{k-1}$.

Assume that $k>0$. Then $a_k⩾2$, and $$b=q_k=a_k{q}_{k-1}+q_{k-2}⩾a_k{q}_{k-1}⩾2q_{k-1}⟹q_{k-1}⩽\frac{b}{2},$$ with strict inequality for $k>1$, and $$(-1{)}^{k-1}{q}_{k-1}a+(-1{)}^k{p}_{k-1}b=1.$$ Now we finish the proof of the Lemma. It is immediate for $k=0$. If $k=1$, then $(-1{)}^{k-1}=1$, so $$-b/2<0⩽(-1{)}^{k-1}{q}_{k-1}⩽b/2.$$ If $k>1$, we have $q_{k-1}<b/2$, so $$-b/2<(-1{)}^{k-1}{q}_{k-1}<b/2.$$ Thus, for any $k>0$, we find that $g(a,b)=\left((-1{)}^{k-1}{q}_{k-1},(-1{)}^k{p}_{k-1}\right)$, and so $$f(a,b)=1⟺k\text{ is odd }⟺u=(-1{)}^{k-1}{q}_{k-1}>0.$$