Se n-1 è l'unico a = 2, ..., n-1 t.c. a^{a-1} = 1 mod n

[HiTLeuLeR]

(very late) EDIT: ho modificato il testo secondo le indicazioni di jordan. ma_go

Essendo $ n $ un numero naturale $ > 2 $, si dimostri che, quando $ n-1 $ è l'unico intero $ a \in \{2, 3, \ldots, n-1\} $ tale che $ a^{a-1} \equiv 1 \bmod n $, allora $ n = 2p $, per qualche primo naturale $ p > 2 $.

[jordan]

Essendo $ n $ un numero naturale $ > 2 $, si dimostri che, quando $ n-1 $ è l'unico intero $ a \in \{2, 3, \ldots, p-1\} $ tale che $ a^{a-1} \equiv 1 \bmod n $, allora $ n = 2p $, per qualche primo naturale $ p > 2 $.

Mmh e' sicuro che c'è qualche refuso nel testo: in particolare, se fosse vero, allora $n-1\le p-1 \implies n\le p$, ma allora non puo' essere $2p$..

Ps. Credo che sia sufficiente sostituire l'insieme $\{2, 3, \ldots, p-1\}$ con $\{2, 3, \ldots, n-1\}$: in tal caso ho mostrato che $n$ deve essere della forma $2m$ con $m$ dispari e libero da quadrati; se cio' è vero, mostrato che $\omega(m)=1$, postero' la soluzione

[jordan]

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. []