Nieskończoność zbioru liczb pierwszych
Dowód na nieskończoność zbioru liczb pierwszych (Dowód Euklidesa)
Dowiedziemy, że istnieje nieskończenie wiele liczb pierwszych, korzystając z dowodu nie wprost (przez zaprzeczenie), który został przedstawiony przez #Euklides około 300 r. p.n.e.
Krok 1: Założenie przeciwne
Załóżmy, że zbiór liczb pierwszych jest skończony. Oznacza to, że istnieje tylko pewna skończona liczba liczb pierwszych:
[math]p_1,p_2,p_3,…,p_n[/math]
gdzie każda liczba [math]p_i[/math] jest liczbą pierwszą.
Krok 2: Konstrukcja nowej liczby
Rozważmy liczbę N zdefiniowaną jako:
[math]N=p_1⋅p_2⋅p_3⋅…⋅p_n+1[/math]
Jest to liczba otrzymana poprzez pomnożenie wszystkich liczb pierwszych i dodanie liczby 1.
Krok 3: Analiza podzielności
Liczba N nie jest podzielna przez żadną z liczb pierwszych [math]p_1,p_2,…,p_n[/math] Dlaczego?
Jeśli podzielimy N przez dowolne [math]p_i, to otrzymamy resztę 1, bo N mod p_i = 1[/math]
co oznacza, że żadna z liczb [math]p_i[/math] nie jest dzielnikiem N.
Krok 4: Sprzeczność
Jeśli N jest liczbą pierwszą, to znaleźliśmy nową liczbę pierwszą, której nie było w naszym pierwotnym skończonym zbiorze. To sprzeczność z założeniem, że wszystkie liczby pierwsze były już znane.
Jeśli NNN nie jest liczbą pierwszą, to musi mieć przynajmniej jeden dzielnik pierwszy. Ale ten dzielnik nie może być żadnym z [math]p_1,p_2,…,p_n[/math] (bo każda z nich daje resztę 1 przy dzieleniu).
W takim razie istnieje inna liczba pierwsza, której nie było w naszym początkowym zbiorze. To również sprzeczność.
Krok 5: Wniosek
Ponieważ nasze założenie o skończoności zbioru liczb pierwszych prowadzi do sprzeczności, musi być błędne. Zatem liczba liczb pierwszych musi być nieskończona. Istnieje nieskończenie wiele liczb pierwszych.
Podsumowanie
#Dowód Euklidesa jest jednym z najprostszych i najpiękniejszych dowodów matematycznych. Pokazuje, że każda skończona lista liczb pierwszych zawsze pozwala skonstruować nową liczbę pierwszą, co oznacza, że nigdy nie możemy wymienić wszystkich liczb pierwszych – jest ich nieskończenie wiele!
