Cardinality of $ S = \{ x \in \mathbb{Z}_p^* | \phi(1-x^2) = 1 \}$ 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.
 A: 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)$$
