Categorie archieven: Getaltheorie

Pseudopriemen

Geplaatst op door

De kleine stelling van Fermat leert ons dat voor een priemgetal p geldt dat

    \[a^{p-1} \equiv 1 \mod p\]

of voor getallen a die onderling ondeelbaar zijn met p: a^p \equiv a \mod p.

De stelling van Fermat is niet omkeerbaar. Inderdaad is  2^{340} \equiv 1 \mod 341 en 341 = 11 \times 31. In de vijfde eeuw voor onze jaartelling wisten de Chinezen al dat uit p priem volgt dat 2^{p-1} \equiv 1 \mod p. Zij waren ook overtuigd van het omgekeerde. Ook Leibniz was daarvan overtuigd. Slechts in 1819 vond F. Sarrus bovenvermeld tegenvoorbeeld.

We noemen 341 een pseudopriem t.o.v. de basis 2.

Een Carmichael getal is een getal  p dat niet priem is en waar voor alle a die onderling ondeelbaar zijn met p, toch geldt dat a^{p-1} \equiv 1 \mod p. Zo is bijvoorbeeld 561 het kleinste Carmichael getal. De volgende Carmichael getallen zijn  1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841 en  29341. Pas in 1994 werd bewezen dat er oneindig veel Carmichael getallen zijn.

De naam Carmichael getal komt van de Amerikaanse wiskundige  Richard David  Carmichael ( 1979-1967) die het bestaan ervan introduceerde in 1910. Een andere naam voor deze getallen is absolute pseudopriemen

Priemgetaltest

Geplaatst op door

We willen twee fundamentele vragen uit de getaltheorie even onder de aandacht brengen:

  1. Hoe kan men snel zien of een getal een priemgetal is?
  2. Als n niet priem is, hoe vindt men gehele getallen a en b , groter dan 1, zodat n = a.b?

Het is verbazingwekkend dat men dikwijls kan weten dat een getal niet priem is, zonder er een factor van te kennen. Dat is te danken aan de stelling van Fermat: als n priem is dan geldt voor elk geheel getal a dat

    \[a^n \equiv a \mod n\]

Dus als je een geheel getal a kan vinden waarvoor a^n niet gelijk is aan a modulo n, dan weet men zeker dat n niet priem is, zonder nochtans een factor van n te kennen.

Willen we bewijzen dat een getal toch priem is, dan hebben we een omkering van de stelling  van Fermat nodig. Hier doen zich twee moeilijkheden voor:

  • De directe omkering is gewoon fout! Het getal n = 1729 = 7.13.19 is niet priem en toch is  a^{1729}\equiv a \mod 1729 voor elk geheel getal a.
  • En zelfs al zou de omkering waar zijn, dan zou ons dat niet echt helpen want het is ondoenlijk alle gehele getallen a te proberen.

Het zoeken naar oplossingen van deze problemen is zeer actueel en de gevonden methoden zijn soms zelfs futuristisch, aangezien ze steunen op het nog onbewezen vermoeden betreffende de veralgemeende Riemannhypothese.  Enkele namen die op dit gebied een belangrijke bijdrage geleverd hebben zijn: R. Solovay, V.Strassen, G.L. Miller, M.O.Rabin en  H.W. Lenstra ( zie foto)

De kleine stelling van Fermat

Geplaatst op door

Als p een priemgetal is en a en p onderling ondeelbaar zijn dan geldt:

    \[a^{p-1} \equiv 1 \text{ mod } p\]

Uit deze stelling, die de kleine stelling van Fermat genoemd wordt en in 1640 een eerste keer vermeld werd, volgt dat voor elke a en voor een priemgetal p geldt dat

    \[a^p \equiv a \text { mod } p\]

De stelling wordt bijvoorbeeld gebruikt om de restklasse modulo een groot getal uit te rekenen. Bereken bijvoorbeeld de rest bij deling van 2^{245} door 11. Volgens de kleine stelling van Fermat is 2^{10} \equiv 1 \text{ mod } 11, dus is 2^{245} \equiv (2^{10})^24.2^5 \equiv 2^5 \equiv 10 \text{ mod } 11.

Er bestaat een veralgemening voor de stelling, die zegt dat als a en m onderling ondeelbaar zijn, geldt

    \[a^{\varphi(m)} \equiv 1 \text { mod }m\]

Hierbij is \varphi(m) de totiënt functie van Euler die het aantal getallen, kleiner dan m, berekent die onderling ondeelbaar zijn met m. Deze stelling wordt de Euler-Fermat stelling genoemd.

Deelbaarheid door 3, 7, 9 en 11

Geplaatst op door

Iedereen weet dat een getal deelbaar is door 2 als het laatste cijfer, in zijn decimale notatie, even is.  Want een getal n kan je schrijven als n=10k+u, waarbij u het laatste cijfer is in de decimale notatie van n. Het is duidelijk dat 2|n als en slechts als 2|u. Hetzelfde geldt voor 5.

Elk getal n  is te schrijven  als n=100k+u, waarbij u het getal is gevormd door de laatste 2 cijfers van n. Bijgevolg is n deelbaar door 4 of 25 als de laatste 2 cijferss deelbaar zijn door 4 of 25.

Hoe kunnen we nu zien of een getal deelbaar is door 3, 9 of 11? Bekijken we eerst een stelling over congruenties met veeltermen met gehele cëfficiënten:

Stel f(x)=\sum_{k=0}^nc_kx^k met c_i \in \mathbb{Z}. Als a \equiv b mod m, dan is f(a) \equiv f(b) mod m.

Neem nu a=\sum_{k=0}^na_k10^k, de decimale schrijfwijze van het getal a en noteer s=\sum_{k=0}^na_k en t=\sum_{k=0}^n(-1)^ka_k. Het is duidelijk dat a=f(10) met f(x)=\sum_{k=0}^na_kx^k en dat s=f(1). Omdat 10 \equiv 1 mod 9, geldt volgens vorige stelling dat f(10) \equiv f(1) mod 9 of met andere woorden : een getal is deelbaar door 9 als de som van haar cijfers deelbaar is door 9. Analoog voor deelbaarheid door 3. Het bewijs voor deelbaarheid door 11 volgt uit het feit dat 10 \equiv -1 mod 11 en t=f(-1).

Besluit:
Een getal is deelbaar door 3 of 9 als de som van de cijfers van het getal deelbaar is door 3 of 9.
Een getal is deelbaar door 11 als t=\sum_{k=0}^n(-1)^ka_k deelbaar is door 11.

 

Een toemaatje : deelbaarheid door 7: Omdat 10^3 \equiv -1 mod 7 kan je  deelbaarheid door 7 als volgt vinden: Verdeel het getal van rechts naar links in groepjes van 3. Voor zie elk groepje alternerend met een + en – teken. Een getal is deelbaar door 7 las de som van die getallen deelbaar is door 7. Zo is bijvoorbeeld  2 345 678 902 deelbaar door 7 omdat 902 -678 + 345 – 2 = 567 en dat is deelbaar door 7 .

De Euler-phi functie

Geplaatst op door

De Euler-phi functie, ook wel totiënt functie of indicator genoemd, telt het aantal positieve natuurlijke getallen kleiner dan of gelijk aan n, die onderling ondeelbaar zijn met n. Notatie: \varphi(n).

Zo is bijvoorbeeld \varphi(10)=4, want de enige getallen die onderling ondeelbaar zijn met 10 en kleiner zijn dan 10, zijn 1,3,7 en 9.

Enkele eigenschappen:

  • \varphi(1)=1.
  • Als p een priemgetal is dan is \varphi(p)=p-1.
  • Als p een priemgetal is dan is \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).
  • Als n=p_1^{k_1}.p_2^{k_2}.\cdots.p_r^{k_r} de priemontbinding is van n, dan geldt \varphi(n)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1). Dit kan je ook schrijven als :

        \[\varphi(n)= n.\prod_{p|n}(1-\frac{1}{p})\]

    Hierbij doorloopt p alle priemdelers van n.

  • \sum_{d|n}\varphi(d)=n
  • De indicator geeft ook de omvang aan van de multiplicatieve groep van natuurlijke getallen modulo n