Deelbaarheid

Definities | Algoritmen | Priemgetallen | Hoofdstelling | Functie van Euler ][ Getallentheorie

Zie ook pagina "Mersenne-priemgetallen"
Zie ook pagina "Bronnen en informatie over priemgetallen"

1. Definities

Gevolgen
[1] Elk getal is deler van het getal 0, terwijl 0 geen deler is van een van 0 verschillend getal.
[2] Uit a | b volgt (-a) | b, a | (-b) en (-a) | (-b).
[3] a | a en 1 | a.
[4] Uit a | b en b | c volgt a | c
Immers
Er zijn getallen k₁ en k₂ met ak₁ = b en bk₂ = c, zodat ak₁k₂ = bk₂ = c.
[einde Gevolgen]

Bewijs:
Uit |ab |= |a|.|b| = 1 waarbij a=0 en b=0 uitgesloten zijn, volgt |a| ³ 1, |b| ³ 1
Zou nu gelden |a| > 1, dan is |a|.|b| ¹ 1. Dus is |a| = 1.
Evenzo geldt dan ook |b| = 1.
Waaruit dus volgt dat a = ± 1 en b = ± 1. ¨

De rij priemgetallen is dus:
   2, 3, 5, 7, 11, 13, 17, 19, 23, ...

Voor priemgetallen zie verder paragraaf 3.

2. Algoritmen

Overzicht

• 2.1. Delingsalgoritme
         2.1.1. Het bewijs van de delingsalgoritme
         2.1.2. De Entier-functie
• 2.2. KGV en GGD
         2.2.1. Kleinste gemene veelvoud
         2.2.2. Grootste gemene deler
• 2.3. Euclidische algoritme

2.1. Delingsalgoritme

2.1.1. Het bewijs van de delingsalgoritme

Bewijs:
Zij A de verzameling van de getallen van de vorm a - xb, waarbij x een geheel getal is.
Zij S de verzameling van de (niet-negatieve) getallen in A.
Nu is S een deelverzameling van de niet-negatieve getallen.
Voorbeeld
x = -|a|sgn(b) geeft in A het getal a + |a|.|b|, en dit getal is niet-negatief, omdat |b| ³ 1.
Nb.
sgn(x) is de "teken-functie": sgn(x) = 1 als x positief is; sgn(x) = -1 als x negatief is; sgn(x) = 0 als x = 0
[einde Nb en einde Voorbeeld]

S heeft een kleinste element r.
Zij nu r bepaald door x = q, dan is a - qb = r.
Dus:
   a = qb + r
We bewijzen nu het tweede deel van de stelling.
Zij r ³ |b| > 0 (veronderstelling).
Dan is 0 £ r - |b| < r en r - |b| = a - qb - |b| = a - ( q + sgn(b) )b.
Het getal r - |b| behoort dus tot S, maar het is kleiner dan r.
Tegenspraak. Dus
   0 £ r < |b|
Het bestaan van q en r is nu dus aangetoond.
We bewijzen tenslotte de uniciteit van q en r.
Zij a = qb + r en a = q₁b + r₁ met 0 £ r < |b| en 0 £ r₁ < |b| (veronderstelling).
Hieruit vinden we
   0 £ | r - r₁| < |b|
maar ook geldt
   | r - r₁| = | q - q₁|.|b|
Tegenspraak. Dus q en r zijn uniek. ¨

Opmerking
De gebruikelijke algoritme voor de deling van twee positieve getallen levert het getal r, dat de hoofdrest van de deling wordt genoemd.
Immers
7 / 128 \ 18
    7
     58
     56
      2
Nu is 128 = 18 . 7 + 2. Hierbij is dus q = 18 en r = 2.
Bij deling van een negatief getal is dat echter niet zo:
   -128 = (-19) . 7 - 2
De hoofdrest vinden we hier via -128 = (-19) . 7 + 5. Nu is q = -19 en r = 5.
Zie paragraaf 2.1.2. De Entier-functie voor een verdere uitwerking hiervan.
[einde Opmerking]

2.1.2. De Entier-functie

Gevolgen
[1]
Voor elke reëel getal x bestaat er een reëel getal t waarvoor x = [x] + t met 0 £ t < 1.
t heet het fractionele deel van x.
[2]
Uit a =qb + r met 0 £ r < |b| volgt dan
   
[einde Gevolgen]

2.2. KGV en GGD

2.2.1 Kleinste gemene veelvoud

Bewijs:
Het productl |a₁a₂a₃...a_n| is element van V⁺.¨

Gevolg
V⁺ heeft een kleinste element.
Dit kleinste element van V⁺ speelt een bijzondere rol (als kgv) in hetgeen volgt
[einde Gevolg]

Bewijs:
[1] m | l houdt in, dat l deelbaar is door iedere a_i (volgens de definitie van m).
Daarom is l een gemeenschappelijk veelvoud van a₁, ..., a_n. Dus l is element van V.
[2] l een element van V.
Volgens Stelling 2 is nu voor l en m : l = qm + r, waarbij 0 £ r < m
Nu geldt: m in V, dus qm in V, l in V, dus ook r = l - qm in V⁺;  immers r ³ 0).
Wegens r < m, terwijl m de kleinste van V⁺ is, moet dus gelden: r = 0.
Dus l = qm, zodat  m | l.¨

2.2.2 Gootste gemene deler

Bewijs:
1 is deelbaar op elke a_i. D⁺ is dus niet-leeg.
Het aantal delers van elke a_i is eindig. D⁺ is de doorsnede van een aantal eindige verzamelingen. Dus is D⁺ eveneens eindig.¨

Gevolg
De verzameling D⁺ heeft een grootste element.
Dit grootste element van D⁺ speelt een bijzondere rol (als ggd) in hetgeen volgt.
[einde Gevolg]

Bewijs:
Zij, bij gegeven getallen a₁, a₂, ..., a_n,  S de verzameling van alle getallen a van de vorm
   a = a₁x₁ + a₂x₂ + ... +a_nx_n
De verzameling S is niet-leeg, immers S bevat  |a₁|, met x₁ = sgn(a₁), x₂=x₃=...=x_n=0
De verzameling positieve getallen in S heeft dus een kleinste; stel d₀ is die kleinste.
Volgens Stelling 2 (delingsalgoritme) is er nu bij elke element m van S een q en een r zodat
   m = d₀q + r met r <d₀
Uit
   r = m - d₀q
   m = a₁x₁ + ... + a_nx_n
   d₀ = a₁y₁ + ... + a_ny_n
leiden we nu af:
   r = a₁(x₁ - qy₁) + ... +a_n(x_n - qy_n)
Dus r behoort eveneens tot S. Maar d₀ is het kleinste positieve getal, dus r = 0.
We vinden dus d₀ | m.
Daar m willekeurig is in S,  is d₀ dus eveneens deler van a_i (immers ai is element van S (x_j = 0 en x_i <> 0)
Volgens de definitie van d is nu
   d₀ £ d.
Uit d | a_i volgt d | d₀, zodat dus ook
   d £ d₀
Met andere woorden: d = d₀, waaruit de stelling volgt.¨

Bewijs:
[1]
Als d₁ | d, dan is, omdat d = ggd(a₁, ..., a_n), d₁ | a_i. Dus d₁ is gemeenschappelijke deler van a_i.
Stel nu dat d₁ gemeenschappelijke deler is van a_i.
Volgens Stelling 6 zijn er dan getallen x_i met d = a₁x₁ + ... + a_nx_n. Dus d₁ | d. ¨
[2]
We bewijzen met inductie.
De stelling is juist voor n = 2, immers d₂= (d₁, a₂) = (d₁, a₂).
Stel nu d_n = ggd(a₁, ..., a_n) , inductie-veronderstelling.
Zij verder e_n+1 = ggd(a₁, ..., a_n, a_n+1).
Omdat e_n+1 deelbaar is op a₁, ..., a_n+1, is e_n+1 ook deelbaar op a₁, ...,a_n.
Volgens Stelling 7.1 hebben we dan: e_n+1 | d_n.
Hieruit concluderen we dan e_n+1 | ggd(d_n, a_n+1); dat wil zeggen e_n+1 | d_n+1.
Maar er geldt ook
   d_n+1 | d_n en d_n+1 | a_n+1
Gebruiken we weer Stelling 7.1, dan zien we dat d_n+1 | a_i (met i  = 1, 2, ..., n+1), zodat dan
   d_n+1 | e_n+1
Dus d_n+1 = ggd(a₁, a₂, ..., a_n+1)
Waarmee door inductie stelling 7.2 bewezen is. ¨ 

In het bovenstaande hebben we nog steeds geen methode aangegeven om ggd(a₁, ..., a_n) te vinden.
Stelling 7.2 toont echter aan, dat het voldoende is de ggd van telkens twee van die getallen te bepalen.
In paragraaf 2.3 wordt een methode (de Euclidische algoritme) behandeld waarmee dit gedaan kan worden.

2.3. Euclidische algoritme

Bewijs:
We gaan (zonder de algemeenheid geweld aan te doen) uit van de positieve getallen a₁ en a₂ (waarbij a₂ £ a₁).
Volgens Stelling 2 zijn er dan getallen q₁ en a₃ zodat
   a₁ = a₂q₁ + a₃ met a₃ < a₂
Als a₃ = 0, dan a₂ | a₁, en dus a₂ = ggd(a₁, a₂)
Als a₃ > 0, dan zijn er (weer volgens Stelling 2) getallen q₂ en a₄ zodat
   a₂ = a₃q₂ + a₄ met a₄ < a₃
Op deze manier doorgaande vinden we de rij getallen
   a₁ > a₂ > a₃ > a₄ > ...
Deze rij van niet-negatieve getallen moet na een eindig aantal stappen afbreken.
Stel dat dit het geval is na r - 1 stappen. Dan is dus a_r ¹ 0 en a_r+1 = 0
De laatste twee stappen zijn dan
   a_r-2 = a_r-1q_r-2 + a_r met 0 < a_r < a_r-1 < .. .< a₁
   a_r-1 = a_rq_r-1
Nu is a_r = ggd(a₁, a₂), immers:
Het proces teruglezend, zien we dat
   a_r | a_r-1, a_r | a_r-2, ...,   a_r | a₂, a_r | a₁
Dus
   a_r | ggd(a₁, a₂)
Maar ook, lezend vanaf het begin van het proces:
   (a₁, a₂) | a₃, (a₁, a₂) | a₄ , ..., (a₁, a₂) | a_r
Dus a_r = ggd(a₁, a₂). ¨ 

Voorbeeld
We tonen aan, dat ggd(1147, 851) = 37
   
Dus ggd(1147, 851) = 37.
Uit het proces vinden we ook
   
De getallen x₁ en x₂, als bedoeld in Stelling 6, zijn dus x₁ = 3, x₂ = -4.
[einde Voorbeeld]

Opmerking
Een toepassing van de Euclidische algoritme is te vinden op de pagina "Kettingbreuken".
[einde Opmerking]

Bewijs:
Zij d = (a,b) en d₁ = (a + kb, b).
Dus is d | a en d | b, dus d | (a + kb), dus eveneens d | d₁.
Maar ook d₁ | (a + kb) en d₁ | b. Daaruit volgt, dat d₁ | (a + kb - kb), zodat d₁ | a.
Uit d₁ | a en d₁ | b volgt dan d₁ | d
Zodat d = d₁.¨ 

Opmerking
We kunnen natuurlijk ook zeggen
   ggd(a,b) = ggd(a - kb, b) = ggd(b, a - kb)

Gevolg
Op basis hiervan kunnen we op eenvoudige wijze een recursieve functie definieren die de ggd van twee getallen a en b berekent.
Als 1e voorbeeld in een programmeertaal (in dit geval UniComal)

FUNC ggd(a,b) CLOSED // 
  IF a MOD b=0 THEN  
    // a MOD b=0 betekent: a heeft rest 0 bij deling door b
    RETURN b
  ELSE
    RETURN ggd(b,a MOD b)
  ENDIF
ENDFUNC ggd

De opdracht

PRINT ggd(1147, 851) 

geeft als resultaat

37

Zie ook de pagina "UniComal".

Een tweede voorbeeld staat in een Maple-worksheet (merk op, dat de beschrijvung van de procedure ggd hierin veel overeenkomst vertoont met de hierboven staande FUNCtie).

> restart:
> ggd:=proc(a,b)
>   if a mod b = 0 then
>     RETURN (b)
>   else
>   RETURN (ggd(b, a mod b))
>   fi
> end:

> ggd(1147, 851);

37

Zie voor andere Maple-worksheets de pagina "Maple V".
[einde Opmerking en einde Gevolg]

3. Priemgetallen
Klik hier voor de definitie van priemgetal.

Bewijs:
Zij d de kleinste positieve deler van van n (maar wel groter dan 1).
Dan is d een priemgetal.
Stel dat dit niet zo is (veronderstelling), dan is d = d₁d₂ met 1 < d_i < d
Nu is bijvoorbeeld d₁ ook een deler van n, maar dit is in strijd met de definitie van d (als kleinste deler).
Dus de veronderstelling is onjuist. ¨ 

Bewijs:
We laten hieronder het bewijs volgen, zoals dat door Euclides (Euclides van Alexandrië, ~325 - ~265 vC) is gegeven als Propositie 20 van Boek IX van zijn Elementen.
Uiteraard bewijst Euclides deze stelling door gebruik te maken van lijnstukken die de getallen representeren. We zullen dat hier echter achterwege laten.

Zijn A, B, C priemgetallen.
Ik zeg nu dat er meer priemgetallen zijn dan A, B en C.
Zij D het kleinste getal, dat gemeten wordt door A,B,C. [dk: d = abc].
Laat de eenheid nu bij D worden opgeteld tot F [dk: we bekijken dus f = d+1 = abc +1]
Nu is F een priemgetal of niet.
Ten eerste, zij F een priemgetal; dan hebben we de priemgetallen A,B,C,F; en dat zijn er meer dan A,B,C.
Vervolgens, zij F geen priemgetal; dan moet het gemeten worden [dk: deelbaar zijn] door een priemgetal.
Laat het gemeten worden door het primegetal G.
Ik zeg nu, dat G niet hetzelfde is als de getallen A,B,C.
Maar we gaan ervan uit dat dit wel zo is.
A,B,C meten D; G meet D dus eveneens. Maar het [dk: G] meet ook F. G moet dus ook de eenheid meten. En dit is onzin.
Dus G valt niet samen met A,B,C; en volgens de veronderstelling is het een priemgetal.
Dus hebben we de priemgetallen A,B,C,G gevonden; en dat zijn er meer dan A,B,C.
Hetgeen bewezen moest worden. ¨ 

4. Hoofdstelling van de rekenkunde

Bewijs:
We gebruiken inductie.
De stelling is juist voor het getal 2.
(Inductie-veronderstelling) Stel de stelling is bewezen voor 2, 3 , 4, 5, 6 ..., n.
Beschouw nu het getal n+1.
Als n+1 een priemgetal is, dan is het gestelde juist.
Als n+1 geen priemgetal is, dan geldt n+1 = n₁n₂ (met 1 < n_i < n).
Volgens de inductie-veronderstelling kunnen n₁ en n₂ elk geschreven worden als een product van priemgetallen
Dus n+1 kan ook geschreven worden als een product van priemgetallen.
Het gestelde volgt nu via inductie.  ¨ 

Voordat we een zeer belangrijke stelling uit de Getallentheorie (de hoofdstelling van de rekenkunde) geven, bewijzen we eerst een

Bewijs:
[1]
Stel p is niet deelbaar op m. Dan is dus ggd(p,m) = 1. Volgens Stelling 6 zijn er dan getallen x en y, met
   px + my = 1
Dus geldt ook
   pxn + myn = n
Omdat p | mn, is er een getal k, zodat pk = mn. Uit de relatie in de vorige regel volgt dan
   n = pxn + pky = p (xn + ky).
En hieruit volgt p | n. ¨ 
[2]
Uit Hulpstelling 13.1 volgt nu onmiddellijk p | p₁ of p | (p₂...p_n).
Als p niet deelbaar is op p₁, dan geldt weer volgens Hulpstelling 13.1 : p | p₂ of p | (p₃...p_n).
Dus met een eindig aantal toepassingen van Hulpstelling 13.1 vinden we dat p | p_i voor zekere i.
Omdat p en p_i priem zijn, geldt p = p_i. ¨ 

Bewijs:
Stel dat
   n = p₁p₂...p_r = q₁q₂...q_s
waarin p₁, p₂, ..., p_r, q₁, q₂, ..., q_s priemgetallen zijn.
Stel ook dat deze getallen in de representatie van n niet-dalend geordend zijn.
We zullen nu aantonen, dat r = s en dat p_i = q_i.
We gebruiken inductie.
Het gestelde is juist voor n = 2.
Stel de bewering is juist voor 2, 3, 4, 5, ..., n-1 (inductie-veronderstelling).
Beschouw nu het getal n.
Als n priem is, dan is de stelling juist.
Als n niet-prime is, dan hebben we r > 1 en s > 1.
Volgens Hulpstelling 13.2 geldt nu q₁ = p_i (voor zekere i) en p₁ = q _j (voor zekere j).
Omdat nu (vanwege de ordening) p₁ £ p_i = q₁ £ q _j = p₁, vinden we (insluitend): p₁ = q₁.
Voor het gehele getal n / p₁ (met 1 < n/p₁ < n) geldt dan de schrijfwijze
   n/p₁ = p₂...p_r = q₂...q_s
Uit de inductie-veronderstelling volgt dan dat r = s en p_i = q _i (voor i = 2, ..., r)
Dus ook r = s en p_i = q _i (voor i = 1, ..., r).
Het gestelde volgt dus via inductie. ¨ 

Opmerkingen
[1] Uit Stelling 14 volgt dat een geheel getal n geschreven kan worden als

n =

waarin de getallen p_i primegetallen zijn met p₁ < p₂ < ...< p_r met positieve gehele exponenten a_i.
Deze uitdrukking heet wel de priemrepresentatie van n.
Als we de rij priemgetallen schrijven als p₁, p₂, ... ,  dan is

n =

waarin een eindig aantal exponenten a_i ongelijk aan 0 is.

[2] Een willekeurig geheel getal n kan nu worden geschreven als

n = ±

waarbij we het + teken gebruiken als n positief is, en het - teken als n negatief is.

[3] Als n een rationaal getal is (ongelijk aan 0 en ongelijk aan ±1), dan kan n geschreven worden als

n = ±

waarin de exponenten a_i positief of negatief zijn.
[einde Opmerkingen]

5. Functie van Euler (indicator van Euler)
We zullen in deze paragraaf iets zeggen over het aantal getallen dat relatief priem is met een gegeven getal n.

Voorbeeld
   f(1) =1, immers alleen (1,1) = 1
   f(2) = 1 = 2 -1, immers (1,1) = 1
   f(3) = 2 = 3 -1, immers (1,3)1= 1, (2,3) = 1
   f(4) = 2, omdat alleen (1,4) = 1 en (3,4) = 1
   f(5) = 4 = 5 - 1, omdat (1,5) = 1, (2,5) = 1, (3,5) = 1, (4,5) = 1
   f(6) = 2, omdat (1,6) = 1, (5,6) = 1
   f(7) = 6 = 7 -1 (!!)
   ....
[einde Voorbeeld]

Stelling 15 ALS    n = DAN   f(n) =

1e Bewijs:
Om f(n) te bepalen moeten tellen hoeveel natuurlijke getallen kleiner of gelijk aan n met n onderling ondeelbaar zijn.
Het aantal p₁-vouden onder de getallen 1, 2, ..., n is gelijk aan n/p₁.
Het aantal niet deelbaar is door p₁, is dus gelijk aan n - n/p₁ = n/p₁(p₁ - 1).
Het aantal getallen uit 1, 2, ..., n dat niet deelbaar is door p₁ en ook niet deelbaar is door p₂ is dan gelijk aan
   n/p₁(p₁ - 1) - n/(p₁p₂)(p₁ - 1) = n/(p₁p₂)(p₁ - 1)(p₂ - 2)
Zetten we dit proces voort tot we ook p_r hebben gehad, dan is dus
   f(n) = n/(p₁p₂...p _r) . (p₁ - 1)(p₂ - 1)...(p_r - 1) = n (1 - 1/p₁)(1 - 1/p₂)...(1 - 1/p_r) ¨ 

Voorafgaande aan een tweede bewijs vermelden we, zonder bewijs, de

2e Bewijs van Stelling 15:
Op basis van de hulpstelling kunnen we schrijven
   
We bekijken nu de factor met p_i.
De getallen uit de verzameling 1, 2, ..., p_i^ai die deelbaar zijn door p_i zijn:
   1p_i, 2p_i, 3p_i, 4p_i, ..., p_i^ai-1p_i
Dus zijn er p_i^ai -  p_i^ai-1p_i die onderling ondeelbaar zijn met p_i^ai.
Dus  f (p_i^ai ) = p_i^ai (1 - 1/p_i)
De stelling volgt nu uit de bovenstaande schrijfwijze (gebaseerd op de hulpstelling) van f(n). ¨ 

Opmerkingen
[1]
In het voorbeeld hebben we reeds gezien, dat voor een priemgetal p geldt
   f(p) = p - 1
Deze eigenschap volgt het eenvoudigst uit de finitie van f
Volgens Stelling 15 is f(p) = p(1 - 1/p) = p -1.
[2]
Voor toepassingen van de indicator van Euler, zie de paragraaf Gereduceerd restsysteem op de pagina "Congruenties".
[einde Opmerkingen]

[deelbaar.htm] laatste wijziging op: 12-01-2018