Getaltheorie
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b0/Ulam_Spiral_Divisors_100000.png/260px-Ulam_Spiral_Divisors_100000.png)
Deel van een serie artikelen over Wiskunde | ||||
---|---|---|---|---|
![]() | ||||
Formules van een stochastisch proces | ||||
Kwantiteit | ||||
Complex getal · Geheel getal · Natuurlijk getal · Oneindigheid · Reëel getal · Rekenkunde | ||||
Structuur en ruimte | ||||
Algebra · Functie · Getaltheorie · Goniometrie · Groepentheorie · Meetkunde · Topologie | ||||
Verandering | ||||
Analyse · Chaostheorie · Differentiaalrekening · Dynamische systemen · Vectoren | ||||
Toegepaste wiskunde | ||||
Discrete wiskunde · Grafentheorie · Informatietheorie · Kansrekening · Statistiek · Wiskundige natuurkunde | ||||
|
Traditioneel is getaltheorie de tak van de zuivere wiskunde die de eigenschappen van de gehele getallen bestudeert. In de getaltheorie is zowel zuiver theoretisch onderzoek mogelijk, als onderzoek naar toepassingen in bijvoorbeeld de cryptografie.
Getaltheorie kan worden onderverdeeld in verschillende gebieden, afhankelijk van de gebruikte methoden en de onderzochte vraagstelling. Deze worden hieronder besproken.
Elementaire getaltheorie
In de elementaire getaltheorie worden de gehele getallen bestudeerd zonder gebruik te maken van structuren (ringen en deellichamen) in het lichaam der complexe getallen. Vragen die hieronder vallen zijn de deelbaarheid van getallen, het euclidische algoritme om de grootste gemene deler te berekenen, het ontbinden van getallen in priemfactoren, de hoofdstelling van de rekenkunde en het onderzoek van perfecte getallen.
Bij modulair rekenen wordt het resultaat van de rekenkundige bewerkingen optelling, aftrekking en vermenigvuldiging steeds herleid tot de rest bij deling door een gegeven vast natuurlijk getal , de modulus. De aldus ontstane restklassen vormen een commutatieve ring. Een aantal elementaire stellingen volgen uit het feit dat de inverteerbare elementen van deze ring een eindige abelse groep vormen voor de vermenigvuldiging. Het aantal elementen van deze zogenaamde groep der eenheden is de indicator of het totiënt van .
Typische beweringen zijn de kleine stelling van Fermat, de stelling van Euler, de Chinese reststelling en de wet van de kwadratische reciprociteit. De eigenschappen van multiplicatieve functies zoals de möbiusfunctie en eulerfunctie worden onderzocht. Eveneens worden rijen van gehele getallen onderzocht zoals de rij van Fibonacci.
De stelling van Bachet-Bézout garandeert dat de grootste gemene deler van twee gehele getallen en , beide verschillend van 0, kan geschreven worden als een lineaire combinatie van en :
Veel vragen in de elementaire getaltheorie zijn uitzonderlijk moeilijk. Het beantwoorden vereist een volledig nieuwe aanpak. Het heeft bijvoorbeeld 350 jaar geduurd voordat de laatste stelling van Fermat in 1994 bewezen werd, door Andrew Wiles. De laatste stelling van Fermat (geformuleerd in 1637, bewezen in 1994) betreft de onmogelijkheid van het vinden van drie gehele getallen en , elk ongelijk aan 0, zodanig dat geldt voor enig geheel getal groter dan 2. Het bewijs hiervan is zeer ingewikkeld en wordt daarom in leerboeken over getaltheorie niet behandeld.
Voorbeelden van onopgeloste vraagstukken zijn:
- het vermoeden van Goldbach: elk even getal groter dan 2 kan geschreven worden als som van twee priemgetallen
- de vraag naar priemtweelingen: zijn er oneindig veel priemgetallenparen waarbij de twee priemgetallen slechts 2 verschillen?
- het vermoeden van Collatz, een simpele iteratie
In 2002 werd een ander beroemd vraagstuk met betrekking tot opeenvolgende geheeltallige machten, het vermoeden van Catalan, opgelost. Dit is nu bekend als de stelling van Mihăilescu.
De theorie van diofantische vergelijkingen is bewezen onbeslisbaar te zijn. (Zie ook Hilberts tiende probleem.)
Analytische getaltheorie
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/1rightarrow_blue.svg/15px-1rightarrow_blue.svg.png)
De analytische getaltheorie gebruikt het instrumentarium van de analyse en functietheorie om eigenschappen van gehele getallen te onderzoeken. De priemgetalstelling en de eraan verwante Riemann-hypothese zijn hier voorbeelden van. Veel problemen uit de elementaire getaltheorie worden met methoden uit de analytische getaltheorie aangepakt. Voorbeelden zijn het probleem van Waring, de bovengenoemde vraag naar tweelingpriemgetallen en het vermoeden van Goldbach. Vraagstukken over transcendentie van getallen als van π en e (grondtal van de natuurlijke logaritme) vallen ook onder de analytische getaltheorie. (Merk overigens op dat het in het laatste voorbeeld niet meer over de eenvoudige natuurlijke getallen gaat.)
Algebraïsche getaltheorie
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/1rightarrow_blue.svg/15px-1rightarrow_blue.svg.png)
In de algebraïsche getaltheorie wordt het begrip getal uitgebreid met de algebraïsche getallen, dat zijn de nulpunten van polynomen met rationale coëfficiënten.
Een nuttig procedé in de algebraïsche getaltheorie is lokalisatie naar een priemgetal . Daarbij wordt het lichaam van de -adische getallen gevormd door vervollediging van de rationale getallen naar een bijzondere metriek, de-adische norm.
Meetkundige getaltheorie
De meetkundige getaltheorie omvat alle vormen van meetkunde. Het begint met de stelling van Minkowski over roosterpunten in convexe verzamelingen. De beroemde stelling van Fermat werd met deze technieken bewezen.
Numerieke getaltheorie
Ten slotte is er de numerieke getaltheorie, die onderzoek doet naar snelle algoritmen voor het testen van priemgetallen en het ontbinden in factoren. Deze studie heeft belangrijke toepassingen in de cryptografie.
Geschiedenis
Griekse getaltheorie
Getaltheorie was in Alexandrië (Egypte) een favoriet onderzoeksgebied onder Oud-Griekse wiskundigen uit de laat-hellenistische periode (3e eeuw n.Chr.). Zij waren zich in tal van bijzondere gevallen bewust van het concept van diofantische vergelijkingen. De eerste Griekse wiskundige die dit type vergelijkingen bestudeerde was Diophantus.
Diophantus zocht ook naar een methode voor het vinden van geheeltallige oplossingen voor lineaire onbepaalde vergelijkingen, vergelijkingen die voldoende informatie missen om een enkele discrete verzameling van antwoorden te produceren. De vergelijking is een dergelijke vergelijking. Diophantus ontdekte dat veel onbepaalde vergelijkingen tot een vorm gereduceerd kunnen worden, waar een zekere categorie van de antwoorden bekend is, hoewel een specifiek antwoord dat niet is.
Klassieke Indiase getaltheorie
Diofantische vergelijkingen werden daarna door wiskundigen in het middeleeuwse India uitgebreid bestudeerd. Zij waren de eersten die systematisch methoden onderzochten voor de bepaling van volledige oplossing van diofantische vergelijkingen. Aryabhata gaf in zijn verhandeling Aryabhatiya (499) de eerste expliciete beschrijving van de algemene volledige oplossing van de lineaire diofantische vergelijking . Dit kuttaka algoritme geldt als de belangrijkste bijdrage van Aryabhata in de zuivere wiskunde. Aryabhata vond deze oplossingen voor diofantische vergelijkingen door gebruik te maken van kettingbreuken. Deze techniek werd door Aryabhata toegepast om integrale oplossingen te vinden voor simultane lineaire diofantische vergelijkingen, een probleem met belangrijke toepassingen in de sterrenkunde. Met behulp van deze methode vond hij ook de algemene oplossing voor de onbepaalde lineaire vergelijking.
In 628 behandelde Brahmagupta moeilijkere diofantische vergelijkingen. Hij gebruikte de Chakravala-methode om kwadratische diofantische vergelijkingen op te lossen, met inbegrip van vormen van de vergelijking van Pell, zoals
Zijn Brahmasphuta-siddhanta werd in 773 in het Arabisch vertaald. In 1126 volgde een vertaling in het Latijn. Dezelfde vergelijking werd zo'n duizend jaar later, in 1657, opnieuw als een probleem geponeerd door de Franse wiskundige Pierre de Fermat.
De algemene oplossing voor deze specifieke vorm van de vergelijking Pell werd meer dan 70 jaar later gevonden door Leonhard Euler, terwijl de algemene oplossing voor de vergelijking van Pell in 1767 door Joseph-Louis Lagrange werd gevonden. Ondertussen was de algemene oplossing van de vergelijking van Pell ook al in 1150 gevonden door Bhāskara II. Deze Indiase wiskundige gebruikte een aangepaste versie van de Chakravala-methode van Brahmagupta. Hij gebruikte deze methode ook om de algemene oplossing voor andere onbepaalde kwadratische vergelijkingen en kwadratische diofantische vergelijkingen te vinden.
Bhaskara's Chakravala-methode voor het vinden van de algemene oplossing van de vergelijking Pell was veel eenvoudiger dan de methode die 600 jaar later door Lagrange gebruikt zou worden. Bhaskara vond ook oplossingen voor andere onbepaalde kwadratische-, derdegraads-, vierdegraadsvergelijkingen. De Chakravala-methode werd verder verbeterd door Narayana Pandit.
Islamitische getaltheorie
Vanaf de 9e eeuw vertoonden islamitische wiskundigen een grote interesse in de getaltheorie. De eerste van deze wiskundigen was Thabit ibn Qurra, die een algoritme ontdekte, waardoor men paren van bevriende getallen kon vinden, dat zijn twee getallen, zodanig dat elk getal de som is van de echte delers van het andere getal. In de 10e eeuw bekeek Ibn Tahir al-Baghdadi een licht afwijkende variant van de methode van Thabit ibn Qurra.
In de 10e eeuw lijkt Alhazen de eerste te zijn geweest die een poging heeft gedaan om alle even perfecte getallen (getallen gelijk aan de som van hun echte delers) te classificeren als die van de vorm
- , waar een priemgetal is.
Alhazen is ook de eerste persoon die de stelling van Wilson opstelde, namelijk dat als p een priemgetal is dat dan deelbaar is door . Men noemt deze stelling de stelling van Wilson als gevolg van een opmerking, die in 1770 werd gemaakt door Edward Waring, dat John Wilson het resultaat had opgemerkt. Er is echter geen bewijs dat Wilson wist hoe deze stelling te bewijzen. In 1771 gaf Lagrange het bewijs als eerste.
Bevriende getallen hebben een grote rol in de islamitische wiskunde gespeeld. In de 13e eeuw gaf de Perzische wiskundige al-Farisi een nieuw bewijs van de stelling van Thabit ibn Qurra. Hierbij introduceerde hij belangrijke nieuwe ideeën over het ontbinden van getallen in priemfactoren en combinatorische methoden. Hij gaf ook het paar bevriende getallen 17296, 18416, die zijn toegeschreven aan Euler, maar we weten dat dit paar al eerder bekend was dan ten tijde van al-Farisi, misschien zelfs aan Thabit ibn Qurra zelf. In de 17e eeuw gaf Mohammed Baqir Yazdi, lang voor Euler, het paar bevriende getallen 9.363.584 en 9.437.056.
Vroege Europese getaltheorie
In de 13e eeuw schreef Leonardo de Pisa, beter bekend als Fibonacci, de Liber Quadratorum. In dit werk behandelde hij de pythagorese drietallen en merkte op dat kwadratische getallen kunnen worden geschreven als sommen van oneven getallen. Hij definieerde een congruum, een getal van de vorm als even is en 4 keer zoveel als oneven is. Fibonacci bewees dat een congruum deelbaar moet zijn door 24. Hij bewees ook dat een kwadraat geen congruum kan zijn. Zijn bijdragen aan de getaltheorie waren zo groot, dat wordt gezegd dat
het Liber quadratorum op zich Fibonacci al de belangrijkste bijdrager aan de getaltheorie maakt tussen Diophantus en de 17de-eeuwse Franse wiskundige Pierre de Fermat.[1]
Verdere vooruitgang in de getaltheorie vond plaats in de 16e en 17e eeuw door wiskundigen als Viète, Bachet de Méziriac en vooral Pierre de Fermat. Pierre de Fermat kon met de methode om een stelling met behulp van oneindige afdaling te bewijzen voor het eerst verschillende diofantische vergelijkingen bewijzen. Vooral zijn laatste stelling werd bekend, die hij in 1637 heeft geponeerd. Er werd voor die laatste stelling pas in 1994 een bewijs gevonden. Fermat bewees dat de vergelijking altijd een oplossing heeft, behalve wanneer een kwadraat is. In de achttiende eeuw leverden Euler en Lagrange belangrijke bijdragen aan de getaltheorie. Euler deed werk aan de analytische getaltheorie en vond een algemene oplossing van de vergelijking . Euler en Lagrange losten de meer algemene vergelijkingen van Pell op door gebruik te maken van kettingbreuken.
Begin van de moderne getaltheorie
Rond het begin van de negentiende-eeuwse formuleerden Legendre (1798) en Gauss in hun beider boeken de eerste systematische theorieën in Europa. Gauss zijn Disquisitiones arithmeticae (1801) wordt algemeen als het startpunt van de moderne getaltheorie beschouwd.
De theorie van de congruenties begint met Gauss' Disquisitiones. Hij introduceerde de notatie
en bracht een groot deel van het onderzoeksgebied in kaart. Tsjebysjev publiceerde in 1847 over dit onderwerp een werk in het Russisch, dat in gepopulariseerde vorm door Serret in Frankrijk onder de aandacht werd gebracht.
Naast een samenvatting van eerder werk formuleerde Legendre de wet van de kwadratische reciprociteit. Deze wet werd al genoemd door Euler. Legendre bewees deze stelling voor speciale gevallen voor het eerst in zijn Théorie des nombres (1798). Onafhankelijk van Euler en Legendre ontdekte Gauss ontdekte deze wet rond 1795. Hij was ook de eerste die een algemeen bewijs gaf.
De volgende wiskundige hebben ook bijgedragen aan het onderwerp: Cauchy, Dirichlet, wiens Vorlesungen über Zahlentheorie een klassieker is; Jacobi, die het Jacobi-symbool introduceerde, Liouville, Zeller, Eisenstein, Kummer en Kronecker. De getaltheorie strekte zich dankzij Gauss, Jacobi, die als eerste de wet van de kubieke wederkerigheid bewees, en Kummer uit tot onder meer derdegraads- en vierdegraads reciprociteit.
Aan Gauss hebben wij ook de weergave van getallen als binaire kwadratische vormen te danken.
Priemgetaltheorie
Een terugkerend thema en productief thema in de getaltheorie is de studie van de verdeling van priemgetallen. Gauss poneerde nog in zijn tienerjaren een asymptotische regel voor een dergelijke verdeling (de zogenaamde priemgetalstelling).
Dirichlet bewees in 1837 dat elke in aanmerking komende rekenkundige progressie oneindig veel priemgetallen bevat. Chebyshev gaf in 1850 bruikbare grenzen voor het aantal priemgetallen tussen twee gegeven limieten. Riemann introduceerde de complexe analyse in zijn theorie van de Riemann-zèta-functie. Dit leidde tot een relatie tussen de nulpunten van de zèta-functie en de verdeling van de priemgetallen, en leidde uiteindelijk tot een onafhankelijk bewijs in 1896 van de priemgetalstelling door zowel Hadamard als de la Vallée Poussin. Een elementair bewijs werd in 1949 gegeven door Erdős en Selberg. In deze context betekent elementair dat er geen gebruik wordt gemaakt van de technieken van de complexe analyse, maar het bewijs is nog steeds zeer ingenieus en moeilijk. De Riemann-hypothese, die veel definitieve antwoorden zou kunnen geven blijft, nog steeds een open vraag.
Negentiende-eeuwse ontwikkelingen
Cauchy, Poinsot (1845) en met name Hermite hebben in de 19e-eeuw veel bijgedragen aan de getaltheorie. In de theorie van ternaire vormen was Eisenstein leidend en aan hem en H.J.S. Smith is ook een opmerkelijke vooruitgang in de theorie van vormen in het algemeen te danken. Smith gaf een volledige classificatie van ternaire kwadratische vormen, en breidde Gauss' onderzoekingen over reële kwadratische vormen uit naar complexe vormen. De onderzoekingen met betrekking tot de representatie van getallen door sommen van 4, 5, 6, 7 of 8 kwadraten werden uitgebreid door Eisenstein en de theorie werd door Smith gecompleteerd.
Dirichlet was de eerste die over het onderwerp colleges gaf aan een Duitse universiteit. Onder zijn bijdragen is het bewijs van de laatste stelling van Fermat:
voor de gevallen en . Euler en Legendre hadden de gevallen en en daarmee ook alle veelvouden van 3 en 4 al bewezen.
In Nederland droeg Stieltjes bij aan de getaltheorie. Onder de latere Franse schrijvers waren Borel, Poincaré, wier verhandelingen talrijk en waardevol zijn en Tannery. Onder de leidende bijdragers in Duitsland waren Kronecker, Kummer, Schering, Bachmann en Dedekind. In Oostenrijk waren Stolz' Vorlesungen über allgemeine Arithmetik (1885-1886) en in Engeland Mathews' Theory of Numbers (deel I, 1892) wetenschappelijke algemene werken. Genocchi, Sylvester en Glaisher droegen in deze periode ook bij aan de getaltheorie.
Laat-19e-eeuwse en vroeg-20e-eeuwse ontwikkelingen
Dit was een tijd van grote vooruitgang in de getaltheorie. Opvallende zaken waren het werk van Thue over diofantische vergelijkingen, het werk van Hilbert in de algebraïsche getaltheorie, de oplossing van het probleem van Waring, de constructie van de meetkundige getaltheorie door Minkowski; daarnaast was de vooruitgang ook te danken aan Hurwitz, Voronoi, Sierpiński, Lehmer en vele anderen.
20e-eeuwse ontwikkelingen
Belangrijke figuren in de twintigste-eeuwse getaltheorie waren onder andere Weyl, Chebotaryov, Artin, Hecke, Hasse, Gelfond, Linnik, Erdős, Faltings, Hardy, Landau, Mordell, Littlewood, Niven, Srinivasa Ramanujan, Weil, Vinogradov, Selberg, Siegel, Shafarevich, Tate, Langlands, Shimura, Iwasawa, Serre, Deligne, Bombieri, Baker, Swinnerton-Dyer, Birch, Drinfel'd, Lafforgue, Wiles en Taylor.
Mijlpalen in de twintigste-eeuwse getaltheorie omvatten:
- De ontwikkeling van de klassenveldtheorie en de voltooiing ervan door Teiji Takagi, Artin, Furtwängler in de jaren 1920 en uitbreidingen en herformuleringen van de klassenveldtheorie door Hasse en Chevalley in de jaren 1930.
- De vermoedens van Weil geïntroduceerd door Weil in de jaren 1940 en het bewijs daarvan in het werk van onder andere Dwork, Grothendieck, Deligne.
- De stelling van Barban in 1961 en de verfijning daarvan in 1965, de stelling van Bombieri-Vinogradov.
- De formulering van het Langlands-programma door Robert Langlands in de late jaren 1960 en de daaropvolgende vooruitgang door vele wiskundigen.
- De stelling van Chen werd in 1966 geformuleerd en in 1973 bewezen.
- Het bewijs van de laatste stelling van Fermat door Andrew Wiles en het bewijs van de volledige stelling van Shimura-Taniyama in 1999 door Breuil, Conrad, Diamond en Taylor.
Opmerkelijke hedendaags werk, nieuwe resultaten die werden bewezen in het eerste decennium van de 21e eeuw, kwam van Clozel, Taylor, Harris, Shepherd-Barron en anderen over het vermoeden van Sato-Tate, de resultaten van Green, Tao, Ziegler en van vele anderen over lineaire vormen in de priemgetallen, op basis van werk door Gowers en nog de stelling van Goldston, Pintz en Yildirim over kleine verschillen tussen priemgetallen.
Toegepaste getaltheorie
In het boek Number theory for computing[2] staat dat de getaltheorie wordt toegepast in de: "natuurkunde, scheikunde, biologie, informatica, techniek, codering en cryptografie, willekeurig getalgeneratie, akoestiek, communicatie, grafische vormgeving en zelfs muziek en het bedrijfsleven." Er staat ook in dat Shiing-Shen Chern de "getaltheorie beschouwt als een tak van de toegepaste wiskunde vanwege de sterke toepasbaarheid ervan in andere gebieden."
Publieke-sleutel cryptografie
Veel publieke-sleutel cryptografie schema's maken gebruik van de getaltheorie bijvoorbeeld het RSA cryptosysteem en de elliptische krommen.
Residu getalsystemen
Een residu getalsysteem (RGS) representeert een groot geheel getal door gebruik te maken van een verzameling van kleinere getallen, zodat de berekening efficiënter kan worden uitgevoerd. Het RGS maakt gebruik van de Chinese reststelling uit het modulair rekenen. Het RGS heeft toepassingen in het gebied van het digitale computerrekenen. Door een groot geheel getal in een verzameling van kleinere gehele getallen te ontbinden, kan een grote berekening als een reeks van kleinere berekeningen worden uitgevoerd, die onafhankelijk en parallel kunnen worden uitgevoerd.
Zie ook
Voetnoten
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/25px-Commons-logo.svg.png)