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 $u a+v b=1$. Moreover, if $(u_{0}, v_{0})$ is one such pair, then all such pairs are of the form $(u, v)=\left(u_{0}+k b, v_{0}-k a\right)$, where $k \in \mathbb{Z}$. So there exists a unique such pair $(u, v)$ with $-b / 2<u \leqslant 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 \Longleftrightarrow 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 \neq 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 \Longleftrightarrow f(a-b, b)=1 \Longleftrightarrow u>0$ by the induction hypothesis.

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

Observe that $f(a, b)=1 \Longleftrightarrow f(b, a)=0 \Longleftrightarrow 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 \Longleftrightarrow v \leqslant 0$ by the inductive hypothesis. Then, since $b>a \geqslant 1$ and $u a+v b=1$, we have $v \leqslant 0 \Longleftrightarrow 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, \ldots, b-1\}$, is at most $b / 2$. Then, for any odd prime $p$ and integer $n$ such that $n \not \equiv 0(\bmod p)$, $f\left(n^{2}, p\right)=1$ iff the inverse of $n^{2} \bmod p$ is less than $p / 2$. Since $\left\{n^{2} \bmod p: 1 \leqslant n \leqslant p-1\right\}=\left\{n^{-2} \bmod p: 1 \leqslant n \leqslant 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.,
$$\left.\sum_{n=1}^{p-1} f\left(n^{2}, p\right)=2 \left\lvert\,\left\{k: 1 \leqslant k \leqslant \frac{p-1}{2} \text{ and } k^{2} \bmod p<\frac{p}{2}\right\}\right. \right\rvert\, .$$
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{2 p}-2 .$$

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}, \ldots, a_{k}$ be positive integers such that $a_{k} \geqslant 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}, \ldots, a_{k}\right] .$$
Then $f(a, b)=0 \Longleftrightarrow k$ is even.

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

Now consider the case $b>1$. Perform the Euclidean division $a=q b+r$, with $0 \leqslant r<b$. We have $r \neq 0$ because $\operatorname{gcd}(a, b)=1$. Hence
$$f(a, b)=f(r, b)=1-f(b, r), \quad \frac{a}{b}=\left[q ; a_{1}, \ldots, a_{k}\right], \quad \text{ and } \quad \frac{b}{r}=\left[a_{1} ; a_{2}, \ldots, 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 \Longleftrightarrow k-1 \text{ is even, }$$
and thus
$$f(a, b)=0 \Longleftrightarrow f(b, r)=1 \Longleftrightarrow k-1 \text{ is odd } \Longleftrightarrow 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}, \ldots, 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}, \ldots, 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} \geqslant 2$, and
$$b=q_{k}=a_{k} q_{k-1}+q_{k-2} \geqslant a_{k} q_{k-1} \geqslant 2 q_{k-1} \Longrightarrow q_{k-1} \leqslant \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 \leqslant(-1)^{k-1} q_{k-1} \leqslant 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 \Longleftrightarrow k \text{ is odd } \Longleftrightarrow u=(-1)^{k-1} q_{k-1}>0 .$$