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 daną liczbą pierwszą. Dla a = 1 twierdzenie jest prawdziwe. Zakłóżmy, że twierdzenie jest prawdziwe dla dowolnej liczby naturalnej a. Korzystając ze wzoru Newtona, mamy:
${(a + 1)}^{p} = a^{p} + (\begin{matrix} p \\ 1 \end{matrix}) a^{p - 1} + (\begin{matrix} p \\ 2 \end{matrix}) a^{p - 2} + ... + (\begin{matrix} p \\ p - 1 \end{matrix}) a + 1$ ,
gdzie dla k = 1, 2, ..., p-1 mamy $(\begin{matrix} p \\ k \end{matrix}) = \frac{p (p - 1) (p - 2) ... (p - k + 1)}{k!}$ . Liczby $(\begin{matrix} p \\ k \end{matrix})$ są całkowite, więc liczba $k! \cdot (\begin{matrix} p \\ k \end{matrix})$ jest podzielna przez p. Wobec k < p współczynnik dwumianowy $(\begin{matrix} p \\ k \end{matrix})$ 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, czyli, że twierdzenie jest prawdziwe dla liczby a + 1. Zatam na mocy zasady indukcji twierdzenie 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 + ... + (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ć: a^p-1 - 1 jest podzielne przez p, jeśli a jest niepodzielna przez p. Jeśli liczba nie spełnia tego warunku, nie może być liczbą pierwszą.