E infatti..
Dato che $a=n-1$ deve verificare $a^{a-1}\equiv 1 \pmod n$ allora $2\mid n$.
Sia $\displaystyle n=2^{\alpha_0}\prod_{1\le i\le \omega}{p_i^{\alpha_i}}$ la fattorizzazione canonica di $n$, per qualche intero $\alpha_0\ge 1$, e notiamo che la condizione $a^{a-1}\equiv 1 \pmod n$
equivale al sistema di congruenze:
- $a^{a-1}\equiv 1 \pmod {2^{\alpha_0}}$
- $a^{a-1}\equiv 1 \pmod {p_1^{\alpha_1}}$
- $a^{a-1}\equiv 1 \pmod {p_2^{\alpha_2}}$
- $\ldots$
- $a^{a-1}\equiv 1 \pmod {p_{\omega}^{\alpha_{\omega}}}$
Supponiamo che $\alpha_0\ge 2$ allora $a\equiv 1\pmod{2^{\alpha_0-1}}\implies a^2\equiv 1\pmod{2^{\alpha_0}}\implies a^{a-1}\equiv 1\pmod {2^{\alpha_0}}$ per cui il sistema
- $a\equiv 1 \pmod {2^{\alpha_0-1}}$
- $a\equiv -1 \pmod {p_1^{\alpha_1}}$
- $a\equiv -1 \pmod {p_2^{\alpha_2}}$
- $\ldots$
- $a\equiv -1 \pmod {p_{\omega}^{\alpha_{\omega}}}$
fornisce due soluzioni nell'insieme $\{2,3,\ldots,n-1\}$. E' sufficiente a concludere che $\alpha_0=1$.
Supponiamo ora che esiste un primo $p_i$ tale che $\alpha_i\ge 2$, e notiamo che $(p_i^{\alpha_i-1}+1)^{p_i^{\alpha_i-1}}\equiv 1\pmod{p_i^{\alpha_i}}$ per cui il sistema
- $a\equiv -1 \pmod 2$
- $a\equiv -1 \pmod {p_1^{\alpha_1}}$
- $a\equiv -1 \pmod {p_2^{\alpha_2}}$
- $\ldots$
- $a\equiv p_i^{\alpha_i-1}+1 \pmod{p_i^{\alpha_i}}$
- $\ldots$
- $a\equiv -1 \pmod {p_{\omega}^{\alpha_{\omega}}}$
fornisce un'altra soluzione nell'insieme $\{2,3,\ldots,n-1\}$ differente da $n-1$. Questo significa che $\alpha_0=\alpha_1=\alpha_2=\ldots=\alpha_{\omega}=1$.
Infine, supponiamo che $\omega\ge 2$ allora la condizione $a^{a-1}\equiv 1 \pmod{p_i}$ e' soddisfatta sia da $1$ che da $-1$, considerando che $a-1$ e' sicuramente pari. Questo significa che il sistema
- $a\equiv 1 \pmod 2$
- $a\equiv \pm 1 \pmod {p_1}$
- $a\equiv \pm 1 \pmod {p_2}$
- $\ldots$
- $a\equiv \pm 1 \pmod {p_{\omega}}$
avrebbe piu' di una soluzione nell'insieme $\{2,3,\ldots,n-1\}$.
Da quanto detto possiamo concludere che se $n-1$ e' l'unico intero in $\{2,3,\ldots,n-1\}$ tale che $n\mid a^{a-1}-a$ allora $\frac{n}{2}$ e' primo. []