A Wilson- tétel a számelmélet egyik tétele, amely azt állítja
Ha prímszám, akkor a szám osztható -vel . Ezzel szemben, ha osztható -vel , akkor prímszámról van szó. |
Ennek a tételnek elsősorban elméleti jelentősége van, mivel a faktoriálist meglehetősen nehéz kiszámítani. Könnyebb kiszámítani , így azok az elemi tesztek , amelyek meghatározzák, hogy egy szám prím-e, Fermat tételén alapulnak , nem pedig Wilson tételén. Például a Wilson-tétel segítségével talált legnagyobb prímszám valószínűleg 1099511628401, és még optimalizált számítási megközelítés mellett is körülbelül egy napot vesz igénybe a számítások SPARC processzorokon , és a több tízezer számjegyből álló számok átmennek a primalitási teszten Fermat-tétel kevesebb, mint egy óra alatt. De ellentétben Fermat kis tételével, Wilson tétele egyszerre szükséges és elégséges feltétele az egyszerűségnek.
Ezt a tételt Ibn al-Haytham fogalmazta meg először i.sz. 1000 körül, [1] és 1770-ben Waring fogalmazta meg ezt a tételt a Cambridge-ben megjelent Meditationes Algebraicae című művében, Wilson tételét bizonyíték nélkül adja meg. Szerinte a tétel Wilson tanítványáé . A tétel bizonyítását csak 1782-ben publikálta Meditációi harmadik kiadásában. A Wilson-tétel első bizonyítékát 1771-ben Lagrange adta [2] .
Végül Euler az Opuscban. Analyt , 1. kötet , p. 329 bizonyítást adott, Gauss általánosította Wilson tételét egy összetett modul esetére. Bizonyítékok vannak arra, hogy Leibniz egy évszázaddal korábban tudott az eredményről, de soha nem publikálta.
A táblázat tartalmazza a p értékeit 2-től 31-ig, valamint a p -vel való osztás maradékát ( m - nek p -vel való osztásának maradékát m mod p -ként jelöljük ). A prímszámok zölddel vannak kiemelve .
2 | egy | egy |
3 | 2 | 2 |
négy | 6 | 2 |
5 | 24 | négy |
6 | 120 | 0 |
7 | 720 | 6 |
nyolc | 5040 | 0 |
9 | 40320 | 0 |
tíz | 362880 | 0 |
tizenegy | 3628800 | tíz |
12 | 39916800 | 0 |
13 | 479001600 | 12 |
tizennégy | 6227020800 | 0 |
tizenöt | 87178291200 | 0 |
16 | 1307674368000 | 0 |
17 | 20922789888000 | 16 |
tizennyolc | 355687428096000 | 0 |
19 | 6402373705728000 | tizennyolc |
húsz | 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 |
harminc | 8841761993739701954543616000000 | 0 |
31 | 265252859812191058636308480000000 | harminc |
Legyen p prím.
1. módszerFontolja meg . A modulo p modulo szorzás nem nulla maradék osztályok halmaza egy csoport , majd a csoport összes elemének szorzata . Mivel egy csoport, ezért minden eleméhez egyedi inverz elem tartozik . A megfeleltetés a csoportot osztályokra osztja: ha (ami ekvivalens -val , vagyis mivel egy másodfokú egyenletnek legfeljebb két megoldása lehet), akkor az osztály egy elemet tartalmaz , ellenkező esetben az osztály két elemből áll - . Tehát, ha egy osztály egy elemet tartalmaz , akkor az összes elemének szorzata egyenlő , ha pedig az osztály 2 elemet tartalmaz, akkor az összes elemének szorzata egyenlő 1-gyel. A szorzatban az elemeket csoportosítjuk osztályok esetén a 2 elemű osztályok összes szorzata egyszerűen egyenlő 1-gyel:
2. módszerA csoport ciklikus , azaz van olyan elem , amelyhez bármely elemhez létezik olyan, hogy . Mivel van egy eleme, a 0-tól kezdve egészen addig, amíg a maradékok teljes csoportján végigfut az értékeken . Akkor
3. módszer- mező , ezért benne játszódik le a Lagrange-tétel , azaz a fokpolinomnak legfeljebb gyöke van. Tekintsük polinomokat és . Mindkét polinomnak van gyöke ( ezt a Fermat-féle kis tétel kapja ), a polinomok fokai egyenlők , a vezető együtthatók azonosak. Ekkor a polinomnak legalább azonos gyöke van, de foka legfeljebb . Ennélfogva Bezout tétele szerint azonosan egyenlő nullával, azaz mindenre lesz , különösen , ami ekvivalens -val . Megkapjuk a tétel állítását -re , mivel páros, és ezért . ■
Ha és összetett , akkor , és for , megkapjuk .
Egy p = 2 m + 1 páratlan prímre azt kapjuk
Ennek eredményeként
Ezt a tényt egy jól ismert eredmény bizonyítására használhatjuk: minden olyan p prím esetén , amelynél p ≡ 1 (mod 4), a (−1) szám egy négyzet ( másodfokú maradék ) mod p . Valóban, legyen p = 4 k + 1 valamilyen természetes k esetén . Ekkor m = 2 k , tehát
A Wilson-tételt prímszámok generálására használják, de a gyakorlati felhasználáshoz túl lassú.
Példaként használva Euler tételét , próbáljuk meg általánosítani a Wilson-tételt a p = n esetre , ahol n tetszőleges természetes szám. Egyszerű változtatás ( p − 1)! az n -nél kisebb és n -hez relatív prímszámok n 1 n 2 ... n k szorzata nem felel meg: n = 8 esetén ez a szorzat 1 × 3 × 5 × 7 = 105, 106 pedig nem osztható 8-cal. De kiderül, hogy vagy n 1 n 2 … n k + 1, vagy n 1 n 2 … n k − 1 szükségszerűen osztható n -nel .
Tekintsük az n -nél kisebb és n -hez viszonyított prímszámok E n halmazát . Az ab halmaz két elemének szorzata alatt a szokásos ab szorzat n -nel való osztásának maradékát értjük . Nyilvánvaló, hogy ha a , b E n -hez tartozik , akkor ab E n - hez tartozik . Az E n halmaz a szorzás műveletére nézve egy csoport. Ellentétben azzal az esettel, amikor n prím, az E n csoport tartalmazhat olyan elemeket, amelyek nem egyenlők 1-gyel és ( n − 1) úgy, hogy négyzetük egyenlő 1-gyel: például ha n = 8, akkor 3 × 3 = 1,5 × 5 = 1, 7 × 7 = 1. Ezért általános esetben az E n -ből származó összes elem szorzata nem egyenlő ( n − 1). Mutassuk meg, hogy akkor egyenlő 1-gyel.
Az E n csoport egy a elemét speciálisnak nevezzük, ha aa = 1. Ebben az esetben az n − a elem is speciális. Ezért az E n csoport páros számú speciális elemet tartalmaz: ( a , n − a ) az ilyen elemek halmaza, és egyetlen elem sem lehet pár önmagának. Legyen n 1 , n 2 , …, n k az E n csoport összes eleme , azaz n-nél kisebb és n -hez képest relatív prímszámok teljes halmaza . A nem speciális elemek halmazát kölcsönösen inverzek párjaira osztjuk, így az ilyen elemek szorzata egyenlő 1-gyel. Másrészt az ( a , n − a ) párt alkotó speciális elemek szorzata egyenlő n − 1-gyel. Mivel ( n − 1)( n − 1) = 1, akkor az összes speciális elem szorzata 1 vagy n − 1, attól függően, hogy hány párja van az ( a , n − a ) páros vagy páratlan. ■
A tételt először Gauss bizonyította és általánosította , bármely n > 2 esetén, minden n -t meg nem haladó természetes szám és n -re másodlagos szám szorzatára összehasonlítás történik:
ahol páratlan prímszám, természetes mutató.
Később a Wilson-tétel egy másik formális általánosítására is sor került (V. Vinograd):
A Wilson-tételt kapjuk.
Amikor kiderül , i.e.
, ha
és
, ha
![]() |
|
---|