Již před přibližně 2300 lety dokázal slavný matematik Eukleides, že existuje nekonečně mnoho prvočísel. Učinil tak ve dvacáté poučce v deváté knize svého slavného díla "Základy". Onen opravdu chytrý Řek došel ke svému důkazu následujícím postupem.

Řekněme, že existuje pouze konečný počet prvočísel a že největší z nich je prvočíslo p.

Nyní si představme číslo 2 x 3 x 4 x ...x p +1 .

Takové číslo získáme vzájemným vynásobením všech čísel až po p včetně a přičtením jedničky. Nazvěme jej q.

Prozkoumejme nyní toto číslo q. Není dělitelné 2, neboť při dělení číslem dostaneme zbytek 1 pocházející ze závěrečného přičtení jedničky. Podobně však není dělitelné ani třemi, čtyřmi či pěti – a ani žádným jiným číslem až po p, neboť pokaždé nám zůstane onen zbytek 1.

V takovém případě musí platit jedna ze dvou možností:

– Buď existuje prvočíslo větší než p, kterým lze dělit číslo q,

– anebo je samotné q oním prvočíslem.

Oba případy vedou k závěru, že p nemůže být nejvyšším prvočíslem. Předpoklad, že ono větší prvočíslo existuje, odporuje výchozímu tvrzení. Musí proto existovat nekonečné množství prvočísel.