Teorema di Wilson: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Aggiungo: he:משפט וילסון |
→Collegamenti esterni: Aggiunto il template "Collegamenti esterni" |
||
| (91 versioni intermedie di 37 utenti non mostrate) | |||
Riga 1:
In [[Teoria dei numeri]], il '''teorema di Wilson''' afferma che, dato
:<math>(
(
== Storia ==
Questo teorema fu scoperto per la prima volta da [[Ibn al-Haytham]] (conosciuto anche come '''Alhazen''') intorno all'anno mille<ref>O'Connor, John J.; Robertson, Edmund F., "Abu Ali al-Hasan ibn al-Haytham", MacTutor History of Mathematics archive, University of St Andrews.</ref>, ma ha preso il nome da [[John Wilson (matematico)|John Wilson]] (allora studente del matematico inglese [[Edward Waring]]), che lo riscoprì più di 700 anni dopo. Waring annunciò il teorema nel [[1770]], nonostante né lui né Wilson possedessero una dimostrazione. [[Joseph Louis Lagrange|Lagrange]] diede la prima dimostrazione nel [[1773]]<ref>Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers," ''Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin'', vol. 2, pages 125–137 (1771).</ref>. Vi sono alcune ragioni per credere che [[Gottfried Leibniz|Leibniz]] conoscesse questo risultato già un secolo prima, ma non lo pubblicò mai.
== Esempi ==
Applichiamo il teorema di Wilson ai numeri 5 e 6:
* Per il numero 5 si ha: (4! + 1) = (24 + 1) = 25, che infatti è un multiplo di 5.
* Per il numero 6 si ha: (5! + 1) = (120 + 1) = 121, che non è un multiplo di 6.
La tabella seguente mostra i valori di ''n'' da 2 a 30, (''n''-1)! e il resto di (''n''-1)! nella divisione per ''n''. Indichiamo il resto di ''m''/''n'' come ''m'' mod ''n''. Se ''n'' è un numero primo, allora il colore di sfondo è <span style="background-color:#FFC0CB">rosa</span>. E se ''n'' è un numero composto, quindi il colore di sfondo è <span style="background-color:#98FB98">verde pallido</span>.
{| class="wikitable" style="text-align:right"
|+ Tabella di resto modulo ''n''
! <math>n</math> !! <math>(n-1)!</math> !! <math>(n-1)!\ \bmod\ n</math>
|- style="background-color:#FFC0CB"
| 2 || 1 || 1
|- style="background-color:#FFC0CB"
| 3 || 2 || 2
|- style="background-color:#98FB98"
| 4 || 6 || 2
|- style="background-color:#FFC0CB"
| 5 || 24 || 4
|- style="background-color:#98FB98"
| 6 || 120 || 0
|- style="background-color:#FFC0CB"
| 7 || 720 || 6
|- style="background-color:#98FB98"
| 8 || 5040 || 0
|- style="background-color:#98FB98"
| 9 || 40320 || 0
|- style="background-color:#98FB98"
| 10 || 362880 || 0
|- style="background-color:#FFC0CB"
| 11 || 3628800 || 10
|- style="background-color:#98FB98"
| 12 || 39916800 || 0
|- style="background-color:#FFC0CB"
| 13 || 479001600 || 12
|- style="background-color:#98FB98"
| 14 || 6227020800 || 0
|- style="background-color:#98FB98"
| 15 || 87178291200 || 0
|- style="background-color:#98FB98"
| 16 || 1307674368000 || 0
|- style="background-color:#FFC0CB"
| 17 || 20922789888000 || 16
|- style="background-color:#98FB98"
| 18 || 355687428096000 || 0
|- style="background-color:#FFC0CB"
| 19 || 6402373705728000 || 18
|- style="background-color:#98FB98"
| 20 || 121645100408832000 || 0
|- style="background-color:#98FB98"
| 21 || 2432902008176640000 || 0
|- style="background-color:#98FB98"
| 22 || 51090942171709440000 || 0
|- style="background-color:#FFC0CB"
| 23 || 1124000727777607680000 || 22
|- style="background-color:#98FB98"
| 24 || 25852016738884976640000 || 0
|- style="background-color:#98FB98"
| 25 || 620448401733239439360000 || 0
|- style="background-color:#98FB98"
| 26 || 15511210043330985984000000 || 0
|- style="background-color:#98FB98"
| 27 || 403291461126605635584000000 || 0
|- style="background-color:#98FB98"
| 28 || 10888869450418352160768000000 || 0
|- style="background-color:#FFC0CB"
| 29 || 304888344611713860501504000000 || 28
|- style="background-color:#98FB98"
| 30 || 8841761993739701954543616000000 || 0
|}
== Dimostrazioni==
=== Prima dimostrazione ===
Questa dimostrazione sfrutta il fatto che gli [[Anello (algebra)#Elementi invertibili|elementi invertibili]] dell'[[Anello (algebra)|Anello]] <math>\Z/n</math> delle [[classi di resto]] degli interi modulo n sono determinati mediante la [[Funzione φ di Eulero]] di n ovvero rappresentate dagli interi positivi m tali che m < n ed m coprimo con n. Quindi, se ''p'' è un primo, l'insieme <math>G = (\Z/p)^*= \{1, 2, \dots , p-1\}</math> forma un [[Gruppo (matematica)|gruppo]] nell'operazione di moltiplicazione modulo ''p''. Ciò significa che per ogni elemento ''i'' in ''G'', esiste un unico inverso ''j'' in ''G'' tale che ''ij'' ≡ 1 (mod ''p''). Se ''i'' ≡ ''j'' (mod ''p''), allora ''i''<sup>2</sup> ≡ 1 (mod ''p''), che implica ''i''<sup>2</sup> − 1 = (''i'' + 1)(''i'' − 1) ≡ 0 (mod ''p''), e poiché ''p'' è primo, questo implica che ''i'' ≡ 1 o −1 (mod ''p''), cioè ''i'' = 1 o ''i'' = ''p'' − 1.
In altri termini, 1 e ''p'' − 1 sono gli unici termini che coincidono con i loro inversi, mentre ogni altro elemento di ''G'' ha un inverso diverso da sé stesso, perciò se raccogliamo gli elementi di ''G'' a coppie in questa maniera e li moltiplichiamo, il prodotto risultante sarà −1 ovvero
<math>(p-1)! = (p-1)(p-2)\cdots 2\cdot 1\equiv (p-1)\cdot 1\equiv -1 \mod p</math>
Per esempio, se ''p'' = 11, abbiamo
:<math>10! = 1(10)(2 \cdot 6)(3 \cdot 4)(5 \cdot 9)(7 \cdot 8) \ \equiv\ -1\ (\mbox{mod}\ 11).</math>
Se ''p'' = 2, è banale la verifica del risultato.
Per quanto riguarda il teorema inverso (vedi sotto per maggiori dettagli), supponiamo che la congruenza valga per un [[numero composto|composto]] ''n''. Allora ''n'' ha un divisore proprio ''d'' tale che 1 < ''d'' < ''n''. Ovviamente ''d'' divide (''n'' − 1)! e, per ipotesi, ''d'' divide anche (''n'' − 1)! + 1.
Ma allora ''d'' divide anche la loro differenza, cioè ''d'' divide (''n'' − 1)! + 1 - (''n'' − 1)! = 1, e ciò è assurdo.
=== Seconda dimostrazione ===
Qui vi è un'altra dimostrazione del teorema.
Supponiamo che ''p'' sia un primo dispari. Si consideri il [[polinomio]]
:<math>g(x)=(x-1)(x-2) \cdots (x-(p-1))</math>
:<math>f(x)=g(x)-(x^{p-1}-1).</math>
Poiché i coefficienti dei termini di grado massimo si annullano, possiamo dedurre che ''f''(''x'') è un polinomio di grado, al più, ''p''
Ma dal momento che ''p'' è dispari, il termine costante di ''f''(''x'') è uguale a (''p''
== Applicazioni ==
Il teorema di Wilson è inutilizzabile come [[test di primalità]], dal momento che il calcolo esplicito di (''n'' − 1)! mod ''p'', richiedendo ''n'' moltiplicazioni, è difficile per ''n'' grande.
Usando il teorema di Wilson, abbiamo per ogni primo ''p'':
Riga 46 ⟶ 116:
:<math>1\cdot 2\cdots (p-1)\ \equiv\ -1\ (\mbox{mod}\ p)</math>
:<math>1\cdot(p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv\ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv\ -1\ (\mbox{mod}\ p),</math>
dove ''p'' = 2''m'' + 1. Questo diventa:
:<math>\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1}\ (\mbox{mod}\ p).</math>
:<math>\left( \prod_{j=1}^{2k}\ j \right)^{2} = \prod_{j=1}^{2k}\ j^2\ \equiv (-1)^{2k+1}\ = -1(\mbox{mod}\ p).</math>
=== Formula esatta per π(''x'')===
Dal teorema di Wilson si può ricavare facilmente una formula per il numero di numeri primi minori di ''x''. Infatti vale:
:<math>\left(p-1\right)! \equiv -1 \pmod{p}</math>
per ogni numero primo ''p'', e inoltre:
:<math>\left(n-2\right)! \equiv 0 \pmod{n}</math>
per ogni numero composto ''n'' > 4. Utilizzando questi fatti si dimostra che, per ''n''
:<math>\pi(x)= \sum_{5 \leq n \leq x} n \left\{ \frac{\left(n-2\right)!}{n}\right\} + 2,</math>
dove <math>\lbrace x \rbrace </math> indica la parte frazionaria di ''x''. Questa formula sfrutta il fatto che, per ''n'' > 4, <math>\left\{ \frac{\left(n-2\right)!}{n}\right\}</math> è uguale a 0 se ''n'' è composto, a <math>\frac{1}{n}</math> se ''n'' è primo. Essa risulta comunque inutile nelle applicazioni poiché richiede una mole di calcoli di gran lunga più elevata del [[crivello di Eratostene]], e va quindi considerata solo come una curiosità matematica.
== Generalizzazione ==
Vi è anche una generalizzazione del teorema di Wilson, dovuta a [[Carl Friedrich Gauss]]:
:<math>\prod_{\begin{matrix} 1 \le a <
dove ''p'' è un primo dispari.
Proviamo la generalizzazione. Per <math>n=2</math> la verifica è immediata, pertanto considereremo gli altri casi.
I casi dove la [[produttoria]] è congrua a <math>-1</math> sono i casi in cui il modulo è ciclico, infatti <math>\mathbb{Z}_n</math> si può partizionare in tre insiemi distinti <math>I_0, I_1, I_2</math> dove:
:<math>I_0=\left\{x \in \mathbb{Z}_n :(x,n)\ne 1\right\}</math> , <math>I_1=\left\{x \in \mathbb{Z}_n :(x,n)=1\land x^2\not\equiv1 \pmod {n}\right\}</math>, <math>I_2=\left\{x \in \mathbb{Z}_n :(x,n)=1 \land x^2\equiv1 \pmod {n}\right\}.</math>
Ora si ha che:
:<math>\prod_{\begin{matrix} 1 \le a < n \\ (a,n)=1 \end{matrix}} a\equiv\prod_{x \in I_1} x \prod_{y \in I_2} y \pmod {n}.</math>
L'insieme <math>I_1</math> contiene ogni elemento ed il suo inverso, pertanto la produttoria vale 1 (In questo insieme ogni elemento è distinto dal suo inverso). L'insieme <math>I_2</math> contiene tutte le radici seconde dell'unità, pertanto è un gruppo rispetto alla moltiplicazione. In particolare, contenendo l'elemento <math>-1,</math> si ha che
:<math>-1, x \in I_2 \Rightarrow -x \in I_2</math>
e poiché ogni elemento è distinto dal suo opposto, per assurdo
:<math>x \equiv -x \pmod {n} \Rightarrow 2x \equiv 0 \pmod {n}.</math>
Ma poiché <math>x</math> è invertibile otteniamo <math>n=2</math> , valore che avevamo escluso. Quindi si ha che in <math>I_2</math> gli opposti sono distinti e pertanto <math>\left | I_2 \right |=2r</math> ed enumerandoli:
:<math>I_2=\left\{x_1 ,-x_1, x_2,-x_2, \ldots, x_r, -x_r\right\}.</math>
Quindi:
:<math>\prod_{y \in I_2} y\equiv (x_1)(-x_1)(x_2)(x_2)\ldots(x_r)(-x_r)\equiv(-1)^r (x_1)^2(x_2)^2\ldots(x_r)^2 \pmod{n}.</math>
Guardando alla definizione di <math>I_2 </math> abbiamo
:<math>\prod_{y \in I_2} y \equiv (-1)^r \pmod{n},</math>
dove <math>r</math> è la metà del numero di soluzioni dell'equazione <math>x^2-1 \equiv 0 \pmod{n}</math>. Poiché il numero di soluzioni di tale equazioni vale:
* <math>2^{\omega(n)} </math> se <math>\nu_2 (n)=0,2;</math>
* <math>2^{\omega(n)-1} </math> se <math>\nu_2 (n)=1;</math>
* <math>2^{\omega(n)+1} </math> se <math>\nu_2 (n)>2.</math>
Qui <math>\nu_2 (n)</math> è una [[Valutazione p-adica|valutazione]]. Sostituendo otteniamo
:<math>\prod_{\begin{matrix} 1 \le a < n \\ (a,n)=1 \end{matrix}} a \equiv (-1)^{2^{\omega(n)+s}} \pmod{n},</math>
dove
* <math>s=-1</math> se <math>\nu_2 (n)=0,2;</math>
* <math>s=-2 </math> se <math>\nu_2 (n)=1;</math>
* <math>s=0 </math> se <math>\nu_2 (n)>2.</math>
Si vede quindi che solo i moduli ciclici hanno <math>r=1</math> , mentre per i moduli non ciclici <math>r</math> è pari.
==Teorema inverso==
L'inverso del teorema di Wilson afferma che, dato un [[numero composto]] <math>n>5</math>,
:<math>n|(n-1)!.</math>
Ciò non considera il caso <math>n=4</math>, per cui <math>3! \equiv 2 \pmod{4}.</math>
Infatti, se <math>q</math> è un [[fattore primo]] di <math>n</math> tale che <math>n=qa</math>, la sequenza
:<math>1, 2,\cdots, n-1</math>
include <math>a-1</math> multipli di <math>q</math>. Dunque la massima potenza di <math>q</math> che divide il fattoriale è almeno <math>{n \over q}-1</math> e la massima potenza che divide <math>n</math> è al più
:<math>{{\log n} \over {\log q}}.</math>
La [[disuguaglianza (matematica)|disuguaglianza]] richiesta
:<math>{{\log
è valida in generale, ad eccezione del caso
==Note==
<references />
==Bibliografia==
*Luca Barbieri Viale, Teorema 4.28, ''Che cos'è un numero ?'' Raffaello Cortina, 2013, ISBN 978-88-6030-604-3
*{{Cita libro|Harold|Davenport|Aritmetica superiore|1994|Zanichelli|Bologna|isbn=88-08-09154-6}}
*{{Cita libro|Trygve|Nagell|Introduction to number theory|2001|Chelsea|New York|isbn=0-8218-2833-9|ed=2}}
==Collegamenti esterni==
* {{Collegamenti esterni}}
* {{cita web|http://www.math.unipr.it/~zaccagni/psfiles/papers/importanza.pdf|Saggio sui numeri primi, con una sezione dedicata al teorema di Wilson|formato=pdf}}
{{Algebra}}
{{Teoria dei numeri}}
{{Portale|matematica}}
[[Categoria:Aritmetica modulare]]
[[
| |||