Teorema lui Wilson

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 octombrie 2021; verificările necesită 3 modificări .

Teorema lui Wilson este o teoremă în teoria numerelor care afirmă că

Dacă este un număr prim, atunci numărul este divizibil cu . În schimb, dacă este divizibil cu , atunci este un număr prim. $p$ $(p-1)!+1$ $p$ $(p-1)!+1$ $p$ $p$

Această teoremă este în principal de importanță teoretică, deoarece factorialul este destul de dificil de calculat. Este mai ușor de calculat , așa că testele elementare care determină dacă un număr este prim se bazează pe teorema lui Fermat , nu pe teorema lui Wilson. De exemplu, cel mai mare număr prim găsit folosind teorema lui Wilson este probabil să fie 1099511628401 și, chiar și cu o abordare optimizată de calcul, va dura aproximativ o zi de calcule pe procesoarele SPARC , iar numerele cu zeci de mii de cifre trec testul de primalitate folosind Teorema lui Fermat în mai puțin de o oră. Dar, spre deosebire de mica teoremă a lui Fermat, teorema lui Wilson este atât o condiție necesară, cât și suficientă pentru simplitate. $(p-1)!$ $a^{p-1}$ $p!$

Istorie

Această teoremă a fost formulată pentru prima dată de Ibn al-Haytham în jurul anului 1000 d.Hr. [1] și în 1770 Waring a formulat această teoremă în Meditationes Algebraicae publicată la Cambridge, el dă teorema lui Wilson fără dovezi. Potrivit lui, teorema îi aparține studentului său Wilson . El a publicat demonstrația teoremei abia în cea de-a treia ediție a Meditationes în 1782. Prima demonstrație a teoremei lui Wilson a fost dată în 1771 de Lagrange [2] .

În fine, Euler în Opusc. Analyt , vol . 1, p. 329 a dat o demonstrație, Gauss a generalizat teorema lui Wilson în cazul unui modul compus. Există dovezi că Leibniz știa despre rezultat cu un secol mai devreme, dar nu l-a publicat niciodată.

Exemplu

Tabelul conține valori pentru p de la 2 la 31, precum și restul împărțirii cu p (restul divizării lui m cu p este notat cu m mod p ). Numerele prime sunt evidențiate cu verde . $(p-1)!$ $(p-1)!$

Tabelul resturilor modulo n

$p$	$(p-1)!$	$(p-1)!{\bmod {p}}$
2	unu	unu
3	2	2
patru	6	2
5	24	patru
6	120	0
7	720	6
opt	5040	0
9	40320	0
zece	362880	0
unsprezece	3628800	zece
12	39916800	0
13	479001600	12
paisprezece	6227020800	0
cincisprezece	87178291200	0
16	1307674368000	0
17	20922789888000	16
optsprezece	355687428096000	0
19	6402373705728000	optsprezece
douăzeci	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	155112100433330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
treizeci	8841761993739701954543616000000	0
31	265252859812191058636308480000000	treizeci

Dovada

Adecvarea

Fie p prim.

Metoda 1

Luați în considerare . Mulțimea claselor de reziduuri non-nule modulo p modulo multiplicare este un grup și apoi este produsul tuturor elementelor grupului . Deoarece este un grup, atunci pentru fiecare dintre elementele sale există un element invers unic . Corespondența împarte grupul în clase: dacă (care este echivalent cu , adică , deoarece o ecuație de gradul doi nu poate avea mai mult de două soluții), atunci clasa conține un element , în caz contrar clasa este formată din două elemente - . Deci, dacă o clasă conține un element , atunci produsul tuturor elementelor sale este egal , iar dacă clasa conține 2 elemente, atunci produsul tuturor elementelor sale este egal cu 1. Acum, în produs, grupăm elementele după clase, toate produsele din clase cu 2 elemente sunt pur și simplu egale cu 1: $(p-1)!$ ${\mathbb {Z}}_{p}^{{\times }}$ $(p-1)!$ ${\mathbb {Z}}_{p}^{{\times }}$ ${\mathbb {Z}}_{p}^{{\times }}$ $A$ $a^{{-1}}:aa^{{-1}}\equiv 1{\pmod p}$ $a\la a^{{-1}}$ $a=a^{{-1}}$ $a^{2}=1$ $a\în\{1,-1\}$ $A$ $\{a,a^{{-1}}\}$ $A$ $A$ $(p-1)!$

(p-1)!\equiv \prod \limits _{{a^{2}=1}}a\cdot \prod \limits _{{a^{2}\neq 1}}a\equiv \prod \ limite _{{a^{2}=1}}a\equiv 1\cdot (-1)\equiv -1{\pmod p}.

■

Metoda 2

Grupul este ciclic , adică există un element astfel încât pentru orice element există astfel încât . Deoarece are un element, acesta parcurge valorile de la 0 până la momentul în care trece prin întregul grup de reziduuri. Apoi ${\mathbb {Z}}_{p}^{{\times }}$ $g$ $A$ $k$ $a=g^{k}$ ${\mathbb {Z}}_{p}^{{\times }}$ $p-1$ $k$ $p-1$ $A$

(p-1)!\equiv g^{1}g^{2}\ldots g^{{p-1}}\equiv g^{{{1+2+\ldots +(p-1)}}= g^{{{\frac {p-1}{2}}p}}\equiv (-1)^{p}\equiv -1{\pmod p}.

■

Metoda 3

${\mathbb {Z}}_{p}^{{\times }}$ - câmp , prin urmare, în el are loc teorema Lagrange , adică polinomul de grad nu are mai mult decât rădăcini. Luați în considerare polinoamele și . Ambele polinoame au rădăcini (pentru aceasta se obține prin mica teoremă a lui Fermat ), gradele polinoamelor sunt egale , coeficienții conducători sunt aceiași. Atunci polinomul are cel puțin aceleași rădăcini, dar gradul său este de cel mult . Prin urmare, conform teoremei lui Bezout, este identic egal cu zero, adică pentru toate va fi , în special , care este echivalent cu . Obținem afirmația teoremei pentru , deoarece este par și deci . ■ $n$ $n$ $f(x)=(x-1)\ldots (x-(p-1))$ $g(x)=x^{{p-1}}-1$ $1,2,\ldots ,p-1$ $g(x)$ $p-1$ $h(x)=f(x)-g(x)$ $p-1$ $p-2$ $h(x)$ $X$ $f(x)=g(x)$ $f(0)=g(0)$ $(-1)^{{p-1}}(p-1)!\equiv -1{\pmod p}$ $p>2$ $p-1$ $(-1)^{{p-1}}=1$

Nevoie

Dacă și este compus , atunci , și pentru , obținem . $p$ $p\neq 4$ $(p-1)!\equiv 0{\pmod {p))$ $p=4$ $(4-1)!\equiv 2{\pmod 4}$

Dovada geometrică a suficienței

Fie p un număr prim. Să renumerotăm vârfurile unui p -gon regulat în ordinea parcurgerii conturului: 1, 2, 3, ..., p . Dacă le conectăm prin diagonale în serie prin unu, apoi prin doi, prin trei etc., atunci pe lângă poligonul obișnuit 123..., obținem și ( p − 2) poligoane 135..., 147.. ., 159.. etc. Aceste ( p − 1) poligoane sunt identice pe perechi, deoarece unind vârfurile prin k și prin ( p − k − 2) se obține poligoane identice. Numărul de poligoane regulate diferite obținute în acest mod este ; $(p-1)/2$
Dacă conectăm vârfurile într-o altă ordine, de exemplu în ordinea 13245..., atunci obținem un poligon neregulat; rotind acest poligon astfel încât numerele vârfurilor sale să fie înlocuite cu numerele următoare în ordine (numărul p este înlocuit cu unul), obținem p poligoane neregulate. În exemplul de mai sus, acestea vor fi poligoane 13245..., 24356..., 35467..., ..., 2134... Dacă formăm toate poligoanele neregulate posibile în acest fel, atunci numărul lor va fi un multiplu de p , dar, ca și în cazul poligoanelor regulate, acestea sunt două identice; sunt două șiruri de vârfuri, directe și inverse, care dau același poligon;
Dacă facem toate permutările posibile ( p − 1) ale vârfurilor 23... în succesiunea vârfurilor 123... , atunci obținem toate poligoanele posibile (regulate și neregulate); numărul lor va fi ; vor fi din nou identici în perechi, deci numărul lor real este ; $1\cdot 2\cdot 3\cdots (p-1)=(p-1)!'$ $(p-1)!/2$
Comparând rezultatele de la punctele 1 și 3, vedem că numărul de poligoane neregulate va fi egal cu: . De la punctul 2, acest număr trebuie să fie divizibil cu p ; prin urmare ( p − 1)! + 1 multip .: ■ $1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)$

Aplicație

Folosim teorema Wilson

1\cdot 2\cdots (p-1)\equiv -1{\pmod {p)).

Pentru un prim impar p = 2 m + 1 , obținem

1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (pm)\equiv 1\cdot (-1)\cdot 2\cdot (-2)\cdots m \cdot (-m)\equiv -1{\pmod {p}}.

Ca urmare

\prod _{j=1}^{m}j^{2}\equiv (-1)^{m+1}{\pmod {p)).

Putem folosi acest fapt pentru a demonstra un rezultat binecunoscut: pentru orice prim p astfel încât p ≡ 1 (mod 4), numărul (−1) este un pătrat ( reziduu pătratic ) mod p . Într-adevăr, fie p = 4 k + 1 pentru unele k naturale . Atunci m = 2 k , deci

{\biggl (}\prod _{j=1}^{2k}\ j{\biggr )}^{2}=\prod _{j=1}^{2k}j^{2}\ echiv (-1)^{2k+1}=-1{\pmod {p)).

Teorema lui Wilson este folosită pentru a genera numere prime, dar este prea lentă pentru utilizare practică.

Generalizare

Folosind teorema lui Euler ca exemplu , să încercăm să generalizăm teorema lui Wilson în cazul p = n , unde n este un număr natural arbitrar. O simplă schimbare ( p − 1)! produsul n 1 n 2 ... n k al tuturor numerelor mai mici decât n și relativ prim la n nu trece: în cazul lui n = 8, acest produs este 1 × 3 × 5 × 7 = 105, iar 106 este nu este divizibil cu 8. Dar se dovedește că fie n 1 n 2 … n k + 1, fie n 1 n 2 … n k − 1 este în mod necesar divizibil cu n .

Se consideră mulțimea E n de numere mai mici decât n și relativ prime la n . Sub produsul a două elemente din această mulțime ab , înțelegem restul împărțirii produsului obișnuit ab la n . Este clar că dacă a , b aparține lui E n , atunci ab aparține lui E n . Mulțimea E n cu privire la operația de înmulțire este un grup. Spre deosebire de cazul în care n este prim, grupul E n poate conține elemente care nu sunt egale cu 1 și ( n − 1) astfel încât pătratul lor să fie egal cu 1: de exemplu, dacă n = 8, atunci 3 × 3 = 1,5 × 5 = 1, 7 × 7 = 1. Prin urmare, în cazul general, produsul tuturor elementelor din E n nu este egal cu ( n − 1). Să arătăm că atunci este egal cu 1.

Numim un element a din grupul E n special dacă aa = 1. În acest caz, elementul n − a este de asemenea special. Prin urmare, grupul E n conține un număr par de elemente speciale: ( a , n − a ) este mulțimea unor astfel de elemente și niciun element nu poate fi o pereche pentru el însuși. Fie n 1 , n 2 , …, n k toate elementele grupului E n , adică un set complet de numere mai mici decât n și relativ prime cu n . Mulțimea elementelor care nu sunt speciale este împărțită în perechi de elemente reciproc inverse, deci produsul acestor elemente este egal cu 1. Pe de altă parte, produsul elementelor speciale care alcătuiesc perechea ( a , n − a ) este egal cu n − 1. Deoarece ( n − 1)( n − 1) = 1, atunci produsul tuturor elementelor speciale este egal cu 1 sau n − 1, în funcție de numărul de perechi de forma ( a , n − a ) este par sau impar. ■

Teorema a fost mai întâi demonstrată și generalizată de Gauss , pentru orice n > 2, pentru produsul tuturor numerelor naturale care nu depășesc n și coprime la n , are loc o comparație:

\prod _{{k=1 \atop (k,n)=1}}^{{n}}\!\!k\equiv {\begin{cases}-1{\pmod {n)),&n= 4,\;p^{\alpha },\;2p^{\alpha }\,;\\\;\;\,1{\pmod {n)),&n\neq 4,\;p^{\ alpha },\;2p^{\alpha }\,,\end{cases}}

unde este un număr prim impar, este un indicator natural. $p$ $\alfa$

Mai târziu, a fost găsită o altă generalizare formală a teoremei lui Wilson (V. Vinograd):

$(pm)!*(m-1)!\equiv (-1)^{m}{\pmod {p))$

La , se obține teorema lui Wilson. $m=1$

Când se dovedește , i.e. $m=\left({\frac {p+1}{2}}\right)$ $\left({\frac {p-1}{2}}\right)!^{2}+(-1)^{\left({\frac {p-1}{2}}\right) )}\equiv 0{\pmod {p}}$

$\left({\frac {p-1}{2}}\right)!^{2}+1\equiv 0{\pmod {p}}$ , dacă $p\equiv 1{\pmod {4}}$

și

$\left({\frac {p-1}{2}}\right)!^{2}-1\equiv 0{\pmod {p}}$ , dacă $p\equiv 3{\pmod {4}}$

Vezi și

Note

↑ John J. O'Connor și Edmund F. Robertson . Abu Ali al-Hasan ibn al-Haytham (engleză) este o biografie din arhiva MacTutor .
↑ Joseph Louis Lagrange, „Demonstration d'un théorème nouveau concernant les nombres premiers” Arhivat la 11 mai 2022 la Wayback Machine (Dovada unei noi teoreme privind numerele prime), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres ( Berlin), voi. 2, paginile 125-137 (1771)

Literatură

Bukhshtab A. A. Teoria numerelor, ediția a 2-a, M., 1966
Trost E. Numere prime, trad. din germană, M., 1959
Vinogradov I.M. Fundamentele teoriei numerelor . - Ed. a V-a - M. - L .: Gostekhizdat, 1952.
R. Crandall, K. Dilcher și C. Pomerance Glosarul principal
Ore, O. Teoria numerelor și istoria ei. McGraw-Hill, 1948.
Bonchkovsky R. N. și Chistyakov I. I. Educație matematică, numărul 01

Dicționare și enciclopedii	mare danez Marele Soviet (1 ed.) Britannica (online)