Dukaz nekonecnosti prvocisel

Zajímavosti z teorie čísel 1

Myslím si, že by každý středoškolák (i základoškolák) měl znát definici provočísla. Pro jistotu ji zvopakuji. Prvočíslo p je každé přirozené číslo větší než 1, které má pouze dva dělitele: 1 a p.
Tedy prvočísla jsou např. 1, 2, 3, 5, 7, 11, 13, 17, 19, .... . Je asi jasné, že prvočísel je nekonečně mnoho. Jak to ale dokázat?

Důkaz není vůbec složitý. Provede se sporem. Předpokládejme, že prvočísel je konečně mnoho, tedy p₁, p₂, ... , p_n. Pak číslo

není dělitelné žádným z čísel p_i , kde i = 1, ... , n, neboť při dělení je vždy zbytek 1. To znamená, že toto číslo je buď prvočíslem nebo je dělitelné nějakým dalším prvočíslem, které je větší než p_n. Což je spor s předpokladem, takže prvočísel je nekonečně mnoho.