Tag archieven: priemgetal

Circulair priemgetal

Geplaatst op door

Een  circulair priemgetal is een priemgetal dat een priemgetal blijft bij elke cyclische rotatie van de cijfers . Zo is 13 een circulair priemgetal, want het is priem en ook 31 is een priemgetal. 

Het is duidelijk dat een circulair priemgetal nooit het cijfer 0,2,4,5 of 8 kan bevatten, want door een cyclische permutatie komt dat cijfer ooit achteraan en dan is het getal deelbaar door 2 of 5 en dus niet priem.

De eerste circulaire priemen zijn 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197,…

Er is een stelling die zegt dat elk priemgetal dat enkel bestaat uit enen, altijd een circulair priemgetal is. Eveneens beweert men dat er oneindig veel priemgetallen bestaan met enkel enen. Dus zijn er ook oneindig veel circulaire priemgetallen. Waarschijnlijk zijn er, vanaf 1000000, geen andere dan die met enkel enen.

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 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