Se n > 0: n | a^n - 1 sse p | n => p^2 \nmid n & p

[HiTLeuLeR]

Essendo $ n $ un intero positivo, mostrare che le seguenti condizioni sono fra loro equivalenti: a) $ n \mid (a^n - a) $, per ogni intero $ a > 0 $; b) se $ p $ è primo in $ \mathbb{N} $ e $ p \mid n $, allora $ p^2 \nmid n $ e $ (p-1) \mid (n-1) $. (Turchia 1995)

[Simo_the_wolf]

Se $ p|n $ allora avremo che $ n|p^n-p $ che se $ p^2|n $ sarebbe falso. Quindi $ n $ è libero da quadrati. Adesso consideriamo:

$ a^n \equiv a \pmod{p} $

E prendiamo a come un generatore modulo p. Allora si dovrà avere per forza, siccome $ p|a^{n-1}-1 $ che $ p-1|n-1 $ poichè l'ordine moltiplicativo di un generatore mod p è $ \phi(p)=p-1 $.

L'inverso è (quasi) ovvio...