Małe twierdzenie Fermata

Jeżeli $p$ jest liczbą pierwszą, to dla każdej liczby całkowitej $a$ liczba $a^p - a$ jest podzielna przez $p$.

Dowód. Niech $p$ będzie liczbą pierwszą. Dla $a = 1$ twierdzenie jest prawdziwe. Załóżmy, że twierdzenie jest prawdziwe dla dowolnej liczby naturalnej $a$. Korzystając ze wzoru Newtona, mamy: $(a+1)^p = a^p + \binom{p}{1}a^{p-1} + \binom{p}{2}a^{p-2} + \ldots + \binom{p}{p-1}a + 1$. Dla $k = 1, 2, \ldots, p-1$ mamy $\binom{p}{k} = \frac{p(p-1)(p-2)\ldots (p-k+1)}{k!}$. Liczby $\binom{p}{k}$ są całkowite, zatem liczba $k! \cdot \binom{p}{k}$ jest podzielna przez $p$. Wobec $k \lt p$ współczynnik dwumianowy $\binom{p}{k}$ jest podzielny przez $p$, stąd liczba $(a+1)^p - a^p - 1$ jest podzielna przez $p$. Dodając do tej liczby liczbę $a^p - a$, podzielną przez $p$, otrzymujemy liczbę $(a + 1)^p - (a + 1)$ podzielną przez $p$. Twierdzenie jest prawdziwe dla liczby $a+1$, zatem na mocy zasady indukcji, jest prawdziwe dla każdej liczby naturalnej $a$.

Z małego twierdzenia Fermata wynika, że jeżeli $p$ jest liczbą pierwszą, to $1^p-1 + 2^{p-1} + \ldots + + (p-1)^{p-1} + 1$ jest podzielna przez $p$.

Kryterium Fermata dla liczb pierwszych

Fermat pokazał, że każda nieparzysta liczba pierwsza $p$ musi spełniać $p|a^{p-1} - 1$, jeśli $a$ jest niepodzielna przez $p$. Jeśli liczba nie spełnia tego warunku, nie może być liczbą pierwszą.