Soorten getallen > BewijzenVoorbeeld 4
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 Euclides.
Neem aan dat er een eindig aantal (
`n`
) priemgetallen is.
Noem die
`n`
priemgetallen:
`p_1`
,
`p_2`
, ...,
`p_n`
.
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`
.
De hoofdstelling van de rekenkunde stelt dat elk natuurlijk getal groter dan `1` één of meer priemdelers heeft. Dit betekent:
-
`a` is zelf een priemgetal
of
-
`a` heeft een priemdeler die niet in `p_1` , `p_2` , ..., `p_n` zit.
In beide gevallen heb je een nieuw priemgetal. De stelling dat er maar eindig priemgetallen zijn, is dus onjuist. Hieruit volgt dat er inderdaad oneindig veel priemgetallen zijn.
De volgende bewering ligt nogal voor de hand: "Als er tien duiven in negen duivenhokken zitten, is er minstens één duivenhok met minstens twee duiven."
Bewijs deze stelling indirect.
Formuleer de stelling algemener. De stelling staat bekend als het duivenhokkenprincipe.
Bewijs: Kies je uit de getallen `1, 2, ..., 10` zes getallen, dan zijn er zeker twee getallen bij die minstens `11` als som hebben.
In een zaal bevinden zich vijftig 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.
In
Waarom is hier sprake van een "bewijs uit het ongerijmde" ?
Bewijs dat elk getal te schrijven is als het product van priemgetallen.