Teorema lui Wilson

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În teoria numerelor , teorema lui Wilson afirmă că, dat fiind n > 1 natural, este un număr prim dacă și numai dacă

sau, în formă echivalentă,

(a se vedea aritmetica factorială și modulară pentru notație). Prin urmare, teorema oferă o condiție necesară și suficientă pentru a stabili dacă un număr n ≥ 2 este prim .

Istorie

Această teoremă a fost descoperită pentru prima dată de Ibn al-Haytham (cunoscut și sub numele de Alhazen ) în jurul anului o mie [1] , dar a fost numită după John Wilson (pe atunci student al matematicianului englez Edward Waring ), care a redescoperit-o mai mult de 700 de ani mai târziu . Waring a anunțat teorema în 1770 , deși nici el, nici Wilson nu dețineau o dovadă. Lagrange a dat prima dovadă în 1773 [2] . Există câteva motive pentru a crede că Leibniz a cunoscut acest rezultat cu un secol mai devreme, dar nu l-a publicat niciodată.

Exemple

Să aplicăm teorema lui Wilson la numerele 5 și 6:

  • Pentru numărul 5 avem: (4! + 1) = (24 + 1) = 25, care este de fapt un multiplu al lui 5.
  • Pentru numărul 6 avem: (5! + 1) = (120 + 1) = 121, care nu este multiplu de 6.

Următorul tabel prezintă valorile lui n de la 2 la 30, ( n -1)! iar restul de ( n -1)! în împărțirea cu n . Notăm restul m / n ca m mod n . Dacă n este un număr prim, atunci culoarea de fundal este roz . Și dacă n este un număr compus, atunci culoarea de fundal este verde pal .

Modul tabel de odihnă nr
2 1 1
3 2 2
4 6 2
5 24 4
6 120 0
7 720 6
8 5040 0
9 40320 0
10 362880 0
11 3628800 10
12 39916800 0
13 479001600 12
14 6227020800 0
15 87178291200 0
16 1307674368000 0
17 20922789888000 16
18 355687428096000 0
19 6402373705728000 18
20 121645100408832000 0
21 2432902008176640000 0
22 51090942171709440000 0
23 1124000727777607680000 22
24 25852016738884976640000 0
25 620448401733239439360000 0
26 15511210043330985984000000 0
27 403291461126605635584000000 0
28 10888869450418352160768000000 0
29 304888344611713860501504000000 28
30 8841761993739701954543616000000 0

Demonstrații

Prima demonstrație

Această dovadă exploatează faptul că dacă p este un prim impar, atunci mulțimea G = ( Z / p Z ) × = {1, 2, ... p - 1} formează un grup în operația de multiplicare modulo p . Aceasta înseamnă că pentru fiecare element i din G , există un j invers unic în G astfel încât ij ≡ 1 (mod p ). Dacă ij (mod p ), atunci i 2 ≡ 1 (mod p ), ceea ce implică i 2 - 1 = ( i + 1) ( i - 1) ≡ 0 (mod p ) și din moment ce p este prim, aceasta implică faptul că i ≡ 1 sau −1 (mod p ), adică i = 1 sau i = p - 1.

Cu alte cuvinte, 1 și p - 1 sunt singurii termeni care coincid cu inversele lor, în timp ce fiecare alt element al lui G are un invers diferit de el însuși, deci dacă colectăm elementele lui G în perechi în acest fel și le înmulțim, produsul rezultat va fi -1.

De exemplu, dacă p = 11, avem

Dacă p = 2, verificarea rezultatului este banală.

În ceea ce privește teorema inversă (a se vedea mai jos pentru mai multe detalii), să presupunem că congruența este valabilă pentru un compus n . Atunci n are un divizor propriu d astfel încât 1 < d < n . Evident d împarte ( n - 1)! și, prin ipoteză, d împarte și ( n - 1)! + 1. Dar apoi d împarte și diferența lor, adică d împarte ( n - 1)! + 1 - ( n - 1)! = 1, ceea ce este absurd.

A doua dovadă

Iată o altă dovadă a teoremei.

Să presupunem că p este un prim ciudat. Luați în considerare polinomul

amintindu-ne că, dacă f ( x ) este un polinom diferit de zero de grad d într-un câmp F , atunci f ( x ) admite cel mult d rădăcini pe F [3] . Să luăm acum în considerare polinomul

Deoarece coeficienții termenilor de grad maxim se anulează reciproc, putem deduce că f ( x ) este un polinom de grad, cel mult, p - 2. Prin reducerea modulului p , deducem apoi că f ( x ) admite la majoritatea p - 2 rădăcini mod p . Dar, conform teoremei lui Fermat , fiecare dintre elementele 1, 2, ..., p - 1 este o rădăcină a lui f ( x ). Acest lucru este imposibil, cu excepția cazului în care f ( x ) este identic zero mod p , iar acest lucru se poate întâmpla numai dacă fiecare coeficient al lui f ( x ) este divizibil cu p .

Dar, din moment ce p este impar, termenul constant al lui f ( x ) este egal cu ( p - 1)! + 1, iar din aceasta urmează teza.

Aplicații

Teorema lui Wilson este inutilizabilă ca test de primărie , deoarece calculul explicit al lui ( n - 1)! mod p , care necesită n multiplicări, este dificil pentru n mare.

Folosind teorema lui Wilson, avem pentru fiecare p prim:

unde p = 2 m + 1. Aceasta devine:

Prin urmare, primalitatea este determinată de reziduurile pătratice modulo p . Putem folosi acest fapt pentru a dovedi o parte a unui rezultat cunoscut: -1 este un mod rezidual pătratic p dacă p ≡ 1 (mod 4). De fapt, să presupunem p = 4 k + 1 pentru un număr întreg k . Atunci putem lua m = 2 k în relația anterioară și putem concluziona că

Formula exactă pentru π ( x )

Din teorema lui Wilson putem obține cu ușurință o formulă pentru numărul de numere prime mai mici decât x . De fapt, se aplică următoarele:

pentru orice număr prim p , și mai mult:

pentru orice număr compus n > 4. Folosind aceste fapte se poate demonstra că, pentru n ≥ 5:

unde este denotă partea fracționată a lui x . Această formulă profită de faptul că, pentru n > 4, este egal cu 0 dacă n este compus, a dacă n este prim. Cu toate acestea, este inutil în aplicații, deoarece necesită o cantitate mult mai mare de calcule decât sita lui Eratostene și, prin urmare, ar trebui considerată doar ca o curiozitate matematică.

Generalizare

Există, de asemenea, o generalizare a teoremei lui Wilson, datorită lui Carl Friedrich Gauss :

unde p este un prim ciudat.

Să încercăm generalizarea. Pentru verificarea este imediată, așa că vom lua în considerare celelalte cazuri.

Cazurile în care producția este adecvată a sunt de fapt cazurile în care modulul este ciclic poate fi partiționat în trei seturi distincte unde este:

, ,

Acum avem asta:

Întregul conține fiecare element și inversul său, prin urmare produsul valorează 1 (În acest set fiecare element este distinct de inversul său). Întregul conține toate a doua rădăcini ale unității, prin urmare este un grup în ceea ce privește multiplicarea. Mai exact, prin conținerea elementului , avem asta

și întrucât fiecare element este distinct de opusul său, prin absurditate

Dar de atunci este inversabil pe care îl obținem , o valoare pe care o excludusem. Așa că avem asta în contrariile sunt distincte și prin urmare și enumerându-le:

Prin urmare:

Privind definiția avem

unde este este jumătate din numărul de soluții ale ecuației . Întrucât numărul soluțiilor unor astfel de ecuații este valabil

  • de sine
  • de sine
  • de sine

Unde este este o evaluare . Înlocuind obținem:

Unde este

  • de sine
  • de sine
  • de sine

Prin urmare, se vede că numai modulele ciclice au , în timp ce pentru module neciclice este chiar.

Teorema inversă

Inversul teoremei lui Wilson afirmă că dat un număr compus ,

Acest lucru nu ia în considerare cazul , asa de

De fapt, dacă este un factor prim al astfel încât , secvența

include multipli de . Prin urmare puterea maximă de care împarte factorialul este cel puțin și puterea maximă care împarte este cel mult

Inegalitatea necesară

este valabil în general, cu excepția cazului în care este cazul și

Notă

  1. ^ O'Connor, John J.; Robertson, Edmund F., „Abu Ali al-Hasan ibn al-Haytham”, arhiva MacTutor History of Mathematics, Universitatea din St Andrews.
  2. ^ Joseph Louis Lagrange, "Demonstration of a théorème nouveau concernant les nombres premiers", Nouveaux Mémoires de l'Académie Royale des Sciences și Belles-Lettres de Berlin , vol. 2, paginile 125–137 (1771).
  3. ^ Teorema fundamentală a algebrei

Bibliografie

  • Harold Davenport, Arithmetic Superior , Bologna, Zanichelli, 1994, ISBN 88-08-09154-6 .
  • Trygve Nagell, Introducere în teoria numerelor , ediția a II-a, New York, Chelsea, 2001, ISBN 0-8218-2833-9 .

linkuri externe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică