Μικρό Θεώρημα του Fermat

Θεώρημα

$𝑝$ πρώτος, $𝑝$ δεν διαιρεί το $𝑎$, τότε $𝑎^{𝑝−1} − 1$ είναι πολλαπλάσιο του $𝑝$. Αντίστοιχα χωρίς περιορισμούς στο $𝑎$: $𝑎^𝑝 − 𝑎$ είναι πολλαπλάσιο του $𝑝$.

Απόδειξη (Euler)

• Όταν $𝑎 = 1$, απλό.

• Έστω αληθές όταν $𝑎 = 𝑘$: $𝑘^𝑝 − 𝑘 = 𝑝𝑡$,$𝑡 ∈ ℕ$.

• Έστω τώρα $𝑎 = 𝑘 + 1$. 

Τότε

$(𝑘 + 1)^𝑝 − (𝑘 + 1) = $

$=(𝑘^𝑝 + 𝑝𝑚 + 1) − (𝑘 + 1) = (𝑘^𝑝 − 𝑘) + 𝑝𝑚 = 𝑝(𝑡 + 𝑚)$

Πηγή: opencourses.auth