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.)
Neem eens aan dat er NIET oneindig veel priemgetallen zijn, maar niet meer dan
`n`
.
Noem die 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 priemgetallen.
Als je dit getal deelt door
`p_1`
, of
`p_2`
, of ..., of
`p_n`
, dan blijft er steeds een rest van over. Dus 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 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 zijn.
De stelling dat er maar eindig priemgetallen zijn is dus onwaar. Hieruit volgt dat
er inderdaad oneindig veel priemgetallen zijn.
In
Waarom is hier sprake van een "bewijs uit het ongerijmde"?
Bewijs dat elk getal is te schrijven als het product van priemgetallen.
De volgende bewering ligt nogal voor de hand: "Als er duiven in duivenhokken zitten, is er minstens één duivenhok met 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 als som hebben.
In een zaal bevinden zich 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.
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 en 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 en kan naar links en naar rechts springen. Zijn sprongen hebben een lengte van of `220` . Toon aan dat hij het getal kan bereiken en bepaal ook hoe.