🔢 Το Μικρό Θεώρημα του Fermat — Από τους τέλειους αριθμούς στους ψευδοπρώτους

Μία από τις πιο γνωστές προτάσεις της Θεωρίας Αριθμών χωρά σε μία μόνο γραμμή.

Αν \(p\) είναι πρώτος αριθμός και \(a\) οποιοσδήποτε ακέραιος, τότε

\[ \boxed{a^p\equiv a\pmod p}. \]

Αν επιπλέον \(p\nmid a\), η σχέση γράφεται στην περισσότερο γνωστή μορφή

\[ \boxed{a^{p-1}\equiv1\pmod p}. \]

Πρόκειται για το Μικρό Θεώρημα του Fermat. Πίσω όμως από αυτή την απλή πρόταση ξεδιπλώνεται μια ολόκληρη ιστορία με τέλειους αριθμούς, αριθμούς Fermat, το θεώρημα του Euler και ψευδοπρώτους αριθμούς.

📜 Η αρχική ιδέα του Fermat

Ο Fermat παρατήρησε ότι αν \(p\) είναι πρώτος, τότε

\[ 2^p\equiv2\pmod p. \]

Η ιδέα αυτή γενικεύτηκε στη σημερινή μορφή του θεωρήματος και εξελίχθηκε σε ένα από τα βασικότερα εργαλεία της αριθμητικής modulo \(p\).

✨ Μια απλή απόδειξη

Αν \(p\) είναι πρώτος, από το διωνυμικό θεώρημα έχουμε

\[ (a+1)^p = a^p+ \binom p1a^{p-1}+ \binom p2a^{p-2} +\cdots+1. \]

Για

\[ 1\le k\le p-1, \]

ο διωνυμικός συντελεστής

\[ \binom pk \]

είναι διαιρετός από το \(p\). Επομένως

\[ (a+1)^p\equiv a^p+1\pmod p. \]

Με επαγωγή προκύπτει

\[ a^p\equiv a\pmod p. \]

🔄 Η γενίκευση του Euler

Η ιδέα του Fermat επεκτείνεται και όταν το modulus δεν είναι πρώτος.

Αν

\[ \gcd(a,n)=1, \]

τότε το Θεώρημα του Euler δίνει

\[ \boxed{ a^{\varphi(n)}\equiv1\pmod n }, \]

όπου \(\varphi(n)\) είναι η συνάρτηση του Euler, δηλαδή το πλήθος των θετικών ακεραίων μικρότερων ή ίσων του \(n\) που είναι πρώτοι προς το \(n\).

💡 Το Μικρό Θεώρημα του Fermat ως ειδική περίπτωση

Αν \(n=p\) είναι πρώτος, τότε \[ \varphi(p)=p-1, \] οπότε το Θεώρημα του Euler γίνεται ακριβώς \[ a^{p-1}\equiv1\pmod p. \]

🔺 Μια σύνδεση με τους τέλειους αριθμούς

Το θεώρημα εμφανίζεται φυσικά και στη μελέτη των άρτιων τέλειων αριθμών.

Ένας θετικός ακέραιος ονομάζεται τέλειος όταν ισούται με το άθροισμα των γνήσιων θετικών διαιρετών του. Για παράδειγμα:

\[ 6=1+2+3 \]

και

\[ 28=1+2+4+7+14. \]

Η κλασική μορφή των άρτιων τέλειων αριθμών είναι

\[ \boxed{2^{p-1}(2^p-1)}, \]

όταν ο \(2^p-1\) είναι πρώτος.

Από το Μικρό Θεώρημα του Fermat προκύπτουν ισχυροί περιορισμοί στους πιθανούς πρώτους διαιρέτες αριθμών της μορφής \(2^p-1\).

🌟 Οι αριθμοί του Fermat

Μια δεύτερη ιστορία ξεκινά από τους αριθμούς

\[ F_n=2^{2^n}+1. \]

Οι πρώτες τιμές είναι:

\[ 3,\quad5,\quad17,\quad257,\quad65537. \]

Όλοι αυτοί είναι πρώτοι και ο Fermat πίστεψε ότι ίσως το ίδιο συμβαίνει για κάθε \(n\).

Όμως ο Euler έδειξε ότι ήδη

\[ F_5=2^{32}+1=4294967297 \]

δεν είναι πρώτος:

\[ \boxed{ 4294967297=641\cdot6700417 }. \]

🎭 Όταν ένας σύνθετος αριθμός προσποιείται τον πρώτο

Θα μπορούσε άραγε το Μικρό Θεώρημα του Fermat να χρησιμοποιηθεί αντίστροφα ως τέλειο τεστ πρώτων αριθμών;

Δυστυχώς όχι.

Υπάρχουν σύνθετοι αριθμοί \(n\) για τους οποίους, για κάποια βάση \(a\) πρώτη προς το \(n\), ισχύει παρ' όλα αυτά

\[ a^{n-1}\equiv1\pmod n. \]

Τέτοιοι αριθμοί ονομάζονται ψευδοπρώτοι ως προς τη βάση \(a\).

Ένα κλασικό παράδειγμα στη βάση \(2\) είναι ο

\[ 341=11\cdot31, \]

ο οποίος είναι σύνθετος, αλλά ικανοποιεί

\[ 2^{340}\equiv1\pmod{341}. \]

🤔 Άρα ποιο είναι το μάθημα;

Αν ένας αριθμός αποτύχει στο τεστ του Fermat, γνωρίζουμε ότι είναι σύνθετος. Αν όμως περάσει το τεστ, αυτό από μόνο του δεν αποδεικνύει ότι είναι πρώτος. Αυτή η λεπτή διαφορά οδηγεί σε πολύ βαθύτερες ιδέες της Θεωρίας Αριθμών.

🧩 Ένα όμορφο πρόβλημα

Έστω \(p\) περιττός πρώτος αριθμός. Επιλέγουμε οποιουσδήποτε

\[ 2p-1 \]

ακεραίους.

Να αποδειχθεί ότι μπορούμε πάντοτε να βρούμε \(p\) από αυτούς των οποίων το άθροισμα είναι διαιρετό από το \(p\).

💡 Εμφάνιση υπόδειξης

Μην προσπαθήσεις να κατασκευάσεις άμεσα το κατάλληλο υποσύνολο.

Σκέψου πόσα διαφορετικά υποσύνολα με \(p\) στοιχεία υπάρχουν και προσπάθησε να χρησιμοποιήσεις το Μικρό Θεώρημα του Fermat μαζί με ένα επιχείρημα καταμέτρησης.

Εδώ βλέπουμε κάτι ιδιαίτερα όμορφο: ένα θεώρημα modular αριθμητικής μπορεί να χρησιμοποιηθεί μέσα σε ένα συνδυαστικό επιχείρημα.

🔍 Μία μικρή πρόταση, πολλές ιστορίες

Το Μικρό Θεώρημα του Fermat συνδέεται με τέλειους αριθμούς, αριθμούς Mersenne και Fermat, το Θεώρημα του Euler, τεστ πρώτων αριθμών, ψευδοπρώτους και συνδυαστικά προβλήματα. Είναι χαρακτηριστικό παράδειγμα μιας απλής ιδέας που ανοίγει πολλές διαφορετικές πόρτες στη Θεωρία Αριθμών.

\[ a^{p-1}\equiv1\pmod p \] Μία μικρή εξίσωση — και πίσω της ένας ολόκληρος κόσμος αριθμών.

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →