Twierdzenie Euklidesa o liczbach pierwszych – twierdzenie mówiące, że istnieje nieskończenie wiele liczb pierwszych. Zostało ono po raz pierwszy udowodnione przez Euklidesa w jego traktacie Elementy. Istnieje co najmniej 200 dowodów tego twierdzenia.
Dowód Przeprowadźmy dowód nie wprost. Załóżmy, że liczb pierwszych jest skończenie wiele i można je wypisać jako . Rozważmy liczbę .
Sprawdźmy, co się dzieje przy dzieleniu przez dowolną liczbę pierwszą z naszej listy. Ponieważ dzieli iloczyn to .
Zatem żadna z liczb nie dzieli liczby .
Stąd wynika, że jest liczbą pierwszą lub nie zawiera wszystkich liczb pierwszych, więc jest ich nieskończenie wiele, q.e.d.
Przypisy
Kategoria:Twierdzenia teorii liczb Kategoria:Twierdzenia o liczbach pierwszych