Fermat’s Little Theorem: Ό,τι πρέπει να ξέρεις με παραδείγματα

Εισαγωγή στο Μικρό Θεώρημα του Fermat

Το Μικρό Θεώρημα του Φερμά είναι ένα θεμελιώδες αποτέλεσμα στη θεωρία αριθμών που συνδέει δυνάμεις ακεραίων με την αριθμητική υπολοίπων (modulo). Διατυπώθηκε από τον Pierre de Fermat το 1640 και αποτελεί ειδική περίπτωση του γενικού Θεωρήματος του Euler.

Διατύπωση

Έστω \(p\) πρώτος και \(a\in\mathbb{Z}\) με \(\gcd(a,p)=1\) (δηλ. \(p\nmid a\)). Τότε

\(a^{p-1}\equiv 1\pmod{p}.\)

Πόρισμα

Για κάθε ακέραιο \(a\) (ανεξάρτητα αν \(p\mid a\) ή όχι):

\(a^{p}\equiv a\pmod{p}.\)

Σχόλια και συνδέσεις

• Ειδική περίπτωση του Θεωρήματος του Euler: αν \(\gcd(a,n)=1\), τότε \(a^{\varphi(n)}\equiv 1\pmod{n}\), όπου \(\varphi(n)\) η συνάρτηση του Euler. Για πρώτο \(p\): \(\varphi(p)=p-1\).
• Εξαιρετικά χρήσιμο για απλοποίηση μεγάλων δυνάμεων modulo· συχνά συνδυάζεται με το Κινέζικο Θεώρημα Υπολοίπων (Chinese remainder theorem).
• Κλασικές αποδείξεις: συνδυαστική μέτρηση (κολιέ), επαγωγή/διωνυμικός τύπος, και θεωρία ομάδων μέσω Lagrange (\((\mathbb{Z}/p\mathbb{Z})^\times\) έχει τάξη \(p-1\)).

Εφαρμογές

Απλοποιεί υπολογισμούς της μορφής \(a^{k}\bmod p\) αξιοποιώντας την «περιοδικότητα» του εκθέτη μήκους \(p-1\) όταν \(\gcd(a,p)=1\). Η ιδέα συνδέεται με τεχνικές που εμφανίζονται και σε κρυπτοσυστήματα δημοσίου κλειδιού (π.χ. RSA μέσω της μορφής του Euler).

Παραδείγματα

Παράδειγμα 1 — \(3^{31}\pmod{7}\).
Επειδή \(\gcd(3,7)=1\), έχουμε \(3^6\equiv 1\pmod{7}\). Γράφουμε \(31=5\cdot 6+1\) και:

\(3^{31}\equiv (3^6)^5\cdot 3 \equiv 1^5\cdot 3 \equiv \boxed{3}\pmod{7}.\)

Παράδειγμα 2 — \(29^{25}\pmod{11}\).
\(29\equiv 7\pmod{11}\), \(\varphi(11)=10\Rightarrow 7^{10}\equiv 1\). Άρα \(29^{25}\equiv 7^{25}=7^{20}\cdot 7^5\equiv 1\cdot 7^5\).

\(7^2\equiv 49\equiv 5,\quad 7^4\equiv 5^2\equiv 3,\quad 7^5\equiv 3\cdot 7\equiv 21\equiv \boxed{10}\pmod{11}.\)

Παράδειγμα 3 — \(128^{129}\pmod{17}\).
\(128\equiv 9\pmod{17}\), \(\varphi(17)=16\), και \(129\equiv 1\pmod{16}\).

\(128^{129}\equiv 9^{129}\equiv 9^{1}\equiv \boxed{9}\pmod{17}.\)

Παράδειγμα 4 — \(2^{20}+3^{30}+4^{40}+5^{50}+6^{60}\pmod{7}\).
Για \(\gcd(a,7)=1\) ισχύει \(a^6\equiv 1\pmod{7}\), και \(6\equiv -1\).

\(\begin{aligned} 2^{20}&\equiv (2^6)^3\cdot 2^2 \equiv 4,\\ 3^{30}&\equiv (3^6)^5 \equiv 1,\\ 4^{40}&\equiv (4^6)^6\cdot 4^4 \equiv (4^2)^2 \equiv 16^2 \equiv 2^2 \equiv 4,\\ 5^{50}&\equiv (5^6)^8\cdot 5^2 \equiv 25 \equiv 4,\\ 6^{60}&\equiv (6^6)^{10} \equiv 1. \end{aligned}\)

Άρα \(4+1+4+4+1=14\equiv \boxed{0}\pmod{7}.\)

Χρήσιμος κανόνας

Αν \(\gcd(a,p)=1\), τότε \(a^{k}\equiv a^{\,k \bmod (p-1)}\pmod{p}\). Αν \(p\mid a\), από το πόρισμα παίρνουμε άμεσα \(a^{p}\equiv a\pmod{p}\).