Wilsons teorem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 1. oktober 2021; checks kræver 3 redigeringer .

Wilsons sætning er en sætning i talteori , der siger det

Hvis er et primtal, så er tallet deleligt med . Omvendt, hvis det er deleligt med , så er det et primtal. $s$ $(p-1)!+1$ $s$ $(p-1)!+1$ $s$ $s$

Denne teorem er hovedsageligt af teoretisk betydning, da faktortallet er ret vanskeligt at beregne. Det er lettere at beregne , så elementære test , der afgør, om et tal er primtal, er baseret på Fermats sætning , ikke Wilsons sætning. For eksempel er det største primtal fundet ved brug af Wilsons sætning sandsynligvis 1099511628401, og selv med en optimeret beregningstilgang vil det tage omkring en dag med beregninger på SPARC-processorer , og tal med titusindvis af cifre består primalitetstesten vha. Fermats teorem på mindre end en time. Men i modsætning til Fermats lille sætning er Wilsons sætning både en nødvendig og tilstrækkelig betingelse for enkelhed. $(p-1)!$ $a^{p-1}$ $p!$

Historie

Denne sætning blev først fremsat af Ibn al-Haytham omkring 1000 e.Kr., [1] og i 1770 formulerede Waring denne sætning i sin Meditationes Algebraicae udgivet i Cambridge, han giver Wilsons sætning uden bevis. Ifølge ham tilhører teoremet hans elev Wilson . Han offentliggjorde først beviset for teoremet i den tredje udgave af hans Meditationes i 1782. Det første bevis for Wilsons teorem blev givet i 1771 af Lagrange [2] .

Endelig Euler i Opusc. Analyt , bind 1, s. 329 gav et bevis, Gauss generaliserede Wilsons teorem til tilfældet med et sammensat modul. Der er beviser for, at Leibniz kendte til resultatet et århundrede tidligere, men aldrig offentliggjorde det.

Eksempel

Tabellen indeholder værdier for p fra 2 til 31, såvel som resten af divisionen med p (resten af divisionen af m med p er betegnet som m mod p ). Primtal er fremhævet med grønt . $(p-1)!$ $(p-1)!$

Tabel over rester modulo n

$s$	$(p-1)!$	$(p-1)!{\bmod {p}}$
2	en	en
3	2	2
fire	6	2
5	24	fire
6	120	0
7	720	6
otte	5040	0
9	40320	0
ti	362880	0
elleve	3628800	ti
12	39916800	0
13	479001600	12
fjorten	6227020800	0
femten	87178291200	0
16	1307674368000	0
17	20922789888000	16
atten	355687428096000	0
19	6402373705728000	atten
tyve	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
tredive	8841761993739701954543616000000	0
31	265252859812191058636308480000000	tredive

Bevis

Tilstrækkelighed

Lad p være primtal.

Metode 1

Overvej . Sættet af ikke-nul restklasser modulo p modulo multiplikation er en gruppe , og er så produktet af alle elementer i gruppen . Da det er en gruppe, er der for hvert af dets elementer et unikt omvendt element . Korrespondancen deler gruppen op i klasser: hvis (som svarer til , altså da en ligning af anden grad ikke kan have mere end to løsninger), så indeholder klassen et element , ellers består klassen af to elementer - . Så hvis en klasse indeholder ét element , så er produktet af alle dens elementer lig , og hvis klassen indeholder 2 elementer, så er produktet af alle dens elementer lig med 1. Nu, i produktet, grupperer vi elementerne efter klasser, er alle produkter efter 2-elementklasser simpelthen lig med 1: $(p-1)!$ ${\mathbb {Z}}_{p}^{{\times }}$ $(p-1)!$ ${\mathbb {Z}}_{p}^{{\times }}$ ${\mathbb {Z}}_{p}^{{\times }}$ $-en$ $a^{{-1}}:aa^{{-1}}\equiv 1{\pmod p}$ $a\to a^{{-1}}$ $a=a^{{-1}}$ $a^{2}=1$ $a\in\{1,-1\}$ $-en$ $\{a,a^{{-1}}\}$ $-en$ $-en$ $(p-1)!$

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

■

Metode 2

Gruppen er cyklisk , dvs. der er et element således, at der for ethvert element eksisterer sådan, at . Da det har et grundstof, løber det gennem værdierne fra 0 til når det løber gennem hele gruppen af rester. Derefter ${\mathbb {Z}}_{p}^{{\times }}$ $g$ $-en$ $k$ $a=g^{k}$ ${\mathbb {Z}}_{p}^{{\times }}$ $p-1$ $k$ $p-1$ $-en$

(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}.

■

Metode 3

${\mathbb {Z}}_{p}^{{\times }}$ - felt , derfor finder Lagrange-sætningen sted i det , dvs. gradpolynomiet har ikke mere end rødder. Overvej polynomier og . Begge polynomier har rødder (for dette opnås ved Fermats lille sætning ), graderne af polynomierne er ens , de førende koefficienter er de samme. Så har polynomiet mindst de samme rødder, men dets grad er højst . Derfor, ifølge Bezouts sætning, er det identisk lig med nul, dvs. for alle vil det være , i særdeleshed , hvilket svarer til . Vi får påstanden om sætningen for , da det er lige og dermed . ■ $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$

Brug for

Hvis og er sammensat , så , og for, får vi . $s$ $p\neq 4$ $(p-1)!\equiv 0{\pmod {p))$ $p=4$ $(4-1)!\equiv 2{\pmod 4}$

Geometrisk bevis for tilstrækkelighed

Lad p være et primtal. Lad os omnummerere hjørnerne af en regulær p - gon i rækkefølgen for at krydse konturen: 1, 2, 3, ..., p . Hvis vi forbinder dem med diagonaler i serie gennem en, derefter gennem to, gennem tre osv., så får vi udover den regulære polygon 123... også ( p − 2) polygoner 135..., 147.. ., 159.. osv. Disse ( p − 1) polygoner er parvis identiske, da vi ved at forbinde hjørnerne gennem k og gennem ( p − k − 2) opnår identiske polygoner. Antallet af forskellige regulære polygoner opnået på denne måde er ; $(p-1)/2$
Hvis vi forbinder hjørnerne i en anden rækkefølge, for eksempel i rækkefølgen 13245..., så får vi en uregelmæssig polygon; drejer denne polygon, så tallene på dens hjørner erstattes af tallene i den næste rækkefølge (tallet p er erstattet af en), får vi p uregelmæssige polygoner. I ovenstående eksempel vil disse være polygoner 13245..., 24356..., 35467..., ..., 2134... Hvis vi danner alle mulige uregelmæssige polygoner på denne måde, så vil deres antal være et multiplum af p , men som i tilfældet med regulære polygoner er de to identiske; det er to sekvenser af hjørner, direkte og inverse, der giver den samme polygon;
Hvis vi laver alle mulige permutationer ( p − 1) af toppunkter 23... i rækkefølgen af toppunkter 123... , så får vi alle mulige (regulære og irregulære) polygoner; deres antal vil være ; de vil igen være identiske i par, så deres reelle tal er ; $1\cdot 2\cdot 3\cdots (p-1)=(p-1)!'$ $(p-1)!/2$
Ved at sammenligne resultaterne fra punkt 1 og 3 ser vi, at antallet af uregelmæssige polygoner vil være lig med: . Fra punkt 2 skal dette tal være deleligt med p ; derfor ( p − 1)! + 1 multiplum p .: ■ $1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)$

Ansøgning

Vi bruger Wilson-sætningen

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

For et ulige primtal p = 2 m + 1 får vi

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}}.

Som resultat

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

Vi kan bruge denne kendsgerning til at bevise et velkendt resultat: for ethvert primtal p sådan at p ≡ 1 (mod 4), er tallet (−1) en kvadratisk ( kvadratisk rest ) mod p . Faktisk lad p = 4 k + 1 for nogle naturlige k . Så m = 2 k , derfor

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

Wilsons sætning bruges til at generere primtal, men den er for langsom til praktisk brug.

Generalisering

Lad os bruge Eulers sætning som eksempel , og lad os prøve at generalisere Wilsons sætning til tilfældet p = n , hvor n er et vilkårligt naturligt tal. En simpel ændring ( p − 1)! produktet n 1 n 2 ... n k af alle tal mindre end n og relativt primtal til n passerer ikke: i tilfælde af n = 8 er dette produkt 1 × 3 × 5 × 7 = 105, og 106 er ikke deleligt med 8. Men det viser sig, at enten n 1 n 2 … n k + 1, eller n 1 n 2 … n k − 1 nødvendigvis er delelig med n .

Betragt mængden E n af tal mindre end n og relativt primtal til n . Under produktet af to elementer i denne mængde ab , mener vi resten af at dividere det sædvanlige produkt ab med n . Det er klart, at hvis a , b hører til E n , så hører ab til E n . Mængden E n med hensyn til driften af multiplikation er en gruppe. I modsætning til tilfældet, hvor n er primtal, kan gruppen E n indeholde elementer, der ikke er lig med 1 og ( n − 1), således at deres kvadrat er lig med 1: for eksempel, hvis n = 8, så 3 × 3 = 1,5 × 5 = 1, 7 × 7 = 1. Derfor er produktet af alle elementer fra E n i det generelle tilfælde ikke lig med ( n − 1). Lad os vise, at det så er lig med 1.

Vi kalder et element a i gruppen E n specielt, hvis aa = 1. I dette tilfælde er elementet n − a også specielt. Derfor indeholder gruppen E n et lige antal specielle elementer: ( a , n − a ) er mængden af sådanne elementer, og intet element kan være et par for sig selv. Lad n 1 , n 2 , …, n k være alle elementer i gruppen E n , det vil sige et komplet sæt tal mindre end n og relativt primtal til n . Sættet af elementer, der ikke er specielle, er opdelt i par af indbyrdes omvendte, så produktet af sådanne elementer er lig med 1. På den anden side er produktet af specielle elementer, der udgør parret ( a , n − a ) er lig med n − 1. Da ( n − 1)( n − 1) = 1, så er produktet af alle specialelementer lig med 1 eller n − 1, afhængig af om antallet af par af formen ( a , n − a ) er lige eller ulige. ■

Sætningen blev først bevist og generaliseret af Gauss , for enhver n > 2, for produktet af alle naturlige tal, der ikke overstiger n og coprime til n , finder en sammenligning sted:

\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}}

hvor er et ulige primtal, er en naturlig indikator. $s$ $\alfa$

Senere blev der fundet en anden formel generalisering af Wilsons teorem (V. Vinograd):

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

Ved opnås Wilsons sætning. $m=1$

Når det viser sig , dvs. $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}}$ , hvis $p\equiv 1{\pmod {4}}$

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

Se også

Noter

↑ John J. O'Connor og Edmund F. Robertson . Abu Ali al-Hasan ibn al-Haytham (engelsk) er en biografi på MacTutor- arkivet .
↑ Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers" Arkiveret 11. maj 2022 på Wayback Machine (Bevis for en ny sætning om primtal), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles- Lettres Berlin), bind. 2, side 125-137 (1771)

Litteratur

Bukhshtab A. A. Theory of Numbers, 2. udgave, M., 1966
Trost E. Primtal, overs. fra German, M., 1959
Vinogradov I.M. Grundlæggende om talteori . - 5. udg. - M. - L .: Gostekhizdat, 1952.
R. Crandall, K. Dilcher og C. Pomerance Den primære ordliste
Ore, O. Talteori og dens historie. McGraw-Hill, 1948.
Bonchkovsky R. N. og Chistyakov I. I. Matematisk uddannelse, udgave 01

Ordbøger og encyklopædier	Flot dansk Great Soviet (1 udg.) Britannica (online)