Grundlæggende sætning for aritmetik

Aritmetikkens grundsætning siger, at [1] [2]

hvert naturligt tal kan faktoriseres ( udvides ) i formen $n>1$ ${\displaystyle n=p_{1}\cdot \ldots \cdot p_{k))$ ${\displaystyle p_{1},\ldots ,p_{k))$

Hvis vi formelt er enige om, at det tomme produkt af et tomt sæt tal er lig med 1, så kan betingelsen i formuleringen udelades - så for enhed er faktorisering med et tomt sæt af primtal underforstået: [3] [ 4] . $n>1$ $1=1$

Som en konsekvens kan hvert naturligt tal repræsenteres som $n$

n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k)),

hvor er primtal, og er nogle naturlige tal,

{\displaystyle p_{1}<p_{2}<\ldots <p_{k))

{\displaystyle d_{1},\ldots ,d_{k))

og på en unik måde. Denne repræsentation af et tal kaldes dets kanoniske faktorisering . $n$

Bevis

Ifølge metoden til induktion

Eksistens : vi vil bevise eksistensen af en faktorisering af et tal til primfaktorer, hvis vi antager, at det samme allerede er blevet bevist for et hvilket som helst andet tal mindre end . Hvis er prime, så er eksistensen bevist. Hvis er sammensat, så kan det repræsenteres som et produkt af to tal og , som hver er større end 1 men mindre end . Tallene og er enten primtal eller kan dekomponeres til et produkt af primtal (allerede bevist tidligere). Ved at erstatte deres nedbrydning i , opnår vi nedbrydningen af det oprindelige tal i primtal. Eksistens er bevist [5] . $n$ $n$ $n$ $n$ $-en$ $b$ $n$ $-en$ $b$ $n=a\cdot b$ $n$

Unikhed : For et primtal er unikhed indlysende.

For et sammensat tal er ideen til beviset at bruge metoden "ved modsigelse" , nemlig den antagelse, at tallet har to forskellige udvidelser. Vi betragter primtal og , som er de mindste i henholdsvis den første og anden af disse udvidelser, og beviser følgende lemma: $p_{0}$ $q_{0}$

hvis nedbrydningen af et tal i primfaktorer er unik, så skal hver primtal divisor inkluderes i denne dekomponering. $m$ $m$

Dernæst betragter vi tallet , som igen er et naturligt tal, og som er mindre end . Det følger af den induktive antagelse og ovenstående lemma, at der er en divisor af det givne tal, hvorefter det tilsvarende konkluderes, at den første faktorisering er delelig med . Intet primtal kan forekomme i begge dekomponeringer på én gang, da det ellers ville være muligt at reducere det og opnå forskellige nedbrydninger til primfaktorer med et tal mindre end . ${\displaystyle n-p_{0}\cdot q_{0))$ $n$ $p_{0}\cdot q_{0}$ $q_{0}$ $n$ $n$

Brug af Euclid-algoritmen

Man kan bevise aritmetikkens grundsætning ved at bruge konsekvensen fra Euklids algoritme [7] :

den største fælles divisor er den største fælles divisor af og ganget med . $n\cdot a$ $n\cdot b$ $-en$ $b$ $n$

Ud fra dette resultat kan man bevise Euklids lemma , også nødvendigt for beviset for sætningen:

hvis er et primtal og produktet af to tal er deleligt med , så er mindst én af de to faktorer delelig med . $s$ $s$ $s$

Eksistens: Ideen bag eksistensbeviset er at bevise lemmaet:

overveje et primtal og et produkt . Hvis det er deleligt med , men ikke deleligt med , så er det deleligt med . $s$ $n\cdot a$ $n\cdot a$ $s$ $-en$ $s$ $n$ $s$

Yderligere, ved at bruge ovenstående lemma, dekomponeres tallet sekventielt i primfaktorer, idet det antages, at alle primtalsdelere af dette tal er kendte.

Unikhed: lad tallet n have to forskellige nedbrydninger til primtal:

n=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots =p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots

Da det er deleligt med , så enten , eller er deleligt med . Hvis er deleligt med , Så , Da begge disse tal er primtal. Hvis det er deleligt med , så fortsætter vi den tidligere begrundelse. I sidste ende vil det vise sig, at et af tallene er lig med tallet , og derfor falder begge udvidelser af tallet faktisk sammen. Dermed er det unikke ved nedbrydningen bevist. $p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1}$ $p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1}$ $p_{1}$ $p'_{1}=p_{1}$ $p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1},p'_{2},p'_{3},\ldots$ $p_{1}$

Historie

Præmisserne for aritmetikkens grundlæggende teorem har deres oprindelse i det antikke Grækenland . På trods af, at i oldgræsk matematik ikke forekommer den grundlæggende aritmetiske sætning i den moderne formulering, har Euklid tilsvarende sætninger i " principperne " ( andre græske Στοιχεῖα ) . Efter Euklid har mange matematikere gennem århundreder bidraget til beviset for aritmetikkens grundlæggende teorem, idet de citerer udsagn, der er tæt på betydningen i deres værker, blandt disse videnskabsmænd er Kamal ad-Din al-Farisi , J. Preste , L Euler , A. Legendre [8] . Den første nøjagtige formulering af aritmetikkens grundsætning og beviset heraf er givet af K. Gauss i bogen " Arithmetical Investigations " ( lat. Disquisitiones Arithmeticae ), udgivet i 1801 [9] . Siden da er der dukket mange forskellige nye beviser for sætningen op, som konkurrerer med hinanden i skønhed og originalitet [8] .

Euklid (3. århundrede f.Kr.)

Euclid fremlagde i Elements vigtige grundlag for talteori, herunder aritmetikkens grundlæggende sætning. Tre sætninger meget tæt i betydningen af aritmetikkens grundlæggende sætning kan findes i bog VII og IX, nemlig påstand 30 fra bog VII, bedst kendt som Euklids Lemma , påstand 31 fra bog VII og påstand 14 fra bog IX. Nedenfor er deres versioner i Morduchai-Boltovskys oversættelse :

VII.30:

Hvis to tal, der multiplicerer hinanden, frembringer noget, og det, der opstår af dem, måles med et første tal, så vil (sidstnævnte) også måle et af de originale [10]

VII.31:

Hvert sammensat tal måles med et første tal [11]

IX.14:

Hvis tallet er det mindste målbare (givet) af de første tal, så kan det ikke måles med noget andet primtal, undtagen dem, der oprindeligt målte (det) [12]

På nuværende tidspunkt[ hvad? ] tid, er beviset for aritmetikkens grundsætning afledt af påstande VII.30 og VII.31, men Euklid fremlagde ikke dette bevis i sine skrifter. Påstand IX.14 er til gengæld ret lig påstanden om det unikke ved faktorisering til primfaktorer, men det viste sig, at dette udsagn ikke dækker alle mulige tilfælde - for eksempel når mindst et kvadrat af et primtal optræder i nedbrydningen til primfaktorer [13] [14] .

Al-Farisi (XIV århundrede)

Den berømte persiske videnskabsmand Kamal ad-Din al-Farisi tog et væsentligt skridt fremad i studiet af aritmetikkens grundlæggende teorem. I sit værk Memorandum for friends on the proof of mindability beviste han eksistensen af en faktorisering til primære faktorer og gav den nødvendige information til at bevise det unikke ved denne nedbrydning. Kamal al-Farisi var dog mest interesseret i at konstruere sit eget bevis for Sabit ibn Kurras sætning om søgen efter venskabelige tal - og al-Farisi søgte ikke at bevise aritmetikkens grundlæggende sætning, men søgte efter alle divisorer af en sammensat nummer [15] . Han undersøgte omhyggeligt faktoriseringen af tal og formulerede og beviste en erklæring, som faktisk viste sig at være et bevis på eksistensen af en faktorisering af et naturligt tal til primfaktorer.

Oversat lyder hans udtalelse noget som dette:

Hvert sammensat tal kan dekomponeres i et endeligt antal primfaktorer, som det er et produkt af.

I Udsagn 9 formulerede al-Farisi et princip for at bestemme alle divisorer af et sammensat tal: dette var præcis, hvad han havde brug for for at bevise Ibn Qurras sætning. Oversættelsen lyder således:

Hvis et sammensat tal er dekomponeret i primfaktorer som , så har det ingen divisor undtagen og og produkterne af hver af dem med hver, produkterne af tripletter osv., op til produktet af alle elementer uden nogen. $-en$ $a=b\cdot c\cdot d\cdot h\cdot \ldots \cdot k\cdot l$ $-en$ $en$ $b,c,d,...,k,l$

Allerede ud fra selve ordlyden af udtalelsen kan man konkludere, at al-Farisi kendte til det unikke ved nedbrydningen til primære faktorer. Derudover er alle udsagn og fakta givet af videnskabsmanden for at bevise denne udsagn et nødvendigt sæt for at bevise det unikke i aritmetikkens hovedsætning.

Jean Preste (1600-tallet)

Resultaterne offentliggjort af Jean Preste i bogen Elements de Mathématiques (1675) bekræfter, at primfaktorisering i de dage ikke blev betragtet som noget af interesse i sig selv, men som en nyttig anvendelse - et middel til at finde divisorer for et givet tal . Preste formulerede hverken eksistensen eller det unikke ved nedbrydningen og var mest opmærksom på selve søgen efter divisorer af et tal [16] . På trods af dette tilvejebragte Preste ligesom al-Farisi al den nødvendige information for at bevise det unikke ved faktorisering ved hjælp af sin Corollary IX, som i sig selv kan betragtes som ækvivalent med det unikke ved faktorisering.

Konsekvens IX:

Hvis tallene og er primtal, så er hver divisor af et tal enten , eller , eller , eller et af produkterne af disse tre tal med . Det er en af seks :. $-en$ $b$ $a\cdot a\cdot b$ $-en$ $a^2$ $en$ $b$ $1,a,a\cdot a,1\cdot b,a\cdot b,a\cdot a\cdot b$

Euler og Legendre (1700-tallet)

I The Complete Guide to Algebra ( tysk: Vollstandige Einleitung zur Algebra ) offentliggjorde Leonhard Euler resultater svarende til sine forgængeres. Han formulerede eksistensen af faktorisering af et tal til primfaktorer, og ved at udelade nogle detaljer gav han et delvist bevis for dette i afsnit 41 i kapitel IV fra den første del af bogens første afsnit.

Dens oversættelse er som følger:

Alle sammensatte tal, der kan faktoriseres, er repræsenteret ved produktet af primtal; det vil sige, at alle deres faktorer er primtal. For hvis der findes en faktor, der ikke er et primtal, kan den altid faktoriseres og repræsenteres af to eller flere primtal.

Euler formulerede ikke teoremer om nedbrydningens unikke karakter, men han foreslog en lignende udtalelse, som han efterlod uden bevis, i afsnit 65 i kapitel IV i første afsnit af første del. Der forklarer Euler implicit, at faktorisering af et tal i primfaktorer er unikt, idet han siger, at alle divisorer af et tal kan findes ved at kende primfaktorerne fra faktorisering af det givne tal [17] . Dette element kan således betragtes som ækvivalent med det unikke ved faktorisering.

Denne udtalelse er oversat som følger:

Når vi indregner et tal i primfaktorer, bliver det meget nemt at finde alle dets divisorer. For vi skal først gange primfaktorerne med hinanden, og derefter gange dem parvis, tre med tre, fire med fire og så videre, indtil vi kommer til selve tallet.

"Erfaring i teorien om tal" ( fransk Essai sur la théorie des nombres , 1798) Legendre indeholder et bevis på eksistensen af nedbrydning i primfaktorer og en ejendommelig antagelse om det unikke ved denne dekomponering ved at opregne alle primdivisorer af et givet tal .

Legendres udtalelse om eksistensen af en nedbrydning lyder [18] :

Ethvert tal , der ikke er primtal, kan repræsenteres som et produkt af flere primtal osv., som hver er hævet til en bestemt potens, således kan man altid antage , osv. $N$ $\alfa ,\beta ,\gamma$ ${\displaystyle N=\alpha ^{m}\beta ^{n}\gamma ^{p))$

Påstanden relateret til det unikke ved faktorisering er givet i afsnit 10 i introduktionen, hvor Legendre havde til hensigt at finde antallet af alle divisorer af et tal og på samme tid deres sum. Det unikke er let at bevise ud fra denne påstand.

Carl Gauss (1800-tallet)

Den første nøjagtige formulering af sætningen og dens bevis er givet i Gauss' Arithmetical Investigations (1801). Udtalelsen af sætningen kan findes i afsnit 16, og dens oversættelse er som følger:

Et sammensat tal kan indregnes i primfaktorer på en unik måde.

Ansøgning

Største fælles divisor og mindst fælles multiplum

Aritmetikkens grundlæggende sætning giver elegante udtryk for GCD og LCM .

Angiv med alle de forskellige primtal, som tallene blev nedbrudt i, og de grader , hvormed de forekommer i disse nedbrydninger, som hhv . Det er klart, at de kun kan tage naturlige værdier eller nulværdier. ${p_{i}}$ $-en$ $b$ ${d_{i))$ ${d'_{i))$ ${d_{i}},{d'_{i}}$

Derefter:

{\text{gcd}}(a,b)=p_{1}^{\min\{\,d_{1},d_{1}'\,\}}\cdot p_{2}^ {\min\{\,d_{2},d_{2}'\,\}}\cdot p_{3}^{\min\{\,d_{3},d_{3}'\,\} }\cdot p_{4}^{\min\{\,d_{4},d_{4}'\,\))\cdot \ldots =\prod p_{i}^{\min\{\,d_ {i},d_{i}'\,\}};

{\text{LCD))(a,b)=p_{1}^{\max\{\,d_{1},d_{1}'\,\))\cdot p_{2}^ {\max\{\,d_{2},d_{2}'\,\}}\cdot p_{3}^{\max\{\,d_{3},d_{3}'\,\} }\cdot p_{4}^{\max\{\,d_{4},d_{4}'\,\))\cdot \ldots =\prod p_{i}^{\max\{\,d_ {i},d_{i}'\,\}}.

Divisorer af et naturligt tal

Når du kender faktoriseringen af et naturligt tal, kan du straks angive alle dets divisorer .

Vi bruger den kanoniske nedbrydning af det tal , der er angivet i begyndelsen af artiklen. De naturlige tal er ikke andet end antallet af tilsvarende primtal , der forekommer i nedbrydningen af det oprindelige tal. For at finde alle divisorer er det således tilstrækkeligt at skrive produkter med alle mulige kombinationer af primtal, varierende antallet af hver i produktet fra til $n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k)),$ ${\displaystyle d_{1},\cdots ,d_{k))$ $p_{1},...,p_{k}$ $p_{i}$ $0$ $d_{i}$

Eksempel: $N=1164=2\cdot 2\cdot 3\cdot 97=2^{2}\cdot 3^{1}\cdot 97^{1}.$

Da tallet 2 forekommer i udvidelsen 2 gange, kan det tage heltalsværdier fra 0 til 2. På samme måde tager de værdier fra 0 til 1. Således består sættet af alle divisorer af tal $d_{1}$ $d_{2}$ $d_{3}$

${\begin{aligned}{2}1,\\2,\\3,\\97,\\2\cdot 2,\\2\cdot 3,\\2\cdot 97,\\3 \cdot 97,\\2\cdot 2\cdot 3,\\2\cdot 2\cdot 97,\\2\cdot 3\cdot 97,\\2\cdot 2\cdot 3\cdot 97.\end{ aligned}}$ .

For at beregne det samlede antal divisorer skal du gange antallet af alle mulige værdier for forskellige . $d_{k}$

I dette eksempel er det samlede antal divisorer $2\cdot 2\cdot 3=12.$

Aritmetiske funktioner

Nogle aritmetiske funktioner kan beregnes ved hjælp af kanonisk primfaktorisering.

For eksempel, for Euler-funktionen af et naturligt tal, er formlen gyldig: hvor er et primtal og løber gennem alle de værdier, der er involveret i udvidelsen til primfaktorer ( bevis ). $\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,$ $s$ $n$

Faktorering af produktet af naturlige tal

Produktet af to tal kan beregnes som følger:

a\cdot b=p_{1}^{d_{1}+d_{1}'}\,p_{2}^{d_{2}+d_{2}'}\,p_{3} ^{d_{3}+d_{3}'}\,p_{4}^{d_{4}+d_{4}'}\ldots =\prod p_{i}^{d_{i}+d_{ jeg}'},

hvor er den styrke, hvormed primtallet forekommer i udvidelsen af tallet . Eksempel: ${d'_{i))$ ${p_{i}}$ $b$ $68\cdot 36=(2\cdot 2\cdot 17)\cdot (2\cdot 2\cdot 3\cdot 3)=2^{4}\cdot 3^{2}\cdot 17$

Grundlæggende sætning for aritmetik i ringe

Overvej aritmetikkens grundlæggende teorem i et mere generelt tilfælde: i normringe og i euklidiske ringe .

En ring, der har en divisionsalgoritme med en rest, kaldes en euklidisk ring. For enhver euklidisk ring kan beviset for aritmetikkens grundsætning udføres på nøjagtig samme måde som for naturlige tal.

Grundlæggende sætning for aritmetik i ringen af Gaussiske heltal

Aritmetikkens hovedsætning med en lille korrektion (nemlig det præciseres, at faktorerne ikke kun tages op til rækkefølgen, men også op til association - egenskaberne for gaussiske tal opnås fra hinanden ved at gange med divisoren af enhed : 1, i , −1 eller − i ) har plads i ringen af Gaussiske heltal . Ideen med beviset er at finde en divisionsalgoritme med en rest i en given ring af tal [19] .

Ikke-unikhed ved nedbrydning i en ring

Denne teorem gælder dog ikke for alle ringe [19] .

Overvej for eksempel komplekse tal af formen , hvor , er heltal. Summen og produktet af sådanne tal vil være tal af samme art. Så får vi en ring med norm . $a=m+in{\sqrt {5}}$ $m$ $n$ $N(a)=m^{2}+5n^{2}=|a|^{2}$

Der er to forskellige nedbrydninger for tallet 6 i denne ring: . Det er tilbage at bevise, at tallene er primtal. Lad os bevise, at tallet 2 er primtal. Lad tallet dekomponeres i primfaktorer som . Så . Og for at tallene og for at forblive primtal, er den eneste mulighed, at de er præcis 2. $6=2\cdot 3=(1-i{\sqrt {5)))(1+i{\sqrt {5)))$ $2,3,1\pm i{\sqrt {5}}$ $2$ $(m_{1}+in_{1}{\sqrt {5)))(m_{2}+in_{2}{\sqrt {5)))$ $4=|m_{1}+in_{1}{\sqrt {5}}|^{2}|m_{2}+in_{2}{\sqrt {5}}|^{2}= (m_{1}^{2}+5n_{1}^{2})(m_{2}^{2}+5n_{2}^{2})$ $m_{1}+i_{1}{\sqrt {5}}$ $m_{2}+i_{2}{\sqrt {5}}$ $m_{1}^{2}+5n_{1}^{2}$ $m_{2}^{2}+5n_{2}^{2}$

Men i den betragtede ring er der ingen tal med norm 2, derfor er en sådan nedbrydning umulig, så tallet 2 er primtal. Tal behandles på samme måde . $3.1\pm i{\sqrt {5}}$

Ringe, hvor aritmetikkens hovedsætning stadig gælder, kaldes faktorielle .

Se også

Noter

↑ Davenport, 1965 .
↑ Zhikov, 2000 , s. 112.
↑ Kaluzhnin, 1969 , s. 6-7.
↑ Weisstein, 2010 , s. 1126.
↑ Davenport, 1965 , s. 15-16.
↑ Davenport, 1965 , s. 17-18.
↑ Davenport, 1965 , s. 26-27.
↑ 1 2 A. Göksel Ağargün og E. Mehmet Özkan, 2001 , s. 207.
↑ Davenport, 1965 , s. 17.
↑ Begyndelsen af Euclid Bøger VII - X, 1949 , s. 33.
↑ Begyndelsen af Euclid Bøger VII - X, 1949 , s. 34.
↑ Begyndelsen af Euclid Bøger VII - X, 1949 , s. 83.
↑ Hendy, 1975 .
↑ Mullin, 1965 .
↑ A. Göksel Ağargün og E. Mehmet Özkan, 2001 , s. 209.
↑ A. Göksel Ağargün og E. Mehmet Özkan, 2001 , s. 211.
↑ A. Göksel Ağargün og E. Mehmet Özkan, 2001 , s. 212.
↑ A.M. Le Gendre, Essai sur la théorie des nombres , Paris, VI (1798), s. 6.
↑ 1 2 Zhikov, 2000 , s. 116.

Litteratur

Vinogradov I.M. Grundlæggende om talteori . - Statens forlag for teknisk og teoretisk litteratur, 1952. - 180 s. — 10.000 eksemplarer.
Davenport G. Højere aritmetik / udg. Yu. V. Linnik , oversættelse. B. Z. Moroz - M . : Nauka , 1965. - S. 15-38. — 176 s.
Zhikov V.V. Grundlæggende sætning for aritmetik // Soros Educational Journal . - 2000. - T. 6 , nr. 3 . - S. 112-117 .
Kaluzhnin L. A. Den grundlæggende aritmetiske sætning . — Populære Forelæsninger om Matematik . — M .: Nauka, 1969. — 32 s.
Courant R., Robbins G. Supplement til kapitel I, § 4.2 // Hvad er matematik? - MTSNMO , 2000. - 568 s.
Weisstein E. W. CRC Concise Encyclopedia of Mathematics (engelsk) - Anden udgave - Chapman og Hall London , CRC Press , 2010. - 3242 s. — ISBN 978-1-4200-3522-3
A. Göksel Ağargün og E. Mehmet Özkan. En historisk undersøgelse af aritmetikkens grundlæggende sætning // Historia Mathematica. - 2001. - Bd. 28. - S. 207-214. - doi : 10.1006/hmat.2001.2318 .
D.D. Mordukhai-Boltovskoy, I.N. Veselovsky. Euklids begyndelse. Bøger VII-X. - Statens forlag for teknisk og teoretisk litteratur, 1949. - 510 s.
MD Hendy. Euklid og aritmetikkens grundsætning . - Historia Mathematica 05/1975, 1975.
A. A. Mullin. Matematisk-filosofiske bemærkninger om nye sætninger analogt med aritmetikkens grundsætning. - Notre Dame Journal of Formal Logic, 1965.

Ordbøger og encyklopædier	Britannica (online)

Tal efter delelighedskarakteristika
Generel information	Faktorisering af heltal Delbarhed enhedsdeler Divisor funktion primtal Grundlæggende sætning for aritmetik Aritmetisk tal
Faktoriseringsformer	primtal Komposit nummer Semiprime rektangulært tal Sphenisk tal Kvadratløst tal Fuld multiple Perfekt grad Achilles nummer glat nummer Almindelig nummer groft tal usædvanligt antal
Med begrænsede divisorer	perfekt tal Lidt utilstrækkelige tal Lidt overflødige tal Multiperfekt tal Hemiperfekte tal hyperperfekt tal super perfekt nummer enhedsprimtal semiperfekt tal pararytmisk tal Erdős-Nicolas nummer
Tal med mange divisorer	Overskydende tal Primitive overskydende tal Meget overflødige tal Super redundante numre Enormt overflødige tal supersammensat tal Et meget supersammensat tal mærkeligt nummer
Relateret til aliquot -sekvenser	helligt tal venlige tal offentlige numre Kvasivenlige tal
Andet	Ikke nok tal ven tal sublimerede tal Malmtal ydmygt nummer Lige cifre ekstravagant nummer