Een paar begrippen en feiten uit de getaltheorie

De natuurlijke getallen Getaltheorie Deler en 
veelvoud
Delen 
met rest
Manipuleren  
met resten
Grootste gemene deler Een belangrijke 
stelling over de ggd
algoritme van Euclides Priemgetallen Hoofdstelling getaltheorie

De natuurlijke getallen
Dat is de verzameling die bestaat uit de getallen 1, 2, 3, 4, 5, .... Die verzameling wordt aangegeven met N. Als je deze verzameling aanvult met  0 , -1, -2, -3 ... dan krijg je de gehele getallen. notatie Z. De natuurlijke getallen vormen een deelverzameling van de gehele getallen.

Getaltheorie
De tak van de wiskunde die zich bezighoudt met de eigenschappen van natuurlijke en gehele getallen.

Deler en veelvoud
Een natuurlijk getal b is een deler (engels divisor) van een positief natuurlijk getal a als er een natuurlijk getal k bestaat zodanig dat a = k.b. Het getal a noem je een veelvoud van b. Als b geen deler is van a dan zeg je dat a niet deelbaar is door b

                Voorbeelden:

         3 is een deler van 12 want 12 = 4.3

         13 is een deler van 260 want 260 = 20.13

         3 is geen deler van 14 want er bestaat geen geheel getal k waarvoor geldt 14 = k.3

         1 is een deler van 11 want 11 = 11.1

         11 is een deler van 11 want 11 = 1.11

Delen met rest
3 is geen deler van 14 dus 14 is niet deelbaar door 3. Als je van 14 twee aftrekt dan kun je wel delen door 3; immers 14 - 2 = 4*3. Het getal 2 is in dit voorbeeld de rest. 

Algemener:
Als a en b natuurlijke getallen zijn en a > b dan is de rest r het kleinste natuurlijke getal dat je van het getal a moet aftrekken zodanig dat a - r een veelvoud van b is . Als b een deler van a is dan is de rest gelijk aan 0.

                Voorbeelden:

         a = 29 en b = 6 dan is de rest 5 immers 29 = 4*6 + 5

         a = 21 en b = 7 dan is de rest 0 immers 21 = 3*7 + 0

         a = 6 en b = 13 dan is de rest 6 immers 6 = 0*13 + 6

Manipuleren met resten
De getallen 300 en 80 zijn beide niet deelbaar door bijvoorbeeld 9. De rest van 300 bij deling door 9 is 3, de rest van 80 bij deling door 9 is 8. Immers:

    300 = 33*9 + 3
    80   = 8*9 + 8

Hieruit volgt dat 300 + 80 = (33 + 8)*9 + 3 + 8 = 41*9 + 11 = 41*9 + 1*9 + 2= 42*9 + 2. De rest van 380 bij deling van 9 is dus 2.

Deze laatste restberekening kan ook sneller. Als je naar de berekening kijkt dan zie je dat je kunt volstaan met het optellen van de twee eerdere resten: 3 + 8 = 11 en dat geeft rest 2 bij deling door 9.

Grootste gemene deler
De grootste gemene deler van twee natuurlijke getallen a en b is het grootste getal dat deler is van a en van b. De grootste gemene deler wordt aangenoteerd met ggd(a , b). In het Engels wordt gcd(a , b) gebruikt (greatest common divisor)

      Voorbeelden:

         ggd(11 , 14) = 1

         ggd(15 , 42) = 3

         ggd( 2 , 64) = 2

De grootste gemene deler van meer dan twee getallen is het grootste getal dat deler is van alle getallen

     Voorbeelden:

         ggd(3 , 4, 5) = 1

         ggd(6 , 8 , 10) = 2

         ggd( 9 , 12 , 18) = 3

Een belangrijke stelling over de ggd
Als a en b twee natuurlijk getallen zijn met  a > b dan geldt ggd(a , b) = ggd(a-b , b). 

        Voorbeeld:

        ggd(34 , 8) = ggd(26 , 8) = ggd(18 , 8) = ggd(10 , 8) = ggd(2 , 8) = 2

Zo'n getallenvoorbeeld is natuurlijk geen bewijs. Het bewijs van deze stelling is niet heel gemakkelijk. Het kan als volgt:

Stel ggd(a , b) = c. Dat betekent dat c een deler is van a en van b. Er bestaan dus natuurlijke getallen k en l zodat geldt:  a = k*c en b = l*c. Hieruit volgt dat a - b = (k - l)*c en dat betekent dat c een deler is van a - b, dus c is een deler van a - b en van b.
Nu moet je nog bewijzen dat c de grootste deler van b en a - b is. Stel ggd(a - b , b) = d en stel d > c. Hieruit volgt dat d een deler is van b en van a - b. Dus er bestaan natuurlijke getallen p en q zodat geldt:  a - b = p*d en b = q*d. Daaruit volgt echter a = (q + p)*d dus d is ook een deler van a. En dat is een tegenspraak met ggd(a , b) = c. Want d zou dan een grotere deler zin van a en b 

Hoe bepaal je snel de grootste gemene deler? Het algoritme van Euclides
De ggd-berekening van 34 en 8 in het voorbeeld hierboven kan nog sneller. Je kunt namelijk meteen zoveel mogelijk keer 8 van 34 aftrekken: ggd(34 , 8) = ggd(34 - 4*8 , 8) = ggd(2 , 8) = 2. Deze methode wordt het algoritme van Euclides genoemd. Het algoritme wordt meestal als volgt opgeschreven 

                    34  = 4*8 + 2
                    8    = 4*2 + 0    klaar de ggd = 2

Een voorbeeld met grotere getallen. Wat is de ggd van 210 en 57?

Voorbeeld:

210
= 3*57 + 39 
57   = 1*39 + 18
39   = 2*18 + 3
18   = 6*3   + 0   klaar de ggd = 3

Priemgetallen
Priemgetallen zijn positieve, gehele getallen die niet te schrijven zijn als het product van twee kleinere positieve, gehele getallen. Bijvoorbeeld 15 is niet priem, want 15 = 3*5 maar 11 is wel priem. Je kunt ook zeggen dat een priemgetal precies twee positieve delers heeft, namelijk 1 en zichzelf. De eerste 10 priemgetallen zijn:

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19, 23 , 29

         Meer priemgetallen 1

         Meer priemgetallen 2

         Een lijst met de allergrootste priemgetallen

Hoofdstelling getaltheorie
Elk natuurlijk getal groter dan 1 is op eenduidige manier te ontbinden in priemfactoren. Dat wil zeggen dat je elk getal op precies een manier kunt schrijven als het produkt van priemgetallen

      Voorbeelden:

         12 = 2*2*3 = 22*3

         21 = 3*7

         23 = 23

         100 = 2*2*5*5 = 22*52