Tag archieven: priemgetallen

Stelling van Dirichlet voor rekenkundige rijen

Geplaatst op door

De Stelling van Dirichlet over rekenkundige rijen, ook bekend onder de naam Priemgetallenstelling van Dirichlet (Duits wiskundige, 1805-1859), is een stelling uit de getaltheorie die handelt over het voorkomen van priemgetallen in rekenkundige rijen.

De stelling luidt dat, als a en b onderling ondeelbaar zijn, dus hun grootste gemene deler gelijk is aan 1, de rij

{\displaystyle a,\ a+b,\ a+2b,\ a+3b,\ a+4b,\ \dots }

oneindig veel priemgetallen bevat. 

De stelling is een veralgemening van een bewering door Euler dat elke rekenkundige rij die met 1 begint oneindig veel priemgetallen bevat. De huidige vorm werd geformuleerd door Legendre en in 1837 bewezen door Johann Dirichlet.

De wiskundewereld heeft zich eigenlijk altijd al beziggehouden met het zoeken naar formules van rijen die oneindig veel priemgetallen bevatten.

Fermatgetallen

Geplaatst op door

In 1729 schreef Christian Goldbach aan Euler: Kent u de opmerking in het werk van Fermat dat alle getallen F_n=2^{2^n}+1 priemgetallen zijn? Hij schrijft dat hij het niet kan bewijzen, en voor zover ik weet heeft ook niemand anders een bewijs kunnen vinden.

Fermat had al opgemerkt dat de getallen F_n priemgetallen zijn voor n=0,1,2,3,4: F_0=3,F_1=5, F_2=17, F_3=257, F_4=65537, vandaar zijn vermoeden. Maar F_5=4294967297 ging zijn krachten te boven. De getallen F_n=2^{2^n}+1 noemt men Fermatgetallen.  Euler liet zich echter niet afschrikken en hij kwam tot het verrassende resultaat dat F_5 geen priemgetal is omdat het deelbaar is door 641. Het vermoeden van Fermat bleek dus niet waar te zijn – een van de zeldzame keren dat Fermat een vermoeden uitsprak dat onjuist is gebleken.

fer

Waar komt trouwens de vreemde vorm  2^{2^n}+1 vandaan?
Waarom niet gewoon 2^m+1? Wel, het is eenvoudig te bewijzen dat 2^m+1 alleen maar een priemgetal kan zijn als m van de vorm m=2^n is. Dit komt omdat, als q oneven is en groter dan 1, dan is a^q+1=(a+1)(a^{q-1}-a^{q-2}+\cdots -a+1). Op die manier kan men bewijzen dat m geen oneven deler kan hebben.

Hoe zit het met F_6=18446744073709551617? Daar lijkt zonder computer geen beginnen aan. Toch lukte het Landry en Le Lasseur in 1880 een volledige ontbinding te vinden. Ook van F_7, een getal van 39 cijfers, F_8 (78 cijfers), F_9 (155 cijfers) en F_{11} ( 617 cijfers) zijn inmiddels volledige ontbindingen gevonden. Geen van alle zijn het dus priemgetallen. Ook F_{10} is geen priemgetal, maar daarvan is alleen maar bekend dat het deelbaar is door 455925777 en 6487031809. Van de resterende factor kennen we de ontbinding niet.

Van nog veel meer Fermatgetallen is bewezen dat ze geen priemgetallen zijn. In feite is er nog steeds geen enkele grotere priem dan F_4 bekend. Bestaat er dus wel een zesde Fermat priemgetal? Het kleinste Fermat getal waarvan we niet weten of het priem is, is F_{22}, een getal van 1262612 cijfers. Verder onderzoek ligt nog open…

 

 

Veeltermen die priemgetallen uitspuwen

Geplaatst op door

Neem de veelterm 2x^2+29, en bereken de getalwaarde voor alle natuurlijke getallen tot en met 28. Je krijgt de volgende rij van getallen : 29,31,37,47,…,1597. Dit zijn allemaal priemgetallen. Vullen we 29 in dan krijgen we natuurlijk een getal dat deelbaar is door 29 en dus niet priem is.

De veelterm x^2+x+17, ingevuld voor alle natuurlijke getallen tot en met 15, geeft ook allemaal priemgetallen. De bekendste veelterm is zeker deze van Euler: x^2-x+41 die voor alle natuurlijke getallen tot en met 40 priemgetallen geeft. Nog beter doet de veelterm x^2-79x+1601 die voor alle natuurlijke getallen tot en met 79 priemgetallen uitspuwt.

 

euler

Het is wel duidelijk dat er geen niet-constante veelterm bestaat die alle priemgetallen voortbrengt. Dit kan je zelfs bewijzen:
Stel dat A(x) een niet-constante veelterm is die voor elk natuurlijk getal een priemgetal voortbrengt. Neem a \in \mathbb{N} dan is A(a)=p met p een priemgetal. Maar dan is A(a+p)\equiv 0 \text{ mod } p en omdat ook A(a+p) een priemgetal moet zijn is A(a+p)=p. We kunnen dit herhalen voor de natuurlijke getallen a+kp en vinden dat \forall k \in \mathbb{N}: A(a+kp)=p. Bijgevolg heeft de veelterm A(x)-p oneindig veel nulwaarden en is die veelterm dus constant, wat tegen het gegeven is. Er bestaat dus geen niet-constante veelterm die alleen maar priemgetallen voortbrengt.

Superpriemgetallen

Geplaatst op door

priem

 

Neem een priemgetal van 1 cijfer, bijvoorbeeld 2. Voeg er rechts een cijfer bij zodat het nieuwe getal nog steeds priem is . Bijvoorbeeld 23. Ga verder ! Ook 233 is priem. Zo kan je het rijtje  2,23,233,2333,23333 vormen.

Welk is langste priemgetal dat je zo kan vormen?
Via 7,73,739,7393,73939,739391,7393913 kom je uiteindelijk terecht bij een getal van 8 cijfers:

73.939.133

Wat is het langste priemgetal dat je kan vormen als je nu cijfers langs links bijvoegt?
Hier heb je wat meer werk want het getal bevat 24 cijfers:

357.686.312.646.216.567.629.137

Het getal genereert dus 24 priemgetallen , beginnend met 7, 37,137, 9137, …