. First, no integer $x$ is disloyal if it is not coprime with $n$. Therefore, it suffices to show that, among the $\varphi(n)$ elements of $(\mathbb{Z} / n \mathbb{Z})^{*}$, at most $\varphi(n) / p$ are disloyal. Let $a$ be an element of $(\mathbb{Z} / n \mathbb{Z})^{*}$ of order $p(p-1)$ modulo $p^{2}$ and let $\mathcal{D}$ be the set of disloyal elements.

If $x$ and $x^{\prime}$ are two disloyal elements, and for all integers $k \leqslant k^{\prime}$ between 0 and $p-1$, if $a^{k} x=a^{k^{\prime}} x^{\prime}$, then $a^{\left(k^{\prime}-k\right)(n-1)} \equiv x^{n-1} /\left(x^{\prime}\right)^{n-1} \equiv 1\left(\bmod p^{2}\right)$. This shows that $p(p-1)$, and in particular $p$, divides $\left(k^{\prime}-k\right)(n-1)$, so that $k=k^{\prime}$ and thus $x=x^{\prime}$. We conclude that $n-1 \geqslant \varphi(n) \geqslant p|\mathcal{D}|$, which completes the proof.