$\DeclareMathOperator{\ord}{ord}$ Let $g$ be a generator of $Z^*_p$, where $p$ is a prime number. Let $a = g^s$ be a non-quadratic residue in $Z^*_p$, that is, $J(a,p) = -1$, where $J$ describes the Jacobi symbol. It seems that $$\ord(a,p) \times s = 0 \bmod{p - 1}.$$
Why is this true?
Here's a proof of the fact.
Proof. By the definition of order, we have
$$1 = a^{\ord(a,p)} = (g^s)^{\ord(a,p)} = g^{s \ord(a,p)}.$$
By the definition of generator, $\ord(g,p) = p - 1$, so $1 = g^{s \ord(a,p)}$ either implies $s \ord(a,p) = p - 1$, which is a multiple of $p - 1$, or $s \ord(a,p)$ is a multiple of $p - 1$. Either way,
$$s \ord(a,p) = \ord(a,p) s = k (p - 1) = 0 \bmod{p - 1},$$
as desired.
Thanks @RoddyMacPhee for not leaving me alone on this.