TdN: il teorema di Wilson
Inviato: 11 giu 2005, 09:27
Siccome se n'è parlato di recente, colgo l'occasione per inserirlo nella lista dei topic del glossario!
Teorema di Wilson: un intero $ n \geq 2 $ è primo sse $ (n-1)! \equiv - 1 \bmod n $.
Dim. [1]: la condizione è necessaria. Infatti, se $ n $ è primo, ogni intero positivo $ k < n $ è primo con $ n $, dunque invertibile $ \!\bmod\, n $. Del resto, l'equazione $ x^2 \equiv 1 \bmod n $, quando $ n $ sia un modulo primo, possiede le uniche soluzioni modulari $ x = 1 $ ed $ x = n-1 $. Se dunque $ n \geq 5 $, gli interi $ 2, 3, \ldots, n-2 $ possono essere associati a formare $ (n-3)/2 $ coppie di tipo $ (a, b) $ in cui $ b = a^{-1} $, ove $ a^{-1} $ denota qui l'inverso di $ a $ modulo $ n $. E allora, ancora per $ n \geq 5 $: $ \displaystyle (n-1)! \equiv (n-1)\cdot \prod_{k=2}^{n-2} k $ $ \equiv (n-1) \equiv - 1 \bmod n $. La tesi è poi banalmente soddisfatta (per verifica diretta) se $ n = 2 $ oppure $ n = 3 $.
La condizione è sufficiente. Supposto infatti $ (n-1)! \equiv -1 \bmod n $, ammettiamo pur tuttavia per assurdo che $ n $ possa essere composto. Esiste allora un intero $ m > 1 $ tale che $ m \mid n $, perciocché $ m \leq n-1 $, e dunque $ (n-1)! \equiv -1 \bmod n $ solo se $ 0 \equiv (n-1)! \equiv -1 \bmod m $, che è assurdo!!! Di qui la tesi, q.e.d.
Dim. [2]: vi propongo una variante per dimostrare la parte necessaria del teorema cui ho pensato tempo fa spazzolandomi i dentuzzi. Se $ n = 2 $, la tesi è banalmente verificata. Sia pertanto nel seguito $ n \geq 3 $. Poiché $ n $ è primo, esiste $ g\in\mathbb{Z} $ tale che $ g $ sia una radice primitiva $ \!\bmod n $, e per ogni $ k = 1, 2, \ldots, n-1 $ esiste dunque, e univocamente determinato, un intero $ e_k \in \{1, 2, \ldots, n-1\} $ tale che $ g^{e_k} \equiv k \bmod n $. E allora: $ \displaystyle (n-1)! \equiv \prod_{k=1}^{n-1} k \equiv $ $ \displaystyle \prod_{k=1}^{n-1} g^{e_k} \equiv g^{\sum_{k=1}^{n-1} e_k} \bmod n $. Ma $ \displaystyle\sum_{k=1}^{n-1} e_k = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} $, sicché (in ultima analisi): $ (n-1)! \equiv g^{\frac{1}{2}n(n-1)} \equiv - 1 \bmod n $, poiché (per ipotesi) $ g $ è una radice primitiva $ \!\bmod n $, e dunque (per il lemma di Eulero): $ g^{(n-1)/2} \equiv - 1 \bmod n $. Di qui l'asserto, q.e.d.
Teorema di Wilson: un intero $ n \geq 2 $ è primo sse $ (n-1)! \equiv - 1 \bmod n $.
Dim. [1]: la condizione è necessaria. Infatti, se $ n $ è primo, ogni intero positivo $ k < n $ è primo con $ n $, dunque invertibile $ \!\bmod\, n $. Del resto, l'equazione $ x^2 \equiv 1 \bmod n $, quando $ n $ sia un modulo primo, possiede le uniche soluzioni modulari $ x = 1 $ ed $ x = n-1 $. Se dunque $ n \geq 5 $, gli interi $ 2, 3, \ldots, n-2 $ possono essere associati a formare $ (n-3)/2 $ coppie di tipo $ (a, b) $ in cui $ b = a^{-1} $, ove $ a^{-1} $ denota qui l'inverso di $ a $ modulo $ n $. E allora, ancora per $ n \geq 5 $: $ \displaystyle (n-1)! \equiv (n-1)\cdot \prod_{k=2}^{n-2} k $ $ \equiv (n-1) \equiv - 1 \bmod n $. La tesi è poi banalmente soddisfatta (per verifica diretta) se $ n = 2 $ oppure $ n = 3 $.
La condizione è sufficiente. Supposto infatti $ (n-1)! \equiv -1 \bmod n $, ammettiamo pur tuttavia per assurdo che $ n $ possa essere composto. Esiste allora un intero $ m > 1 $ tale che $ m \mid n $, perciocché $ m \leq n-1 $, e dunque $ (n-1)! \equiv -1 \bmod n $ solo se $ 0 \equiv (n-1)! \equiv -1 \bmod m $, che è assurdo!!! Di qui la tesi, q.e.d.
Dim. [2]: vi propongo una variante per dimostrare la parte necessaria del teorema cui ho pensato tempo fa spazzolandomi i dentuzzi. Se $ n = 2 $, la tesi è banalmente verificata. Sia pertanto nel seguito $ n \geq 3 $. Poiché $ n $ è primo, esiste $ g\in\mathbb{Z} $ tale che $ g $ sia una radice primitiva $ \!\bmod n $, e per ogni $ k = 1, 2, \ldots, n-1 $ esiste dunque, e univocamente determinato, un intero $ e_k \in \{1, 2, \ldots, n-1\} $ tale che $ g^{e_k} \equiv k \bmod n $. E allora: $ \displaystyle (n-1)! \equiv \prod_{k=1}^{n-1} k \equiv $ $ \displaystyle \prod_{k=1}^{n-1} g^{e_k} \equiv g^{\sum_{k=1}^{n-1} e_k} \bmod n $. Ma $ \displaystyle\sum_{k=1}^{n-1} e_k = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} $, sicché (in ultima analisi): $ (n-1)! \equiv g^{\frac{1}{2}n(n-1)} \equiv - 1 \bmod n $, poiché (per ipotesi) $ g $ è una radice primitiva $ \!\bmod n $, e dunque (per il lemma di Eulero): $ g^{(n-1)/2} \equiv - 1 \bmod n $. Di qui l'asserto, q.e.d.