Soorten getallen

Soorten getallen > Bewijzen

123456Bewijzen

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_1` , `p_2` , ..., `p_n` in opklimmende volgorde.

Bekijk nu het getal `a = p_1 * p_2 * p_3 * ... * p_(n) + 1` .
Dit getal is groter dan elk van de $n$ priemgetallen.
Als je dit getal deelt door `p_1` , of `p_2` , of ..., of `p_n` , dan blijft er steeds een rest van $1$ over. Dus $a$ is niet deelbaar door één van de priemgetallen `p_1` , `p_2` , ..., `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_1` , `p_2` , ..., `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.

Opgave 7

In Voorbeeld 3 zie je het bewijs van Euklides dat er oneindig veel priemgetallen zijn.

Waarom is hier sprake van een "bewijs uit het ongerijmde"?

Bewijs dat elk getal is te schrijven als het product van priemgetallen.

Opgave 8

De volgende bewering ligt nogal voor de hand: "Als er $10$ duiven in $9$ duivenhokken zitten, is er minstens één duivenhok met $2$ duiven."

Bewijs de bovenstaande stelling indirect.

Formuleer de stelling algemener. Hij staat bekend als het duivenhokkenprincipe.

Bewijs: Kies je uit de getallen `1, 2, ..., 10` er zes, dan zijn er zeker twee getallen bij die $11$ als som hebben.

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.

Opgave 9

De GGD (grootste gemeenschappelijke deler) van twee getallen `a` en `b` is het grootste (gehele) getal `u` waarvoor geldt `a = m * u` en `b = n * u` .
Dit getal kun je vinden door een getal te ontbinden in priemfactoren. Dat doe je door het te delen door de priemgetallen `2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31` , etc., tot het niet meer gaat (en er dus een priemgetal als rest overblijft).
Bijvoorbeeld is `132 = 2^2 * 3 * 11` en `96 = 2^5 * 3` . De GGD van `132` en `96` is daarom `2^2 * 3 = 12` .

Bereken `text(GGD)(140,504)` .

Bereken `text(GGD)(143,2541)` .

Hoeveel is `text(GGD)(a,0)` ?

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. Daarbij maak je gebruik van de eigenschap die je hier bewijst.

Bewijs dat uit `a - q * b = r` volgt dat `text(GGD)(a,b) = text(GGD)(b,r)` .

Bereken nu op deze manier `text(GGD)(140,504)` .

Bereken met behulp van het algoritme van Euklides `text(GGD)(143,2541)` .

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.

verder | terug