Het artikel bespreekt de concepten van priemgetallen en samengestelde getallen. Definities van dergelijke getallen worden gegeven met voorbeelden. Wij leveren het bewijs dat de hoeveelheid priemgetallen onbeperkt en schrijf in de tabel met priemgetallen met behulp van de methode van Eratosthenes. Er zal bewijs worden geleverd om te bepalen of een getal een priemgetal of een samengesteld getal is.
Yandex.RTB R-A-339285-1
Priemgetallen en samengestelde getallen - Definities en voorbeelden
Priemgetallen en samengestelde getallen worden geclassificeerd als positieve gehele getallen. Ze moeten groter zijn dan één. Delers zijn ook onderverdeeld in eenvoudig en samengesteld. Om het concept van samengestelde getallen te begrijpen, moet je eerst de concepten van delers en veelvouden bestuderen.
Definitie 1
Priemgetallen zijn gehele getallen die groter zijn dan één en twee positieve delers hebben, dat wil zeggen zichzelf en 1.
Definitie 2
Samengestelde getallen zijn gehele getallen die groter zijn dan één en minstens drie positieve delers hebben.
Eén is noch een priemgetal, noch een samengesteld getal. Het heeft slechts één positieve deler en is dus anders dan alle andere positieve getallen. Alle positieve gehele getallen worden natuurlijke getallen genoemd, dat wil zeggen dat ze bij het tellen worden gebruikt.
Definitie 3
priemgetallen zijn natuurlijke getallen die slechts twee positieve delers hebben.
Definitie 4
Samengesteld nummer- Dit natuurlijk nummer, met meer dan twee positieve delers.
Elk getal dat groter is dan 1 is een priemgetal of een samengesteld getal. Uit de eigenschap van deelbaarheid weten we dat 1 en het getal a altijd delers zullen zijn voor elk getal a, dat wil zeggen dat het door zichzelf en door 1 deelbaar zal zijn. Laten we een definitie van gehele getallen geven.
Definitie 5
Natuurlijke getallen die geen priemgetallen zijn, worden samengestelde getallen genoemd.
Priemgetallen: 2, 3, 11, 17, 131, 523. Ze zijn alleen deelbaar door zichzelf en 1. Samengestelde nummers: 6, 63, 121, 6697. Dat wil zeggen, het getal 6 kan worden ontleed in 2 en 3, en 63 in 1, 3, 7, 9, 21, 63 en 121 in 11, 11, dat wil zeggen dat de delers 1, 11, 121 zijn. Het getal 6697 wordt ontleed in 37 en 181. Merk op dat de concepten van priemgetallen en coprime-getallen verschillende concepten zijn.
Om het gemakkelijker te maken priemgetallen te gebruiken, moet je een tabel gebruiken:
Een tabel voor alle bestaande natuurlijke getallen is onrealistisch, aangezien er oneindig veel zijn. Wanneer getallen een grootte van 10.000 of 1000000000 bereiken, kunt u overwegen de Zeef van Eratosthenes te gebruiken.
Laten we eens kijken naar de stelling die de laatste bewering verklaart.
Stelling 1
De kleinste positieve deler anders dan 1 van een natuurlijk getal groter dan één is een priemgetal.
Bewijs 1
Laten we aannemen dat a een natuurlijk getal is dat groter is dan 1, waarbij b de kleinste niet-één deler van a is. Het is noodzakelijk om te bewijzen dat b een priemgetal is met behulp van de methode van tegenspraak.
Laten we aannemen dat b een samengesteld getal is. Hieruit blijkt dat er een deler is voor b, die zowel verschilt van 1 als van b. Zo’n deler wordt aangeduid als b 1. Het is noodzakelijk dat voorwaarde 1< b 1 < b werd voltooid.
Uit de voorwaarde blijkt duidelijk dat a gedeeld wordt door b, b gedeeld wordt door b 1, wat betekent dat het concept van deelbaarheid als volgt wordt uitgedrukt: a = bq en b = b 1 · q 1 , vanwaar a = b 1 · (q 1 · q) , waarbij q en k 1 zijn gehele getallen. Volgens de regel van de vermenigvuldiging van gehele getallen geldt dat het product van gehele getallen een geheel getal is met een gelijkheid van de vorm a = b 1 · (q 1 · q) . Het blijkt dat b1 is de deler van het getal a. Ongelijkheid 1< b 1 < b Niet komt overeen, omdat we vinden dat b de kleinste positieve en niet-1 deler van a is.
Stelling 2
Er zijn een oneindig aantal priemgetallen.
Bewijs 2
Vermoedelijk nemen we een eindig aantal natuurlijke getallen n en duiden deze aan als p 1, p 2, …, p n. Laten we eens kijken naar de mogelijkheid om een ander priemgetal te vinden dan aangegeven.
Laten we het getal p in beschouwing nemen, dat gelijk is aan p 1, p 2, ..., p n + 1. Het is niet gelijk aan elk van de getallen die overeenkomen met priemgetallen van de vorm p 1, p 2, ..., p n. Het getal p is een priemgetal. Dan wordt de stelling als bewezen beschouwd. Als het samengesteld is, moet je de notatie p n + 1 nemen en laat zien dat de deler niet samenvalt met p 1, p 2, ..., p n.
Als dit niet zo zou zijn, dan, op basis van de deelbaarheidseigenschap van het product p 1, p 2, ..., p n , we vinden dat het deelbaar zou zijn door pn + 1. Merk op dat de uitdrukking p n + 1 het delen van het getal p is gelijk aan de som p 1, p 2, ..., p n + 1. We verkrijgen dat de uitdrukking p n + 1 De tweede term van deze som, die gelijk is aan 1, moet worden gedeeld, maar dit is onmogelijk.
Het is duidelijk dat elk priemgetal kan worden gevonden onder een willekeurig aantal gegeven priemgetallen. Hieruit volgt dat er oneindig veel priemgetallen zijn.
Omdat er veel priemgetallen zijn, zijn de tabellen beperkt tot de getallen 100, 1000, 10000, enzovoort.
Wanneer u een tabel met priemgetallen samenstelt, moet u er rekening mee houden dat een dergelijke taak een opeenvolgende controle van getallen vereist, beginnend bij 2 tot 100. Als er geen deler is, wordt deze in de tabel vastgelegd; als deze samengesteld is, wordt deze niet in de tabel ingevoerd.
Laten we het stap voor stap bekijken.
Als je met het getal 2 begint, heeft dit slechts 2 delers: 2 en 1, wat betekent dat het in de tabel kan worden ingevoerd. Hetzelfde met nummer 3. Het getal 4 is samengesteld; het moet worden ontleed in 2 en 2. Het getal 5 is een priemgetal, wat betekent dat het in de tabel kan worden opgenomen. Doe dit tot het getal 100.
Deze methode is lastig en tijdrovend. Je kunt een tafel maken, maar je zult moeten uitgeven een groot aantal van tijd. Het is noodzakelijk om deelbaarheidscriteria te gebruiken, die het proces van het vinden van delers zullen versnellen.
De methode waarbij de zeef van Eratosthenes wordt gebruikt, wordt als het handigst beschouwd. Laten we als voorbeeld de onderstaande tabellen bekijken. Om te beginnen worden de getallen 2, 3, 4, ..., 50 opgeschreven.
Nu moet je alle getallen die een veelvoud van 2 zijn, doorstrepen. Voer opeenvolgende doorhalingen uit. We krijgen een tabel als:
We gaan verder met het doorstrepen van getallen die een veelvoud van 5 zijn. We krijgen:
Streep getallen door die een veelvoud zijn van 7, 11. Uiteindelijk ziet de tafel er zo uit
Laten we verder gaan met het formuleren van de stelling.
Stelling 3
De kleinste positieve en niet-1 deler van het grondtal a is niet groter dan a, waarbij a de rekenkundige wortel is van het gegeven getal.
Bewijs 3
Het is noodzakelijk om b de kleinste deler van een samengesteld getal a aan te duiden. Er is een geheel getal q, waarbij a = b · q, en we hebben dat b ≤ q. Ongelijkheden in de vorm zijn onaanvaardbaar b > q, omdat de voorwaarde wordt geschonden. Beide zijden van de ongelijkheid b ≤ q moeten worden vermenigvuldigd met een positief getal b dat niet gelijk is aan 1. We krijgen dat b · b ≤ b · q, waarbij b 2 ≤ a en b ≤ a.
Uit de bewezen stelling blijkt duidelijk dat het doorstrepen van getallen in de tabel ertoe leidt dat je moet beginnen met een getal dat gelijk is aan b 2 en voldoet aan de ongelijkheid b 2 ≤ a. Dat wil zeggen, als u getallen doorstreept die een veelvoud van 2 zijn, begint het proces met 4, en veelvouden van 3 met 9, enzovoort tot en met 100.
Het samenstellen van een dergelijke tabel met behulp van de stelling van Eratosthenes suggereert dat wanneer alle samengestelde getallen zijn doorgestreept, er priemgetallen overblijven die niet groter zijn dan n. In het voorbeeld waarbij n = 50, hebben we dat n = 50. Vanaf hier krijgen we te zien dat de zeef van Eratosthenes alle samengestelde getallen uitzift die niet significant zijn in waarde. grotere waarde wortel van 50. Zoeken naar cijfers doe je door door te strepen.
Voordat u het probleem oplost, moet u weten of het getal een priemgetal of een samengesteld getal is. Er wordt vaak gebruik gemaakt van deelbaarheidscriteria. Laten we dit in het onderstaande voorbeeld bekijken.
voorbeeld 1
Bewijs dat het getal 898989898989898989 samengesteld is.
Oplossing
De som van de cijfers van een bepaald getal is 9 8 + 9 9 = 9 17. Dit betekent dat het getal 9 · 17 deelbaar is door 9, gebaseerd op de deelbaarheidstest door 9. Hieruit volgt dat het samengesteld is.
Dergelijke tekens zijn niet in staat de priemheid van een getal te bewijzen. Als verificatie nodig is, moeten andere maatregelen worden genomen. Meest gepaste manier- het zijn een aantal cijfers. Tijdens het proces kunnen priemgetallen en samengestelde getallen worden gevonden. Dat wil zeggen dat de getallen de waarde a niet mogen overschrijden. Dat wil zeggen dat het getal a moet worden ontleed belangrijkste factoren. als hieraan is voldaan, kan het getal a als een priemgetal worden beschouwd.
Voorbeeld 2
Bepaal het samengestelde of priemgetal 11723.
Oplossing
Nu moet je alle delers voor het getal 11723 vinden. Moet 11723 evalueren.
Vanaf hier zien we dat 11723< 200 , то 200 2 = 40 000 en 11 723< 40 000 . Получаем, что делители для 11 723 minder aantal 200 .
Voor een nauwkeurigere schatting van het getal 11723 moet je de uitdrukking 108 2 = 11 664 schrijven, en 109 2 = 11 881 , Dat 108 2 < 11 723 < 109 2 . Hieruit volgt dat 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Bij het uitbreiden vinden we dat 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107 zijn allemaal priemgetallen. Dit hele proces kan worden weergegeven als deling door een kolom. Dat wil zeggen: deel 11723 door 19. Het getal 19 is een van de factoren, omdat we een deling krijgen zonder rest. Laten we de divisie weergeven als een kolom:
Hieruit volgt dat 11723 een samengesteld getal is, omdat het naast zichzelf en 1 een deler van 19 heeft.
Antwoord: 11723 is een samengesteld getal.
Als u een fout in de tekst opmerkt, markeer deze dan en druk op Ctrl+Enter
Opsomming van delers. Per definitie aantal N is alleen een priemgetal als het niet deelbaar is door 2 en andere gehele getallen behalve 1 en zichzelf. De bovenstaande formule elimineert onnodige stappen en bespaart tijd: na het controleren of een getal deelbaar is door 3, hoeft u bijvoorbeeld niet meer te controleren of het deelbaar is door 9.
- De functie floor(x) rondt x af op het dichtstbijzijnde gehele getal dat kleiner is dan of gelijk is aan x.
Leer meer over modulaire rekenkunde. De bewerking "x mod y" (mod is een afkorting van het Latijnse woord "modulo", dat wil zeggen "module") betekent "deel x door y en vind de rest." Met andere woorden, in modulaire rekenkunde, bij het bereiken van een bepaalde waarde, die wordt genoemd module, de cijfers “draaien” weer naar nul. Een klok houdt bijvoorbeeld de tijd bij met een modulus van 12: hij geeft 10, 11 en 12 uur aan en keert dan terug naar 1.
- Veel rekenmachines hebben een mod-toets. Aan het einde van deze sectie ziet u hoe u deze functie handmatig voor grote getallen kunt evalueren.
Leer meer over de valkuilen van de kleine stelling van Fermat. Alle getallen waarvoor niet aan de testvoorwaarden wordt voldaan, zijn samengesteld, maar de overige getallen zijn dat alleen waarschijnlijk worden als eenvoudig geclassificeerd. Als u onjuiste resultaten wilt voorkomen, zoekt u naar N in de lijst met "Carmichael-getallen" (samengestelde getallen die aan deze test voldoen) en "pseudo-priemgetallen van Fermat" (deze getallen voldoen slechts voor sommige waarden aan de testvoorwaarden A).
Gebruik indien mogelijk de Miller-Rabin-test. Hoewel deze methode nogal omslachtig bij het handmatig berekenen, het wordt vaak gebruikt computerprogramma's. Het biedt acceptabele snelheid en geeft minder fouten dan de methode van Fermat. Een samengesteld getal wordt niet als priemgetal geaccepteerd als er voor meer dan ¼ van de waarden berekeningen worden gemaakt A. Als je willekeurig selecteert verschillende betekenissen A en voor allemaal zal de test een positief resultaat opleveren, daar kunnen we met een vrij hoge mate van zekerheid van uitgaan N is een priemgetal.
Gebruik modulaire rekenkunde voor grote getallen. Als u geen rekenmachine met een mod-functie bij de hand heeft of als de rekenmachine niet is ontworpen voor bewerkingen daarmee grote getallen, gebruik eigenschappen van machten en modulaire rekenkunde om berekeningen eenvoudiger te maken. Hieronder vindt u een voorbeeld voor 3 50 (\displaystyle 3^(50)) mod. 50:
- Herschrijf de uitdrukking in meer handige vorm: mod 50. Voor handmatige berekeningen kunnen verdere vereenvoudigingen nodig zijn.
- (3 25 * 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Hier hebben we rekening gehouden met de eigenschap van modulaire vermenigvuldiging.
- 3 25 (\displaystyle 3^(25)) mod. 50 = 43.
- (3 25 (\displaystyle (3^(25)) mod.50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 * 43) (\displaystyle (43*43)) mod.50.
- = 1849 (\displaystyle =1849) mod.50.
- = 49 (\displaystyle =49).
Ilya's antwoord is correct, maar niet erg gedetailleerd. In de 18e eeuw werd één overigens nog als een priemgetal beschouwd. Bijvoorbeeld grote wiskundigen als Euler en Goldbach. Goldbach is de auteur van een van de zeven problemen van het millennium: de Goldbach-hypothese. De oorspronkelijke formulering stelt dat elke even getal representeerbaar als de som van twee priemgetallen. Bovendien werd aanvankelijk rekening gehouden met 1 als priemgetal, en we zien dit: 2 = 1+1. Dit kleinste voorbeeld, wat voldoet aan de oorspronkelijke formulering van de hypothese. Later werd het gecorrigeerd en werd de bewoording: moderne uitstraling: “elk even getal, beginnend met 4, kan worden weergegeven als de som van twee priemgetallen.”
Laten we de definitie onthouden. Een priemgetal is een natuurlijk getal p dat slechts 2 verschillende natuurlijke delers heeft: p zelf en 1. Uit de definitie volgt: een priemgetal p heeft slechts één priemgetal: p zelf.
Laten we nu aannemen dat 1 een priemgetal is. Per definitie heeft een priemgetal slechts één priemdeler: zichzelf. Dan blijkt dat elk priemgetal groter dan 1 deelbaar is door een ander priemgetal (door 1). Maar twee verschillende priemgetallen kunnen niet door elkaar worden gedeeld, omdat anders zijn het geen priemgetallen, maar samengestelde getallen, en dit is in tegenspraak met de definitie. Met deze aanpak blijkt dat er maar één priemgetal is: de eenheid zelf. Maar dit is absurd. Daarom is 1 geen priemgetal.
1 vormen, evenals 0, een andere klasse getallen: de klasse van neutrale elementen met betrekking tot n-aire bewerkingen in een deelverzameling van het algebraïsche veld. Bovendien is 1, met betrekking tot de werking van het optellen, ook een genererend element voor de ring van gehele getallen.
Met deze overweging is het niet moeilijk om analogen van priemgetallen in andere algebraïsche structuren te ontdekken. Stel dat we een multiplicatieve groep hebben gevormd uit machten van 2, beginnend bij 1: 2, 4, 8, 16, ... etc. 2 fungeert hier als vormend element. Een priemgetal in deze groep is een getal groter dan het kleinste element en alleen deelbaar door zichzelf en door kleinste element. In onze groep hebben er slechts vier zulke eigenschappen. Er zijn geen priemgetallen meer in onze groep.
Als 2 ook een priemgetal zou zijn in onze groep, zie dan de eerste paragraaf - opnieuw zou blijken dat alleen 2 een priemgetal is.
In dit artikel gaan we op onderzoek uit priemgetallen en samengestelde getallen. Eerst zullen we definities geven van priemgetallen en samengestelde getallen, en ook voorbeelden geven. Hierna zullen we bewijzen dat er oneindig veel priemgetallen zijn. Vervolgens zullen we een tabel met priemgetallen opschrijven en methoden overwegen voor het samenstellen van een tabel met priemgetallen, waarbij we bijzondere aandacht besteden aan de methode die de zeef van Eratosthenes wordt genoemd. Concluderend belichten we de belangrijkste punten waarmee rekening moet worden gehouden bij het bewijzen hiervan gegeven nummer is enkelvoudig of samengesteld.
Paginanavigatie.
Priemgetallen en samengestelde getallen - Definities en voorbeelden
De concepten van priemgetallen en samengestelde getallen verwijzen naar getallen die groter zijn dan één. Dergelijke gehele getallen zijn, afhankelijk van het aantal positieve delers, verdeeld in priemgetallen en samengestelde getallen. Dus om te begrijpen definities van priemgetallen en samengestelde getallen, moet je goed begrijpen wat delers en veelvouden zijn.
Definitie.
priemgetallen zijn gehele getallen, grote eenheden, die slechts twee positieve delers hebben, namelijk zichzelf en 1.
Definitie.
Samengestelde getallen zijn gehele getallen, grote, die minstens drie positieve delers hebben.
Afzonderlijk merken we op dat het getal 1 niet van toepassing is op priemgetallen of samengestelde getallen. Eenheid heeft slechts één positieve deler, namelijk het getal 1 zelf. Dit onderscheidt het getal 1 van alle andere positieve gehele getallen die minstens twee positieve delers hebben.
Gezien het feit dat positieve gehele getallen zijn, en dat men slechts één positieve deler heeft, kunnen we andere formuleringen geven van de vermelde definities van priemgetallen en samengestelde getallen.
Definitie.
priemgetallen zijn natuurlijke getallen die slechts twee positieve delers hebben.
Definitie.
Samengestelde getallen zijn natuurlijke getallen die meer dan twee positieve delers hebben.
Merk op dat elk positief geheel getal groter dan één een priemgetal of een samengesteld getal is. Met andere woorden: er is geen enkel geheel getal dat priemgetal noch samengesteld is. Dit volgt uit de eigenschap van deelbaarheid, die stelt dat de getallen 1 en a altijd delers zijn van elk geheel getal a.
Op basis van de informatie in de vorige paragraaf kunnen we de volgende definitie van samengestelde getallen geven.
Definitie.
Natuurlijke getallen die geen priemgetallen zijn, worden genoemd composiet.
Laten we het geven voorbeelden van priemgetallen en samengestelde getallen.
Voorbeelden van samengestelde getallen zijn 6, 63, 121 en 6.697. Ook deze verklaring behoeft verduidelijking. Het getal 6 heeft naast de positieve delers 1 en 6 ook de delers 2 en 3, aangezien 6 = 2 3, dus 6 is echt een samengesteld getal. Positieve factoren van 63 zijn de getallen 1, 3, 7, 9, 21 en 63. Het getal 121 is gelijk aan het product 11·11, dus de positieve delers zijn 1, 11 en 121. En het getal 6.697 is samengesteld, omdat de positieve delers ervan, naast 1 en 6.697, ook de getallen 37 en 181 zijn.
Ter afsluiting van dit punt zou ik ook de aandacht willen vestigen op het feit dat priemgetallen en coprime-getallen verre van hetzelfde zijn.
Priemgetallen tabel
Priemgetallen worden, voor het gemak van verder gebruik, vastgelegd in een tabel die een tabel met priemgetallen wordt genoemd. Hieronder is tabel met priemgetallen tot 1.000.
Er rijst een logische vraag: “Waarom hebben we de tabel met priemgetallen slechts tot 1000 gevuld, is het niet mogelijk om een tabel met alle bestaande priemgetallen te maken”?
Laten we eerst het eerste deel van deze vraag beantwoorden. Voor de meeste problemen waarvoor priemgetallen nodig zijn, zijn priemgetallen binnen duizend voldoende. In andere gevallen zult u hoogstwaarschijnlijk uw toevlucht moeten nemen tot een aantal speciale oplossingen. Hoewel we natuurlijk een tabel met priemgetallen kunnen maken tot een willekeurig groot eindig geheel getal positief nummer Of het nu 10.000 of 1.000.000.000 is, in de volgende paragraaf zullen we het hebben over methoden voor het samenstellen van tabellen met priemgetallen, in het bijzonder zullen we de genoemde methode analyseren.
Laten we nu eens kijken naar de mogelijkheid (of beter gezegd, de onmogelijkheid) om een tabel samen te stellen met alle bestaande priemgetallen. We kunnen geen tabel maken van alle priemgetallen, omdat er oneindig veel priemgetallen zijn. De laatste bewering is een stelling die we zullen bewijzen na de volgende hulpstelling.
Stelling.
De kleinste positieve deler anders dan 1 van een natuurlijk getal groter dan één is een priemgetal.
Bewijs.
Laten a is een natuurlijk getal groter dan één, en b is de kleinste positieve deler van een ander getal dan één. Laten we door tegenspraak bewijzen dat b een priemgetal is.
Laten we aannemen dat b een samengesteld getal is. Dan is er een deler van het getal b (laten we dit b 1 noemen), die verschillend is van zowel 1 als b. Als we er ook rekening mee houden dat de absolute waarde van de deler niet groter is dan absolute waarde deelbaar is (dit weten we uit de eigenschappen van deelbaarheid), dan moet aan voorwaarde 1 zijn voldaan
Omdat het getal a deelbaar is door b volgens de voorwaarde, en we zeiden dat b deelbaar is door b 1, stelt het concept van deelbaarheid ons in staat te praten over het bestaan van gehele getallen q en q 1 zodat a=b q en b=b 1 q 1 , vanwaar a= b 1 ·(q 1 ·q) . Hieruit volgt dat het product van twee gehele getallen een geheel getal is, en de gelijkheid a=b 1 ·(q 1 ·q) geeft aan dat b 1 een deler is van het getal a. Rekening houdend met de bovengenoemde ongelijkheden 1
Nu kunnen we bewijzen dat er oneindig veel priemgetallen zijn.
Stelling.
Er zijn een oneindig aantal priemgetallen.
Bewijs.
Laten we aannemen dat dit niet het geval is. Dat wil zeggen, stel dat er slechts n priemgetallen zijn, en deze priemgetallen zijn p 1, p 2, ..., p n. Laten we laten zien dat we altijd een priemgetal kunnen vinden dat verschilt van de aangegeven getallen.
Beschouw het getal p gelijk aan p 1 ·p 2 ·…·p n +1. Het is duidelijk dat dit getal verschilt van elk van de priemgetallen p 1, p 2, ..., p n. Als het getal p een priemgetal is, is de stelling bewezen. Als dit getal samengesteld is, dan is er op grond van de vorige stelling een priemdeler van dit getal (we noemen het p n+1). Laten we aantonen dat deze deler met geen van de getallen p 1, p 2, ..., p n samenvalt.
Als dit niet zo zou zijn, dan zou, volgens de eigenschappen van deelbaarheid, het product p 1 ·p 2 ·…·pn gedeeld worden door p n+1. Maar het getal p is ook deelbaar door p n+1, gelijk aan de som p 1 ·p 2 ·…·p n +1. Hieruit volgt dat p n+1 de tweede term van deze som, die gelijk is aan één, moet delen, maar dit is onmogelijk.
Het is dus bewezen dat er altijd een nieuw priemgetal kan worden gevonden dat niet onder een aantal vooraf bepaalde priemgetallen valt. Er zijn dus oneindig veel priemgetallen.
Dus vanwege het feit dat er een oneindig aantal priemgetallen zijn, beperk je je bij het samenstellen van tabellen met priemgetallen altijd van bovenaf tot een getal, meestal 100, 1.000, 10.000, enz.
Zeef van Eratosthenes
Nu zullen we manieren bespreken om tabellen met priemgetallen te maken. Stel dat we een tabel moeten maken met priemgetallen tot 100.
De meest voor de hand liggende methode om dit probleem op te lossen is om positieve gehele getallen, beginnend bij 2 en eindigend met 100, opeenvolgend te controleren op de aanwezigheid van een positieve deler die groter is dan 1 en kleiner dan het geteste getal (van de eigenschappen van deelbaarheid die we kennen dat de absolute waarde van de deler niet groter is dan de absolute waarde van het deeltal (niet nul). Als een dergelijke deler niet wordt gevonden, is het geteste getal een priemgetal en wordt het in de tabel met priemgetallen ingevoerd. Als een dergelijke deler wordt gevonden, is het geteste getal samengesteld; het wordt NIET opgenomen in de tabel met priemgetallen. Hierna is er een overgang naar het volgende getal, dat op dezelfde manier wordt gecontroleerd op de aanwezigheid van een deler.
Laten we de eerste paar stappen beschrijven.
Wij beginnen met nummer 2. Het getal 2 heeft geen andere positieve delers dan 1 en 2. Daarom is het eenvoudig, daarom voeren we het in de tabel met priemgetallen in. Hier moet gezegd worden dat 2 het kleinste priemgetal is. Laten we verder gaan naar nummer 3. De mogelijke positieve deler anders dan 1 en 3 is het getal 2. Maar 3 is niet deelbaar door 2, daarom is 3 een priemgetal en moet het ook worden opgenomen in de tabel met priemgetallen. Laten we verder gaan naar nummer 4. De andere positieve delers dan 1 en 4 kunnen de getallen 2 en 3 zijn, laten we ze controleren. Het getal 4 is deelbaar door 2. Daarom is 4 een samengesteld getal en hoeft het niet te worden opgenomen in de tabel met priemgetallen. Houd er rekening mee dat 4 het kleinste samengestelde getal is. Laten we verder gaan naar nummer 5. We controleren of ten minste één van de getallen 2, 3, 4 de deler is. Omdat 5 niet deelbaar is door 2, 3 of 4, is het een priemgetal en moet het worden opgeschreven in de tabel met priemgetallen. Dan is er een overgang naar de getallen 6, 7, enzovoort tot en met 100.
Deze benadering voor het samenstellen van een tabel met priemgetallen is verre van ideaal. Op de een of andere manier heeft hij bestaansrecht. Merk op dat u met deze methode voor het construeren van een tabel met gehele getallen deelbaarheidscriteria kunt gebruiken, wat het proces van het vinden van delers enigszins zal versnellen.
Er is een handiger manier om een tabel met priemgetallen te maken, genaamd. Het woord 'zeef' dat in de naam aanwezig is, is niet toevallig, aangezien de acties van deze methode als het ware helpen om hele getallen en grote eenheden door de zeef van Eratosthenes te 'zeven' om eenvoudige van samengestelde getallen te scheiden.
Laten we de zeef van Eratosthenes in actie laten zien bij het samenstellen van een tabel met priemgetallen tot 50.
Schrijf eerst de getallen 2, 3, 4, ..., 50 op volgorde.
Het eerste getal dat geschreven wordt, 2, is een priemgetal. Nu gaan we vanaf nummer 2 achtereenvolgens twee cijfers naar rechts en schrappen deze cijfers totdat we het einde bereiken van de tabel met getallen die wordt samengesteld. Hierdoor worden alle getallen die een veelvoud van twee zijn, doorgestreept.
Het eerste getal na 2 dat niet is doorgestreept, is 3. Dit getal is een priemgetal. Nu gaan we vanaf nummer 3 achtereenvolgens drie cijfers naar rechts (rekening houdend met de reeds doorgestreepte cijfers) en schrappen ze. Hierdoor worden alle getallen die een veelvoud van drie zijn, doorgestreept.
Het eerste getal na 3 dat niet is doorgestreept, is 5. Dit getal is een priemgetal. Nu gaan we vanaf nummer 5 consequent 5 cijfers naar rechts (we houden ook rekening met de eerder doorgestreepte nummers) en schrappen ze. Hierdoor worden alle getallen die een veelvoud van vijf zijn, doorgestreept.
Vervolgens schrappen we getallen die een veelvoud van 7 zijn, dan een veelvoud van 11, enzovoort. Het proces eindigt wanneer er geen cijfers meer zijn om af te strepen. Hieronder vindt u de ingevulde tabel met priemgetallen tot en met 50, verkregen met behulp van de zeef van Eratosthenes. Alle niet-gekruiste getallen zijn priemgetallen en alle doorgestreepte getallen zijn samengesteld.
Laten we ook een stelling formuleren en bewijzen die het proces van het samenstellen van een tabel met priemgetallen zal versnellen met behulp van de zeef van Eratosthenes.
Stelling.
De kleinste positieve deler van een samengesteld getal a dat verschilt van één is niet groter dan , waarbij is van a .
Bewijs.
Laten we met de letter b de kleinste deler van een samengesteld getal a aanduiden dat verschilt van één (het getal b is een priemgetal, zoals volgt uit de stelling die helemaal aan het begin van de vorige paragraaf is bewezen). Dan is er een geheel getal q zodat a=b·q (hier is q een positief geheel getal, dat volgt uit de regels voor de vermenigvuldiging van gehele getallen), en (voor b>q wordt de voorwaarde dat b de kleinste deler van a is, geschonden , aangezien q ook een deler is van het getal a vanwege de gelijkheid a=q·b ). Door beide zijden van de ongelijkheid te vermenigvuldigen met een positief getal en een geheel getal groter dan één (dit mogen we doen), verkrijgen we , waaruit en .
Wat geeft de bewezen stelling ons over de zeef van Eratosthenes?
Ten eerste moet het doorstrepen van samengestelde getallen die veelvouden zijn van een priemgetal b beginnen met een getal gelijk aan (dit volgt uit de ongelijkheid). Als u bijvoorbeeld getallen doorstreept die een veelvoud van twee zijn, moet u beginnen met het getal 4, veelvouden van drie met het getal 9, veelvouden van vijf met het getal 25, enzovoort.
Ten tweede kan het samenstellen van een tabel met priemgetallen tot en met het getal n met behulp van de zeef van Eratosthenes als voltooid worden beschouwd als alle samengestelde getallen die veelvouden zijn van priemgetallen niet groter zijn dan . In ons voorbeeld is n=50 (aangezien we een tabel maken met priemgetallen tot en met 50) en daarom zou de zeef van Eratosthenes alle samengestelde getallen moeten elimineren die veelvouden zijn van de priemgetallen 2, 3, 5 en 7 die dat wel doen. mag de rekenkundige wortel van 50 niet overschrijden. Dat wil zeggen dat we niet langer hoeven te zoeken naar getallen die veelvouden zijn van de priemgetallen 11, 13, 17, 19, 23 enzovoort tot en met 47, omdat ze dan al zijn doorgestreept als veelvouden van de kleinere priemgetallen 2. , 3, 5 en 7 .
Is dit getal een priemgetal of een samengesteld getal?
Bij sommige taken moet worden uitgezocht of een bepaald getal een priemgetal of een samengesteld getal is. Over het algemeen is deze taak verre van eenvoudig, vooral voor getallen waarvan het schrift uit een aanzienlijk aantal tekens bestaat. In de meeste gevallen moet u op zoek gaan naar een specifieke manier om het probleem op te lossen. Voor eenvoudige gevallen zullen we echter proberen richting te geven aan de gedachtegang.
Natuurlijk kun je proberen deelbaarheidstests te gebruiken om te bewijzen dat een bepaald getal samengesteld is. Als bijvoorbeeld uit een deelbaarheidstest blijkt dat een bepaald getal deelbaar is door een positief geheel getal groter dan één, dan is het oorspronkelijke getal samengesteld.
Voorbeeld.
Bewijs dat 898.989.898.989.898.989 een samengesteld getal is.
Oplossing.
De som van de cijfers van dit getal is 9·8+9·9=9·17. Omdat het getal gelijk aan 9·17 deelbaar is door 9, kunnen we door deelbaarheid door 9 zeggen dat het oorspronkelijke getal ook deelbaar is door 9. Daarom is het samengesteld.
Een belangrijk nadeel van deze benadering is dat de deelbaarheidscriteria het niet mogelijk maken de priemheid van een getal te bewijzen. Wanneer u een getal test om te zien of het een priemgetal of een samengesteld getal is, moet u de zaken daarom anders aanpakken.
De meest logische aanpak is om alle mogelijke delers van een bepaald getal te proberen. Als geen van de mogelijke delers een echte deler is van een bepaald getal, dan is dit getal een priemgetal, anders is het samengesteld. Uit de in de vorige paragraaf bewezen stellingen volgt dat delers van een bepaald getal a moeten worden gezocht onder priemgetallen die niet groter zijn dan . Een bepaald getal a kan dus opeenvolgend worden gedeeld door priemgetallen (die handig uit de tabel met priemgetallen kunnen worden gehaald), in een poging de deler van het getal a te vinden. Als er een deler wordt gevonden, is het getal a samengesteld. Als onder de priemgetallen die niet groter zijn dan , er geen deler van het getal a is, dan is het getal a een priemgetal.
Voorbeeld.
Nummer 11 723 enkelvoudig of samengesteld?
Oplossing.
Laten we eens kijken tot welk priemgetal de delers van het getal 11.723 kunnen zijn. Om dit te doen, laten we evalueren.
Dat is vrij duidelijk 
, sinds 200 2 =40.000, en 11.723<40 000
(при необходимости смотрите статью vergelijking van cijfers). De mogelijke priemfactoren van 11.723 zijn dus minder dan 200. Dit maakt onze taak al veel gemakkelijker. Als we dit niet wisten, zouden we alle priemgetallen moeten doorlopen, niet tot 200, maar tot het getal 11.723.
Indien gewenst kunt u nauwkeuriger evalueren. Omdat 108 2 =11.664 en 109 2 =11.881, dan 108 2<11 723<109 2
, следовательно, 
. Elk van de priemgetallen kleiner dan 109 is dus potentieel een priemfactor van het gegeven getal 11.723.
Nu zullen we het getal 11.723 opeenvolgend verdelen in priemgetallen 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Als het getal 11.723 wordt gedeeld door een van de geschreven priemgetallen, is het samengesteld. Als het niet deelbaar is door een van de geschreven priemgetallen, dan is het oorspronkelijke getal een priemgetal.
We zullen dit hele eentonige en monotone proces van verdeeldheid niet beschrijven. Laten we meteen zeggen dat 11.723
Getallen zijn verschillend: natuurlijk, rationeel, rationeel, geheel getal en fractioneel, positief en negatief, complex en priemgetallen, oneven en even, reëel, enz. In dit artikel kun je ontdekken wat priemgetallen zijn.
Welke getallen worden in het Engels 'eenvoudig' genoemd?
Heel vaak weten schoolkinderen op het eerste gezicht niet hoe ze een van de meest eenvoudige vragen in de wiskunde moeten beantwoorden, over wat een priemgetal is. Ze verwarren vaak priemgetallen met natuurlijke getallen (dat wil zeggen de getallen die mensen gebruiken bij het tellen van objecten, terwijl ze in sommige bronnen met nul beginnen en in andere met één). Maar dit zijn totaal twee verschillende concepten. Priemgetallen zijn natuurlijke getallen, dat wil zeggen gehele getallen en positieve getallen die groter zijn dan één en die slechts twee natuurlijke delers hebben. Bovendien is een van deze delers het gegeven getal, en de tweede is één. Drie is bijvoorbeeld een priemgetal omdat het niet zonder rest kan worden gedeeld door een ander getal dan zichzelf en één.
Samengestelde getallen
Het tegenovergestelde van priemgetallen zijn samengestelde getallen. Ze zijn ook natuurlijk, ook groter dan één, maar hebben geen twee, maar een groter aantal delers. De getallen 4, 6, 8, 9, etc. zijn bijvoorbeeld natuurlijke, samengestelde getallen, maar geen priemgetallen. Zoals je kunt zien, zijn dit meestal even getallen, maar niet allemaal. Maar ‘twee’ is een even getal en het ‘eerste getal’ in een reeks priemgetallen.
Vervolg
Om een reeks priemgetallen te construeren, is het noodzakelijk om uit alle natuurlijke getallen te kiezen, rekening houdend met hun definitie, dat wil zeggen dat je in tegenspraak moet handelen. Het is noodzakelijk om elk van de positieve natuurlijke getallen te onderzoeken om te zien of het meer dan twee delers heeft. Laten we proberen een reeks (reeks) te bouwen die uit priemgetallen bestaat. De lijst begint met twee, gevolgd door drie, omdat deze alleen deelbaar is door zichzelf en één. Denk eens aan het getal vier. Heeft het andere delers dan vier en één? Ja, dat getal is 2. Vier is dus geen priemgetal. Vijf is ook een priemgetal (het is niet deelbaar door een ander getal, behalve 1 en 5), maar zes is wel deelbaar. En als je alle even getallen volgt, zul je in het algemeen merken dat, behalve ‘twee’, geen van deze een priemgetal is. Hieruit concluderen we dat even getallen, behalve twee, geen priemgetallen zijn. Nog een ontdekking: alle getallen die deelbaar zijn door drie, behalve de drie zelf, of ze nu even of oneven zijn, zijn ook geen priemgetallen (6, 9, 12, 15, 18, 21, 24, 27, enz.). Hetzelfde geldt voor getallen die deelbaar zijn door vijf en zeven. Al hun veelheid is ook niet eenvoudig. Laten we het samenvatten. Eenvoudige getallen van één cijfer omvatten dus alle oneven getallen behalve één en negen, en zelfs ‘twee’ zijn even getallen. De tientallen zelf (10, 20,... 40, etc.) zijn niet eenvoudig. Priemgetallen van twee cijfers, drie cijfers, etc. kunnen worden bepaald op basis van de bovenstaande principes: als ze geen andere delers hebben dan zijzelf en één.
Theorieën over de eigenschappen van priemgetallen
Er is een wetenschap die de eigenschappen van gehele getallen bestudeert, inclusief priemgetallen. Dit is een tak van de wiskunde die hoger wordt genoemd. Naast de eigenschappen van gehele getallen houdt ze zich ook bezig met algebraïsche en transcendentale getallen, evenals functies van verschillende oorsprong die verband houden met de rekenkunde van deze getallen. In deze studies worden naast elementaire en algebraïsche methoden ook analytische en geometrische methoden gebruikt. Concreet houdt "Getaltheorie" zich bezig met de studie van priemgetallen.
Priemgetallen zijn de ‘bouwstenen’ van natuurlijke getallen
In de rekenkunde is er een stelling die de fundamentele stelling wordt genoemd. Volgens het kan elk natuurlijk getal, behalve één, worden weergegeven als een product, waarvan de factoren priemgetallen zijn, en de volgorde van de factoren is uniek, wat betekent dat de representatiemethode uniek is. Het heet het ontbinden van een natuurlijk getal in priemfactoren. Er is een andere naam voor dit proces: ontbinding van getallen. Op basis hiervan kunnen priemgetallen ‘bouwmateriaal’, ‘blokken’ worden genoemd voor het construeren van natuurlijke getallen.
Zoeken naar priemgetallen. Eenvoud testen
Veel wetenschappers uit verschillende tijden probeerden enkele principes (systemen) te vinden voor het vinden van een lijst met priemgetallen. De wetenschap kent systemen die de Atkin-zeef, de Sundartham-zeef en de Eratosthenes-zeef worden genoemd. Ze leveren echter geen significante resultaten op en er wordt een eenvoudige test gebruikt om de priemgetallen te vinden. Wiskundigen creëerden ook algoritmen. Ze worden meestal primaliteitstests genoemd. Er is bijvoorbeeld een test ontwikkeld door Rabin en Miller. Het wordt gebruikt door cryptografen. Er is ook de Kayal-Agrawal-Sasquena-test. Ondanks voldoende nauwkeurigheid is het echter erg moeilijk te berekenen, wat de praktische betekenis ervan vermindert.
Heeft de reeks priemgetallen een limiet?
De oude Griekse wetenschapper Euclides schreef in zijn boek ‘Elements’ dat de reeks priemgetallen oneindig is. Hij zei dit: “Laten we ons even voorstellen dat priemgetallen een limiet hebben. Laten we ze dan met elkaar vermenigvuldigen en er één aan het product toevoegen. Het getal dat als resultaat van deze eenvoudige handelingen wordt verkregen, kan door geen van de reeksen priemgetallen worden gedeeld, omdat de rest altijd één zal zijn. Dit betekent dat er een ander getal is dat nog niet in de lijst met priemgetallen staat. Daarom is onze veronderstelling niet waar en kan deze verzameling geen limiet hebben. Naast het bewijs van Euclides bestaat er een modernere formule van de achttiende-eeuwse Zwitserse wiskundige Leonhard Euler. Volgens deze theorie groeit de som van de som van de eerste n getallen onbeperkt naarmate het getal n toeneemt. En hier is de formule van de stelling over de verdeling van priemgetallen: (n) groeit als n/ln (n).
Wat is het grootste priemgetal?
Dezelfde Leonard Euler wist het grootste priemgetal van zijn tijd te vinden. Dit is 2 31 - 1 = 2147483647. In 2013 werd echter nog een meest nauwkeurige grootste in de lijst met priemgetallen berekend: 2 57885161 - 1. Dit wordt het Mersenne-nummer genoemd. Het bevat ongeveer 17 miljoen decimalen. Zoals je kunt zien is het aantal gevonden door een achttiende-eeuwse wetenschapper vele malen kleiner dan dit. Dat had zo moeten zijn, want Euler voerde deze berekening handmatig uit, terwijl onze tijdgenoot waarschijnlijk werd geholpen door een computer. Bovendien werd dit nummer verkregen bij de Faculteit der Wiskunde van een van de Amerikaanse afdelingen. Getallen die naar deze wetenschapper zijn vernoemd, slagen voor de primaliteitstest van Luc-Lemaire. De wetenschap wil daar echter niet stoppen. De Electronic Frontier Foundation, die in 1990 in de Verenigde Staten van Amerika (EFF) werd opgericht, heeft een geldelijke beloning aangeboden voor het vinden van grote priemgetallen. En als tot 2013 de prijs werd toegekend aan wetenschappers die ze zouden vinden tussen 1 en 10 miljoen decimale getallen, vandaag de dag is dit cijfer opgelopen van 100 miljoen tot 1 miljard. De prijzen variëren van 150 tot 250 duizend dollar.
Namen van speciale priemgetallen
De getallen die zijn gevonden dankzij algoritmen die door bepaalde wetenschappers zijn gemaakt en die de eenvoudstest hebben doorstaan, worden speciaal genoemd. Hier zijn er een aantal:
1. Merssen.
4. Cullen.
6. Mills et al.
De eenvoud van deze getallen, genoemd naar bovengenoemde wetenschappers, wordt vastgesteld met behulp van de volgende tests:
1. Luc Lemaire.
2. Pepina.
3. Rijsel.
4. Billhart - Lemaire - Selfridge en anderen.
De moderne wetenschap houdt daar niet op, en waarschijnlijk zal de wereld in de nabije toekomst de namen leren kennen van degenen die de prijs van $ 250.000 hebben kunnen winnen door het grootste priemgetal te vinden.