For prime $p$, let, $ S = \{ x \in \mathbb{Z}_p^* | \phi(1-x^2) = 1 \}$, where $p=4k+1$ and $\phi$ is Legendre symbol. I have to prove that $|S| = 2(k-1)$.
I know that there are $(p-1)/2$ residues and $(p-1)/2$ non-residues in $\mathbb{Z}_p$. However I cannot seem to use this fact.
You want to calculate $$\begin{align*} S &= \frac12 \sum_{x \in (\mathbb Z / p \mathbb Z)^\times} \left[ \left( \frac{1-x^2}p\right)+1 \right] - 1\\ &= \frac{p-1}{2} - 1 + \frac12 \sum_{x \in (\mathbb Z / p \mathbb Z)^\times} \left( \frac{1-x^2}p\right) \\ &= \frac{p-3}{2} + \frac12 \sum_{x \in \mathbb Z / p \mathbb Z} \left( \frac{1-x^2}p\right) - \frac12 \\ &= \frac{p-4}{2} + \frac12 \sum_{x \in \mathbb Z / p \mathbb Z} \left( \frac{1-x^2}p\right) \end{align*}$$ (where the $-1$ comes from the terms for $x = \pm 1$). Let's compute the latter sum. It equals $$\begin{align*} \sum_{x \in (\mathbb Z / p \mathbb Z) - \{1\}} \left( \frac{\frac{1+x}{1-x}}p\right) \end{align*}$$ The map $x \mapsto \frac{1+x}{1-x}$ is a bijection from $\mathbb Z / p \mathbb Z - \{1\}$ to $\mathbb Z / p \mathbb Z - \{-1\}$. Thus the sum equals $$\begin{align*} \sum_{x \in (\mathbb Z / p \mathbb Z) - \{-1\}} \left(\frac xp\right) = -\left( \frac{-1}p \right) \,. \end{align*}$$ We conclude that for any odd prime $p$, $$S = \frac{p-4}2 - \frac12 \left( \frac{-1}p \right)$$