Grundläggande sats för aritmetik

Grundsatsen för aritmetiken säger att [1] [2]

varje naturligt tal kan faktoriseras ( utvidgas ) i formen $n>1$ ${\displaystyle n=p_{1}\cdot \ldots \cdot p_{k))$ ${\displaystyle p_{1},\ldots ,p_{k))$

Om vi formellt är överens om att den tomma produkten av en tom uppsättning siffror är lika med 1, så kan villkoret i formuleringen utelämnas - då för enhet, antyds faktorisering med en tom uppsättning primtal: [3] [ 4] . $n>1$ $1=1$

Som en konsekvens kan varje naturligt tal representeras som $n$

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

var finns primtal och är några naturliga tal,

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

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

och på ett unikt sätt. Denna representation av ett tal kallas dess kanoniska faktorisering . $n$

Bevis

Enligt metoden för induktion

Existens : vi kommer att bevisa förekomsten av en faktorisering av ett tal till primtalsfaktorer, om vi antar att detsamma redan har bevisats för något annat tal mindre än . Om är prime, då är existensen bevisad. Om är sammansatt, då det kan representeras som en produkt av två tal och , som var och en är större än 1 men mindre än . Talen och är antingen primtal eller kan dekomponeras till en produkt av primtal (redan bevisat tidigare). Genom att ersätta deras sönderdelning till , får vi sönderdelningen av det ursprungliga numret till primtal. Existens är bevisad [5] . $n$ $n$ $n$ $n$ $a$ $b$ $n$ $a$ $b$ $n=a\cdot b$ $n$

Unikhet : För ett primtal är unikhet uppenbar.

För ett sammansatt tal är tanken med beviset att använda metoden "genom motsägelse" , nämligen antagandet att talet har två olika expansioner. Vi betraktar primtal och , som är de minsta i den första respektive andra av dessa expansioner, och bevisar följande lemma: $p_{0}$ $q_{0}$

om sönderdelningen av ett tal till primtalsfaktorer är unik, måste varje primtalsdelare inkluderas i denna sönderdelning. $m$ $m$

Därefter överväger vi talet , som i sin tur är ett naturligt tal och som är mindre än . Av det induktiva antagandet och ovanstående lemma följer att det är en divisor av det givna talet, varefter man på samma sätt drar slutsatsen att den första faktoriseringen är delbar med . Inget primtal kan förekomma i båda sönderdelningarna samtidigt, eftersom det annars skulle vara möjligt att reducera det och få olika sönderdelningar till primtalsfaktorer med ett tal mindre än . $n-p_{0}\cdot q_{0}$ $n$ $p_{0}\cdot q_{0}$ $q_{0}$ $n$ $n$

Använder Euklids algoritm

Man kan bevisa aritmetikens grundsats genom att använda följden från Euklids algoritm [7] :

den största gemensamma divisorn är den största gemensamma divisorn av och multiplicerad med . $n\cdot a$ $n\cdot b$ $a$ $b$ $n$

Från denna följd kan man bevisa Euklids lemma , som också är nödvändigt för att bevisa satsen:

om är ett primtal och produkten av två tal är delbar med , då är minst en av de två faktorerna delbar med . $sid$ $sid$ $sid$

Existens: Tanken bakom existensbeviset är att bevisa lemmat:

överväga ett primtal och en produkt . Om det är delbart med , men inte delbart med , då är det delbart med . $sid$ $n\cdot a$ $n\cdot a$ $sid$ $a$ $sid$ $n$ $sid$

Vidare, med användning av ovanstående lemma, sönderdelas talet sekventiellt i primtalsfaktorer, förutsatt att alla primtalsdelare för detta tal är kända.

Unikhet: låt talet n ha två olika uppdelningar till primtal:

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

Eftersom det är delbart med , då antingen , eller är delbart med . Om är delbart med , då , eftersom båda dessa tal är primtal. Om det är delbart med , så fortsätter vi det tidigare resonemanget. I slutändan kommer det att visa sig att ett av talen är lika med numret och därför sammanfaller båda expansionerna av talet faktiskt. Därmed är det unika med sönderdelningen bevisad. $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}$

Historik

Premisserna för aritmetikens grundsats har sitt ursprung i antikens Grekland . Trots det faktum att i den antika grekiska matematiken den grundläggande aritmetikens sats i den moderna formuleringen inte förekommer, i " principerna " ( annan grekiska Στοιχεῖα ) har Euklid motsvarande meningar. Efter Euklids har många matematiker under århundradena bidragit till beviset för aritmetikens grundläggande sats, med hänvisning till uttalanden som har nära betydelse i deras arbeten, bland dessa forskare är Kamal ad-Din al-Farisi , J. Preste , L Euler , A. Legendre [8] . Den första exakta formuleringen av aritmetikens grundsats och dess bevis ges av K. Gauss i boken " Arithmetical Investigations " ( lat. Disquisitiones Arithmeticae ), publicerad 1801 [9] . Sedan dess har många olika nya bevis för satsen dykt upp, som konkurrerar med varandra i skönhet och originalitet [8] .

Euklid (3:e århundradet f.Kr.)

Euklids presenterade i Elements viktiga grunder för talteorin, inklusive aritmetikens grundläggande sats. Tre meningar mycket nära aritmetikens grundläggande sats kan hittas i böckerna VII och IX, nämligen sats 30 från bok VII, mest känd som Euklids Lemma , sats 31 från bok VII och sats 14 från bok IX. Nedan är deras versioner i Morduchai-Boltovskys översättning :

VII.30:

Om två tal, multiplicerande med varandra, producerar något, och det som uppstår från dem mäts med något första tal, så kommer (det senare) också att mäta ett av de ursprungliga [10]

VII.31:

Varje sammansatt tal mäts med ett första tal [11]

IX.14:

Om talet är det minsta mätbara (givet) av de första talen, kan det inte mätas med något annat primtal, förutom de som ursprungligen mätte (det) [12]

För närvarande[ vad? ] tid, härleds beviset för aritmetikens grundsats från satser VII.30 och VII.31, men Euklid presenterade inte detta bevis i sina skrifter. Proposition IX.14 är i sin tur ganska lik påståendet om det unika med faktorisering till primtalsfaktorer, men det visade sig att detta påstående inte täcker alla möjliga fall - till exempel när minst en kvadrat av ett primtal förekommer vid nedbrytningen till primfaktorer [13] [14] .

Al-Farisi (XIV-talet)

Den berömda persiske vetenskapsmannen Kamal ad-Din al-Farisi tog ett betydande steg framåt i studiet av aritmetikens grundläggande sats. I sitt arbete Memorandum for friends on the proof of amicability bevisade han förekomsten av en faktorisering till primära faktorer och gav den nödvändiga informationen för att bevisa det unika med denna nedbrytning. Kamal al-Farisi var dock mest intresserad av att konstruera sitt eget bevis för Sabit ibn Kurras sats om sökandet efter vänliga tal - och al-Farisi försökte inte bevisa aritmetikens grundsats, utan sökte efter alla divisorer för en sammansatt nummer [15] . När han noggrant undersökte faktoriseringen av tal, formulerade och bevisade han ett påstående, som i själva verket visade sig vara ett bevis på existensen av en faktorisering av ett naturligt tal till primfaktorer.

Översatt lyder hans uttalande ungefär så här:

Varje sammansatt tal kan dekomponeras i ett ändligt antal primtalsfaktorer som det är en produkt av.

I uttalande 9 formulerade al-Farisi en princip för att bestämma alla divisorer av ett sammansatt tal: detta var precis vad han behövde för att bevisa Ibn Qurras sats. Översättningen ser ut så här:

Om ett sammansatt tal bryts ner i primtalsfaktorer som , då har det ingen divisor förutom och och produkterna av var och en av dem med var och en, produkterna av tripletter, etc., upp till produkten av alla element utan någon. $a$ $a=b\cdot c\cdot d\cdot h\cdot \ldots \cdot k\cdot l$ $a$ $ett$ $b,c,d,...,k,l$

Redan från själva formuleringen av uttalandet kan man dra slutsatsen att al-Farisi kände till det unika med nedbrytningen till primära faktorer. Dessutom är alla påståenden och fakta som ges av vetenskapsmannen för att bevisa detta påstående en nödvändig uppsättning för att bevisa det unika i aritmetikens huvudsats.

Jean Preste (1600-talet)

Resultaten publicerade av Jean Preste i boken Elements de Mathématiques (1675) bekräftar att primfaktorisering på den tiden inte betraktades som något av intresse i sig, utan som en användbar tillämpning - ett sätt att hitta divisorer för ett givet tal . Preste formulerade varken existensen eller det unika med nedbrytningen och ägnade mest uppmärksamhet åt själva sökandet efter divisorer för ett tal [16] . Trots detta tillhandahöll Preste, liksom al-Farisi, all nödvändig information för att bevisa det unika med faktorisering med hjälp av sin Corollary IX, som i sig kan anses likvärdig med faktoriseringens unika.

Följd IX:

Om talen och är primtal, då är varje divisor av ett tal antingen , eller , eller , eller en av produkterna av dessa tre tal med . Det är en av sex: . $a$ $b$ $a\cdot a\cdot b$ $a$ $a^2$ $ett$ $b$ $1,a,a\cdot a,1\cdot b,a\cdot b,a\cdot a\cdot b$

Euler och Legendre (1700-talet)

I The Complete Guide to Algebra ( tyska: Vollstandige Einleitung zur Algebra ) publicerade Leonhard Euler resultat som liknar sina föregångares. Han formulerade förekomsten av faktorisering av ett tal till primtalsfaktorer och, om några detaljer utelämnades, gav han ett partiellt bevis för detta i avsnitt 41 i kapitel IV från den första delen av bokens första avsnitt.

Dess översättning är som följer:

Alla sammansatta tal som kan faktoriseras representeras av produkten av primtal; det vill säga alla deras faktorer är primtal. För om en faktor hittas som inte är ett primtal, kan den alltid faktoriseras och representeras av två eller flera primtal.

Euler formulerade inte satser om nedbrytningens unika karaktär, men han föreslog ett liknande uttalande, som han lämnade utan bevis, i avsnitt 65 i kapitel IV i den första delen av den första delen. Där förklarar Euler implicit att faktorisering av ett tal i primtalsfaktorer är unikt, och säger att alla divisorer av ett tal kan hittas genom att känna till primtalsfaktorerna från att faktorisera det givna talet [17] . Således kan denna artikel anses likvärdig med det unika med faktorisering.

Detta uttalande översätts enligt följande:

När vi räknar in ett tal i primtalsfaktorer blir det mycket lätt att hitta alla dess divisorer. För vi måste först multiplicera primtalsfaktorerna med varandra och sedan multiplicera dem i par, tre med tre, fyra med fyra och så vidare, tills vi kommer till själva talet.

"Erfarenhet av talteorin" ( franska Essai sur la théorie des nombres , 1798) Legendre innehåller ett bevis på förekomsten av nedbrytning i primtalsfaktorer och ett märkligt antagande om det unika med denna nedbrytning genom att räkna upp alla primtalsdelare för ett givet tal .

Legendres uttalande om förekomsten av en nedbrytning lyder [18] :

Varje tal som inte är primtal kan representeras som en produkt av flera primtal , etc., som vart och ett höjs till en viss styrka, så man kan alltid anta , etc. $N$ $\alfa ,\beta ,\gamma$ ${\displaystyle N=\alpha ^{m}\beta ^{n}\gamma ^{p))$

Påståendet relaterat till det unika med faktorisering ges i avsnitt 10 i inledningen, där Legendre avsåg att hitta numret på alla divisorer för ett tal och samtidigt deras summa. Det unika är lätt att bevisa från detta påstående.

Carl Gauss (1800-talet)

Den första exakta formuleringen av satsen och dess bevis ges i Gauss' Arithmetical Investigations (1801). Uttalandet av satsen finns i stycke 16, och dess översättning är som följer:

Ett sammansatt tal kan faktoriseras till primfaktorer på ett unikt sätt.

Applikation

Största gemensamma divisor och minsta gemensamma multipel

The Fundamental Theorem of Arithmetic ger eleganta uttryck för GCD och LCM .

Beteckna med alla de olika primtal som talen sönderdelades i, och de grader med vilka de förekommer i dessa sönderdelningar, som resp . Det är tydligt att de bara kan ta naturliga eller nollvärden. ${pi}}$ $a$ $b$ ${d_{i))$ ${d'_{i))$ ${d_{i}},{d'_{i}}$

Sedan:

{\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}'\,\}}.

Delare av ett naturligt tal

Genom att känna till faktoriseringen av ett naturligt tal kan du omedelbart ange alla dess divisorer .

Vi använder den kanoniska uppdelningen av numret som anges i början av artikeln. De naturliga talen är inget annat än antalet motsvarande primtal som förekommer vid nedbrytningen av det ursprungliga talet. För att hitta alla divisorer räcker det alltså att skriva produkter med alla möjliga kombinationer av primtal, varierande antalet av varje i produkten från till $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}$ $pi}$ $0$ $d_{i}$

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

Eftersom talet 2 förekommer i expansionen 2 gånger, kan det ta heltalsvärden från 0 till 2. På samma sätt tar de värden från 0 till 1. Således består mängden av alla divisorer av tal $d_{1}$ $d_{2}$ $d_{3}$

${\begin{alignedat}{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}}$ .

För att beräkna det totala antalet divisorer måste du multiplicera antalet av alla möjliga värden för olika . $d_{k}$

I det här exemplet är det totala antalet divisorer $2\cdot 2\cdot 3=12.$

Aritmetiska funktioner

Vissa aritmetiska funktioner kan beräknas med kanonisk primtalsfaktorisering.

Till exempel, för Euler-funktionen för ett naturligt tal, är formeln giltig: där är ett primtal och går igenom alla värden som är involverade i expansionen till primtalsfaktorer ( bevis ). $\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,$ $sid$ $n$

Faktorering av produkten av naturliga tal

Produkten av två tal kan beräknas enligt följande:

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_{ i}'},

var är kraften med vilken primtalet förekommer i talets expansion . Exempel: ${d'_{i))$ ${pi}}$ $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äggande sats för aritmetik i ringar

Betrakta aritmetikens grundläggande sats i ett mer allmänt fall: i normringar och i euklidiska ringar .

En ring som har en divisionsalgoritm med en rest kallas en euklidisk ring. För vilken euklidisk ring som helst kan beviset för aritmetikens grundsats utföras på exakt samma sätt som för naturliga tal.

Grundläggande sats för aritmetik i ringen av Gaussiska heltal

Aritmetikens huvudsats med en liten korrigering (det förtydligas nämligen att faktorerna inte bara tas upp till följdordningen utan också upp till association - egenskaperna hos gaussiska tal erhålls från varandra genom att multiplicera med divisorn av enhet : 1, i , −1 eller − i ) har plats i ringen av Gaussiska heltal . Tanken med beviset är att hitta en divisionsalgoritm med en rest i en given ring av tal [19] .

Icke-unikhet av nedbrytning i en ring

Detta teorem gäller dock inte alla ringar [19] .

Betrakta till exempel komplexa tal av formen , där , är heltal. Summan och produkten av sådana tal kommer att vara tal av samma slag. Då får vi en ring med norm . $a=m+in{\sqrt {5}}$ $m$ $n$ ${\displaystyle N(a)=m^{2}+5n^{2}=|a|^{2))$

Det finns två olika nedbrytningar för siffran 6 i denna ring: . Det återstår att bevisa att talen är primtal. Låt oss bevisa att talet 2 är primtal. Låt numret delas upp i primtalsfaktorer som . Sedan . Och för att talen ska förbli primtal är det enda alternativet att de ska vara exakt 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}+in_{1}{\sqrt {5))$ $m_{2}+in_{2}{\sqrt {5))$ ${\displaystyle m_{1}^{2}+5n_{1}^{2))$ ${\displaystyle m_{2}^{2}+5n_{2}^{2))$

Men i den aktuella ringen finns inga tal med norm 2, därför är en sådan sönderdelning omöjlig, så talet 2 är primtal. Siffror behandlas på samma sätt . $3.1\pm i{\sqrt {5}}$

Ringar där aritmetikens huvudsats fortfarande gäller kallas faktoriella .

Se även

Anteckningar

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

Litteratur

Vinogradov I.M. Grunderna i talteorin . - Statens förlag för teknisk och teoretisk litteratur, 1952. - 180 sid. — 10 000 exemplar.
Davenport G. Högre aritmetik / ed. Yu. V. Linnik , övers. B. Z. Moroz - M . : Nauka , 1965. - S. 15-38. — 176 sid.
Zhikov V.V. Fundamental theorem of aritmetic // Soros Educational Journal . - 2000. - T. 6 , nr 3 . - S. 112-117 .
Kaluzhnin L. A. Grundsatsen för aritmetiken . — Populära föreläsningar i matematik . — M .: Nauka, 1969. — 32 sid.
Courant R., Robbins G. Tillägg till kapitel I, § 4.2 // Vad är matematik? - MTSNMO , 2000. - 568 sid.
Weisstein E. W. CRC Concise Encyclopedia of Mathematics (engelska) - Andra upplagan - Chapman and Hall London , CRC Press , 2010. - 3242 sid. — ISBN 978-1-4200-3522-3
A. Göksel Ağargün och E. Mehmet Özkan. A Historical Survey of the Fundamental Theorem of Arithmetic // Historia Mathematica. - 2001. - Vol. 28. - S. 207-214. - doi : 10.1006/hmat.2001.2318 .
D.D. Mordukhai-Boltovskoy, I.N. Veselovsky. Euklids början. Böcker VII-X. - Statens förlag för teknisk och teoretisk litteratur, 1949. - 510 sid.
MD Hendy. Euklids och aritmetikens grundsats . - Historia Mathematica 05/1975, 1975.
A.A. Mullin. Matematisk-filosofiska anmärkningar om nya satser analoga med aritmetikens grundsats. — Notre Dame Journal of Formal Logic, 1965.

Ordböcker och uppslagsverk	Britannica (online)

Tal efter delbarhetsegenskaper
Allmän information	Faktorisering av heltal Delbarhet enhetsdelare Delningsfunktion primtal Grundläggande sats för aritmetik Aritmetiskt tal
Faktoriseringsformer	primtal Sammansatt tal Semiprime rektangulärt tal Sfeniskt tal Kvadratlöst tal Full multipel Perfekt examen Achilles nummer jämnt antal Vanligt nummer grovt antal ovanligt antal
Med begränsade delare	perfekt nummer Lite otillräckliga siffror Lite överflödiga siffror Multiperfekt nummer Hemiperfekta siffror hyperperfekt siffra super perfekt nummer enhetligt primtal semiperfekt nummer pararytmiskt tal Erdős-Nicolas nummer
Tal med många delare	Överskjutande siffror Primitiva överskottstal Mycket redundanta nummer Superredundanta nummer Enormt överflödiga siffror superkompositnummer Ett mycket supersammansatt tal konstigt nummer
Relaterat till alikvotsekvenser	heligt nummer vänliga siffror offentliga nummer Kvasivänliga siffror
Övrig	Inte tillräckligt med siffror kompisnummer sublimerade tal Malmnummer ödmjukt nummer Lika siffror extravagant nummer