Sea $\psi(d)$ denotan el número de elementos de orden $d$ en $\mathbb Z_p^*$ .
Tenga en cuenta que si $a\in\mathbb Z_p^*$ tiene orden $d$ entonces $a^r$ tiene orden $d$ sólo si $\gcd(r,d)=1$ .
Así son precisamente $\phi(d)$ elementos de la forma de $a^r$ que tienen orden $d$ .
De ello se deduce que $\phi(d)$ divide $\psi(d)$ para todos $d$ .
Utilizando (1) queremos demostrar que $\psi(d)$ es $0$ o igual a $\phi(d)$ para todos $d|(p-1)$ .
Supongamos, por el contrario, que existe algún $d$ dividiendo $p-1$ tal que $\psi(d)>\phi(d)$ .
Sea $a$ sea un elemento de orden $d$ .
Fuera del $d$ elementos $a,a^2,\ldots,a^d$ Precisamente $\phi(d)$ tener orden $d$ .
Por nuestra suposición, hay un elemento $b$ de orden $d$ que no es igual a ninguno de los $a^i$ 's.
Pero tenga en cuenta que $b$ y cada $a^i$ satisface $x^d\equiv 1\pmod{p}$ .
Esto significa que la congruencia $x^d\equiv 1\pmod{p}$ tiene más de $d$ soluciones, contrariamente a (1).
Así que tenemos $\psi(d)=0$ o $\phi(d)$ .
Tenga en cuenta que $\sum_{d|(p-1)}\psi(d)=p-1$ .
Esto se debe a que cada elemento de $\mathbb Z_p^*$ tiene orden $d$ para algunos $d|p-1$ .
De nuestra inferencia anterior también tenemos $\sum_{d|p-1}\psi(d)\leq \sum_{d|p-1}\phi(d)$ .
El lado derecho es igual a $p-1$ por (2).
Por lo tanto, no podemos tener $\psi(d)=0$ para cualquier $d|p-1$ y por lo tanto $\psi(p-1)>0$ demostrando que hay un elemento de orden $p-1$ (y, por tanto, precisamente $\phi(p-1)$ tales elementos).
