Czym jest liczba pierwsza ?
Wszystkie liczby naturalne można podzielić na trzy typy.
Pierwsze to liczby pierwsze. Czym są liczby pierwsze nie trzeba chyba nikomu tłumaczyć. Definicja jest bardzo prosta: liczba pierwsza to taka liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i samą siebie.
Liczby, które nie są pierwsze, są złożone. Można je rozkładać na dwa lub więcej czynników pierwszych.
Wydawało by się, że coś jest nie tak bo przecież liczba jest albo pierwsza albo złożona, jednak liczbę 0 i 1 nie można zaliczyć ani do liczb pierwszych ani do złożonych.
Jednak co jest takiego ciekawego w tych liczbach pierwszych, że aż tyle się o nich mówi. Już Euklides z Aleksandrii w IX księdze Elementów w wieku III p.n.e. udowodnił, że wszystkich liczb pierwszych jest nieskończenie wiele.
Załóżmy, że zbiór liczb pierwszych jest ograniczony. Utwórzmy iloczyn tych wszystkich liczb. Do tego iloczynu dodajmy 1. Otrzymana liczba nie będzie się dzielić przez żadną liczbę z naszego zbioru liczb pierwszych, gdyż zawsze pozostanie reszta 1. Wynika z tego, że albo otrzymana liczba jest też liczbą pierwszą, albo dzieli się ona przez jakąś inną liczbę pierwszą, nie zawartą w naszym zbiorze liczb pierwszych. W obydwu przypadkach oznacza to, że otrzymujemy nową liczbę pierwszą, co jest sprzeczne z założeniem, że zbiór zawierał wszystkie liczby pierwsze.
Euklides również udowodnił podstawowe twierdzenie arytmetyki.
Każdą liczbę naturalną większą od 1, nie będącą liczbą pierwszą, można jednoznacznie przedstawić w postaci iloczynu liczb pierwszych.
Te twierdzenie wyklucza 1 jako liczbę pierwszą, ponieważ każdą z liczb złożonych można byłoby przedstawić na nieskończoną ilość sposobów np:
18 = 3 * 3 * 2 * 1
18 = 3 * 3 * 2 * 1 * 1
18 = 3 * 3 * 2 * 1 * 1 * 1
