It suffices to exhibit one element $a\in\mathbb{Z}_{n}^{*}$ which does not satisfy Equation (1). Indeed, if there exists one such element, then the set of all elements which do satisfy Equation (1) forms a proper subgroup of $\mathbb{Z}_{n}^{*}$, from which we conclude that the elements satisfying Equation (1) number no more than half of the elements of $\mathbb{Z}_{n}^{*}$.

We consider separately the cases where $n$ is squarefree and not squarefree. If $n$ is squarefree, let $p$ be a prime dividing $n$ and let $b$ be a quadratic non-residue mod $n$. Using the Chinese Remainder Theorem, choose an integer $a\in\mathbb{Z}_{n}^{*}$ such that:

The Jacobi symbol ${\genfrac{(}{)}{}{}{a}{n}}$ is given by

We will assume that $a^{{\frac{n-1}{2}}}\equiv-1\;\;(\mathop{{\rm mod}}n)$ and derive a contradiction. The equation $a^{{\frac{n-1}{2}}}\equiv-1\;\;(\mathop{{\rm mod}}n)$ implies that $a^{{\frac{n-1}{2}}}\equiv-1\;\;(\mathop{{\rm mod}}\frac{n}{p})$. However, since $a\equiv 1\;\;(\mathop{{\rm mod}}\frac{n}{p})$, we must have $a^{{\frac{n-1}{2}}}\equiv 1\;\;(\mathop{{\rm mod}}\frac{n}{p})$, so that $1\equiv-1\;\;(\mathop{{\rm mod}}\frac{n}{p})$, which is a contradiction.

Now suppose that $n$ is not squarefree. Let $p$ be a prime such that $p^{2}\mid n$, and set $a=1+\frac{n}{p}$. By the binomial theorem, we have

so the multiplicative order of $a\bmod n$ is equal to $p$, and hence in particular $a^{{n-1}}\neq 1\;\;(\mathop{{\rm mod}}n)$, since $p\nmid n-1$. On the other hand,

so $a$ does not satisfy Equation (1). ∎