Bewijzen

Inleiding

Je leert nu:

• het begrip bewijs (weer?) kennen;
• directe bewijzen en bewijzen uit het ongerijmde leveren;
• de begrippen implicatie en equivalentie.

Je kunt al:

• rekenen met getallen in het tientallig stelsel;
• haakjes uitwerken en ontbinden in factoren.

Verkennen

Als a een oneven geheel getal is, dan is a² – 1 deelbaar door 8.

> Ga dit eerst eens na voor een aantal gehele getallen.
> Waarom heb je dan nog geen bewijs?
> Probeer dit eens te bewijzen.

Uitleg

Je zit een middagje wat te spelen met kwadraten van oneven getallen:
1² = 1
3² = 9 = 8 – 1
5² = 25 = 24 – 1
7² = 49 = 48 – 1
enzovoorts.
Je krijgt het vermoeden:

Maar is dat nu ALTIJD waar, dus voor ELK oneven getal?
Je zoekt een bewijs, een redenering die iedereen wel moet overtuigen, die waterdicht is.

Je bedenkt: a = 2n + 1, want oneven.
Dan is: a² – 1 = (2n + 1)² – 1 = 4n² + 4n = 4(n² + n).
Dus is a² – 1 in ieder geval een viervoud. Maar een achtvoud...?

Hopelijk zie je dat a² – 1 = 4(n² + n) = 4n(n + 1).
En nu is ofwel n een even getal, ofwel zijn opvolger n + 1 is dat.
Dus n(n + 1) is deelbaar door 2.
En nu is a² – 1 deelbaar door 4 · 2, dus door 8.

Q.e.d.

Mooi hè, zo'n bewijs.
Q.e.d. staat voor "quod erad demonstrandum" (Latijn voor "wat te bewijzen was") en sluit traditiegetrouw een bewijs af.

Een paar opmerkingen nog:

• Het gegeven bewijs was een direct bewijs: uitgaande van de eigenschappen van een oneven getal heb je het vermoeden bewezen.
• Het vermoeden is nu een stelling geworden.
• Het is een stelling van de vorm "Als..., dan...".
  Je noemt dat een implicatie en je gebruikt er wel een kortere schrijfwijze voor:
  a is oneven  $\Rightarrow$ a² – 1 is deelbaar door 8.

Er bestaan ook indirecte bewijzen.
Daarbij ga je er van uit dat het vermoeden NIET geldig is en daaruit leid je een tegenspraak af, iets wat onmogelijk waar kan zijn.

‡

Opgaven

1. Bekijk de stelling die in de Uitleg wordt geformuleerd. Er is ook een heel ander bewijs van deze stelling mogelijk.
   1. Ontbind `a^2 - 1` in factoren.
   2. Leg uit waarom beide factoren even getallen zijn.
   3. Leg uit waarom één van die twee factoren een viervoud is.
   4. Bewijs hiermee de stelling.



Bekijk het getal x = 1. Vat de vorige uitdrukking op als vergelijking. Trek aan beide zijden x2 af. Je krijgt: x – x2 = 1 – x2. Ontbinden: x(1 – x) = (1 + x)(1 – x). Beide zijden delen door (1 – x) geeft x = 1 + x. Omdat x = 1 wordt dit 1 = 1 + 1 = 2.

2. Je ziet hiernaast een "bewijs", namelijk het bewijs dat 1 = 2.
   Waar zit de fout in de redenering?
   


3. Als `n * m` oneven is, dan zijn zowel `n` als `m` oneven.
   Onderzoek of dit waar is en zo ja, probeer dan een bewijs te vinden.
   

Theorie

Als je op zoek bent naar eigenschappen van getallen vind je vaak door proberen wel bepaalde regelmaat. Je krijgt dan een vermoeden. Veel vermoedens hebben de vorm "als A, dan B".
Bijvoorbeeld: als a² even is, dan is a ook even.
Je spreekt dan van een implicatie en je schrijft: a² is even ⇒ a is even.
Maar om zeker te weten of dit vermoeden altijd geldig is moet je een redenering geven die dit onomstotelijk aantoont. Dat heet een bewijs.
Er zijn verschillende soorten bewijzen:

• Een direct bewijs:
  Je laat dan door een waterdichte redenering zien dat bewering B inderdaad uit A volgt en dus dat de waarheid van A ook betekent dat B waar is.
• Een indirect bewijs of een bewijs uit het ongerijmde:
  Je gaat nu uit van de onwaarheid van B en je laat zien dat A dan ook onmogelijk waar kan zijn. Dat is een tegenspraak omdat de waarheid van A al vast staat en dus de onwaarheid van B niet kan kloppen: B moet waar zijn.

Verder zijn er verschillende soorten argumenten: soms gebruik je algebraïsche methoden, soms gebruik je figuren en meetkundige methoden, van alles is denkbaar.

Wanneer zowel "als A, dan B" en "als B, dan A" waar zijn, dan zijn A en B gelijkwaardige beweringen, ze zijn equivalent. Je schrijft dan: A ⇔ B.
Er zijn dan twee bewijzen nodig, één voor A ⇒ B en één voor B ⇒ A.

‡

Voorbeeld 1

Bewijs: a² is even $\iff$ a is even.

Antwoord

Dit zijn eigenlijk twee stellingen die allebei moeten worden bewezen:

• Als a een even getal is, dan is a² ook even.
  Het bewijs hiervan vind je bij 11: Gehele getallen, Voorbeeld 2.
• Als a² een even getal is, dan is a ook even.
  Het bewijs is eenvoudig: als a² is even, dan zijn er voor a twee mogelijkheden, namelijk a is even of a is oneven. In 11: Gehele getallen, Voorbeeld 2 is echter bewezen dat het kwadraat van elk oneven getal ook oneven is, dus kan a niet oneven zijn.

Q.e.d.

‡

Voorbeeld 2

Bewijs: n is deelbaar door 2 en door 3 $\iff$ n is deelbaar door 6.

Antwoord

n is deelbaar door 2 betekent: n = 2 · p.
n is ook deelbaar door 3 betekent (omdat 2 niet deelbaar is door 3) dat p deelbaar is door 3: p = 3 · q. En daarom is: n = 2 · 3 · q = 6 · q.
En dus is n deelbaar door 6.

Omgekeerd:
n is deelbaar door 6 betekent: n = 6 · q = 2 · 3 · q.
En dit betekent dat n deelbaar is door zowel 2 als 3.

Q.e.d.

‡

Voorbeeld 3

Bewijs dat er oneindig veel priemgetallen zijn.
(Het hier gegeven bewijs is een klassiek voorbeeld van een bewijs uit het ongerijmde. Het is afkomstig van Euklides.)

Antwoord

Neem eens aan dat er NIET oneindig veel priemgetallen zijn, maar niet meer dan n.
Noem die n priemgetallen: p₁, p₂, ..., p_n in opklimmende volgorde.

Bekijk nu het getal a = p₁ · p₂ · p₃ · ... · p_n + 1.
Dit getal is groter dan elk van de n priemgetallen.
Als je dit getal deelt door p₁, of p₂, of ..., of p_n, dan blijft er steeds een rest van 1 over. Dus a is niet deelbaar door één van de priemgetallen p₁, p₂, ..., p_n. Omdat elk getal te schrijven is als het product van priemgetallen (een stelling die je eigenlijk eerst nog moet bewijzen) is dit getal zelf een priemgetal.

Het getal a is een priemgetal dat groter is dan p₁, p₂, ..., p_n en dus een nieuw priemgetal. Maar dat is in strijd met de aanname dat er maar n zijn.
De stelling dat er maar eindig priemgetallen zijn is dus onwaar. Hieruit volgt dat er inderdaad oneindig veel priemgetallen zijn.

‡

Opgaven

4. In Voorbeeld 1 wordt de gelijkwaardigheid bewezen van `a^2` is even en `a` is even.
   1. Over welke twee stellingen heb je het dan?
   2. Bewijs nu zelf: `a^2` is oneven `hArr` `a` is oneven.
   3. Bewijs de juistheid, of toon met een tegenvoorbeeld de onjuistheid aan van de bewering: `a^2` is drievoud `hArr` `a` is drievoud.


5. Bekijk het bewijs in Voorbeeld 2. Als een getal deelbaar is door 12, dat is het ook deelbaar door 3 en deelbaar door 4.
   1. Bewijs dat dit waar is.
   2. Formuleer het omgekeerde van deze stelling en bewijs dat die ook waar is.
   3. Formuleer deze stelling en zijn omgekeerde als één stelling.
   Als een getal deelbaar is door 12, dan is het ook deelbaar door 2 en door 6.
   4. Bewijs dat dit waar is.
   5. Formuleer het omgekeerde van deze stelling en bewijs dat die stelling niet waar is.
   6. Kun je een algemene stelling formuleren en bewijzen?


6. In Voorbeeld 3 zie je het bewijs van Euklides dat er oneindig veel priemgetallen zijn.
   1. Waarom is hier sprake van een "bewijs uit het ongerijmde"?
   2. Bewijs dat elk niet priem getal is te schrijven als het product van priemgetallen. Zie ook opgave 8 van het onderdeel "Gehele getallen".


7. De volgende bewering ligt nogal voor de hand: "Als er 10 duiven in 9 duivenhokken zitten, is er minstens één duivenhok met 2 duiven."
   1. Bewijs de bovenstaande stelling indirect.
   2. Formuleer de stelling algemener. Hij staat bekend als het duivenhokkenprincipe.
   3. Bewijs: Kies je uit de getallen 1, 2, ..., 10 er zes, dan zijn er zeker twee getallen bij die 11 als som hebben.
   4. In een zaal bevinden zich 50 mensen. Ze kennen allemaal wel één of meer van de anderen in de zaal, maar hoeveel precies is onbekend. Bewijs dat er twee mensen in de zaal zijn, die hetzelfde aantal kennissen in de zaal hebben.


8. Lees na wat wordt verstaan onder de grootste gemeenschappelijke deler van twee getallen in

   www.math4all.nl > MAThADORE-basic HAVO/VWO > 4/5/6 VWO wi-d > Getaltheorie > Soorten getallen > Totaalbeeld > Toepassingen

   Je kunt de GGD van twee getallen berekenen door ze in priemfactoren te ontbinden.
   1. Bereken GGD(140,504).
   2. Bereken GGD(143,2541).
   3. Hoeveel is GGD(`a,0`)?
   4. Hoeveel bedraagt de GGD van twee priemgetallen?
   Een andere manier om de GGD van twee getallen `a` en `b` te vinden is het algoritme van Euklides. Lees na wat hieronder wordt verstaan.
   5. Bewijs dat uit `a - q * b = r` volgt dat GGD(`a,b`) = GGD(`b,r`).
   6. Bereken nu op deze manier GGD(140,504).
   7. Bereken met behulp van het algoritme van Euklides GGD(143,2541).
   8. Een kangoeroe hopt over de getallenlijn. Hij start in 0 en kan naar links en naar rechts springen. Zijn sprongen hebben een lengte van 39 of 220. Toon aan dat hij het getal 1 kan bereiken en bepaal ook hoe.

Verwerken

9. Bewijs dat `(n^3 - n)^2` voor elk natuurlijk getal `n` deelbaar is door 9.
   


10. Je wilt bewijzen dat `n^5 - n` voor elk natuurlijk getal `n` deelbaar is door 30.
    1. Toon aan dat van elke drie opeenvolgende natuurlijke getallen er altijd ééntje even is en een andere een drievoud is.
    2. Bewijs nu de bewering hierboven.


11. Wat is er fout in de volgende redenering?
    
    

    Je weet dat n2 = n · n = n + n + ... + n (n keer n optellen). Als f(n) = n2, dan is f'(n) = 2n. Maar f(n) = n + n + ... + n (n keer n optellen) en heeft dus als afgeleide f'(n) = 1 + 1 + ... + 1 (n keer 1 optellen). In het eerste geval is f'(1) = 2 en in het tweede getal is f'(1) = 1.

    
    


12. Onder het kleinste gemeenschappelijke veelvoud (KGV) van twee getallen `a` en `b` versta je het kleinste getal dat deelbaar is door zowel `a` als `b`. Je kun het KGV van twee getallen berekenen door ze in priemfactoren te ontbinden.
    1. Hoeveel bedraagt KGV(5,7)? En KGV(10,15)?
    2. Bereken KGV(140,504)
    3. Hoeveel bedraagt de KGV van twee priemgetallen `p` en `q`?
    4. Bewijs dat KGV(`a,b`) = `(a * b)/(text(GGD)(a,b))`.

Testen

13. Bewijs of toon de onjuistheid aan van de bewering: `a` is oneven `hArr` `a^3` is oneven.
    


14. Gegeven zijn de getallen 33 en 91.
    1. Bereken de GGD van beide getallen.
    2. Bereken de KGV van beide getallen.
    3. Een kangoeroe springt vanuit 0 over de getallenlijn met sprongen van 33 of 91 naar links of naar rechts. Bepaal hoe deze kangoeroe op 1 kan uitkomen.


15. Bewijs dat een geheel getal deelbaar is door 3 als de som van zijn cijfers deelbaar is door 3.