Θεώρημα Ουίλσον

Στην θεωρία αριθμών, το θεώρημα Ουίλσον (αναφέρεται και ως θεώρημα Wilson) λέει ότι ένας φυσικός αριθμός ${\displaystyle p}$ είναι πρώτος ανν ισχύει ότι^{[1]:111-112[2]:68-69[3]:40-41[4]:132-133[5]:55[6]:69-70[7]}

${\displaystyle (p-1)!\equiv p-1\mod {p}}$,

όπου ${\displaystyle (p-1)!=1\cdot 2\cdot 3\cdot \ldots \cdot (p-1)}$ είναι το παραγοντικό του ${\displaystyle p-1}$.

Δηλαδή το θεώρημα δίνει μία αναγκαία και ικανή συνθήκη για έναν αριθμό να είναι πρώτος. Το θεώρημα παίρνει το όνομά του από τον Τζον Ουίλσον.

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

• Για ${\displaystyle p=2}$, έχουμε ότι ${\displaystyle (2-1)!=1\equiv 2-1{\pmod {2}}}$ (και το ${\displaystyle p}$ είναι πρώτος).
• Για ${\displaystyle p=3}$, έχουμε ότι ${\displaystyle (3-1)!=2\equiv 3-1{\pmod {3}}}$ (και το ${\displaystyle p}$ είναι πρώτος).
• Για ${\displaystyle p=4}$, έχουμε ότι ${\displaystyle (4-1)!=2\cdot 3\equiv 2{\pmod {4}}}$ (και το ${\displaystyle p}$ είναι σύνθετος).
• Για ${\displaystyle p=5}$, έχουμε ότι ${\displaystyle (5-1)!=2\cdot 3\cdot 4=24\equiv 5-1{\pmod {5}}}$ (και το ${\displaystyle p}$ είναι πρώτος).
• Για ${\displaystyle p=6}$, έχουμε ότι ${\displaystyle (6-1)!=2\cdot 3\cdot 4\cdot 5=120\equiv 0{\pmod {6}}}$ (και το ${\displaystyle p}$ είναι σύνθετος).
• Για ${\displaystyle p=7}$, έχουμε ότι ${\displaystyle (7-1)!=720\equiv 7-1{\pmod {7}}}$ (και το ${\displaystyle p}$ είναι πρώτος).

Απόδειξη

Με πολλαπλασιαστικά αντίστροφα

(${\displaystyle \Rightarrow }$) Έστω ${\displaystyle p}$ ένας πρώτος αριθμός. Θα χρησιμοποιήσουμε ότι για κάθε ${\displaystyle a=1,2,\ldots ,p-1}$ υπάρχει ένας πολλαπλασιαστικός αντίστροφος στο ${\displaystyle \mathbb {Z} _{p}}$, δηλαδή ένας αριθμός ${\displaystyle a^{-1}}$ τέτοιος ώστε ${\displaystyle a\cdot a^{-1}\equiv 1{\pmod {p}}}$. Αυτό ισχύει καθώς ο ${\displaystyle a}$ είναι πρώτος σχετικά με τον ${\displaystyle p}$. Αν ο ${\displaystyle a}$ είναι πολλαπλασιαστικός αντίστροφος του ${\displaystyle b}$, τότε και ο ${\displaystyle b}$ είναι πολλαπλασιαστικός αντίστροφος του ${\displaystyle a}$, καθώς ${\displaystyle a\cdot b\equiv b\cdot a\equiv 1{\pmod {p}}}$. Επομένως, οι αντίστροφοι έρχονται σε δυάδες.

Θα δείξουμε ότι ο μόνοι αριθμοί που είναι αντίστροφοι του εαυτού τους είναι ο ${\displaystyle a=1}$ και ο ${\displaystyle a=p-1}$. Έστω ότι ισχύει

${\displaystyle a^{2}\equiv 1{\pmod {p}}}$.

Τότε έχουμε ισοδύναμα ότι ${\displaystyle p\mid a^{2}-1}$ ή ισοδύναμα ότι ${\displaystyle p\mid (a-1)\cdot (a+1)}$ (χρησιμοποιώντας την ταυτότητα για την διαφορά τετραγώνων). Επειδή ο ${\displaystyle p}$ είναι πρώτος έχουμε ότι ${\displaystyle p\mid a-1}$ ή ${\displaystyle p\mid a+1}$ άρα ${\displaystyle a=p+1}$ ή ${\displaystyle a=p-1}$.

Συνεπώς, όλα τα ${\displaystyle a=2,\ldots ,p-2}$ έχουν πολλαπλασιαστικούς αντιστρόφους που έρχονται σε ζεύγη και έτσι χρησιμοποιώντας την αντιμεταθετική ιδιότητα του πολλαπλασιασμού απαλείφονται, άρα

${\displaystyle (p-1)!\equiv 1\cdot 1\cdot \ldots \cdot 1\cdot (p-1)\equiv (p-1)\equiv p-1{\pmod {p}}}$,

που είναι και το ζητούμενο.

(${\displaystyle \Leftarrow }$) Έστω ${\displaystyle p}$ ένας σύνθετος αριθμός. Τότε μπορεί να γραφτεί ως το γινόμενο δύο φυσικών αριθμών ${\displaystyle 1<a,b<n}$, δηλαδή ${\displaystyle p=a\cdot b}$. Διακρίνουμε δύο περιπτώσεις:

• Περίπτωση 1η (${\displaystyle a\neq b}$): Τότε και το ${\displaystyle a}$ και το ${\displaystyle b}$ εμφανίζεται στο γινόμενο ${\displaystyle (p-1)!=1\cdot 2\cdot \ldots \cdot (p-1)}$, άρα το ${\displaystyle p\mid (p-1)!}$.
• Περίπτωση 2η (${\displaystyle a=b}$): Σε αυτή την περίπτωση δεν εμφανίζονται και το ${\displaystyle a}$ και το ${\displaystyle b}$ στο γινόμενο. Για ${\displaystyle p=1,2,3,4}$ είναι εύκολο να ελέγξουμε ότι η σχέση ισχύει. Για ${\displaystyle p>5}$ έχουμε ότι ${\displaystyle 2b<b^{2}=p}$ και άρα το ${\displaystyle a}$ και το ${\displaystyle 2b}$ (για τα οποία ισχύει ότι ${\displaystyle a\cdot (2b)=2\cdot ab=2\cdot p}$) εμφανίζονται στο γινόμενο ${\displaystyle (p-1)!=1\cdot 2\cdot \ldots \cdot (p-1)}$, και άρα ${\displaystyle p\mid (p-1)!}$.

Εφαρμογές

Από πρακτικής απόψεως, η συνθήκη αυτή δεν χρησιμοποιείται για να ελέγξουμε αν ένας αριθμός είναι πρώτος, καθώς ο υπολογισμός του ${\displaystyle (p-1)!}$ χρειάζεται ${\displaystyle \Theta (p)}$ πράξεις, ενώ μπορούμε για παράδειγμα να ελέγξουμε απευθείας αν κάποιος από τους αριθμούς ${\displaystyle 1,\ldots ,\lceil {\sqrt {p}}\rceil }$ διαιρεί τον ${\displaystyle p}$ (που χρειάζεται ${\displaystyle \Theta ({\sqrt {p}})}$ πράξεις).^[4]: 133

Δείτε επίσης

• Μικρό θεώρημα του Φερμά
• Συνάρτηση Όιλερ
• Πρώτοι αριθμοί Ουίλσον

Περαιτέρω ανάγνωση

Εξωτερικοί σύνδεσμοι

• Εφαρμογές του θεωρήματος Ουίλσον
• Διάλεξη για το μικρό θεώρημα του Φερμά και το θεώρημα Ουίλσον
• Cut the knot: Θεώρημα Ουίλσον
• Art of Problem Solving: Θεώρημα Ουίλσον

Ξενόγλωσσα άρθρα

• Anderson, Peter G.; Benjamin, Arthur T.; Rouse, Jeremy A. (Μαρτίου 2005). «Combinatorial Proofs of Fermat's, Lucas's, and Wilson's Theorems». The American Mathematical Monthly 112 (3): 266–268. doi:10.1080/00029890.2005.11920193. https://archive.org/details/sim_american-mathematical-monthly_2005-03_112_3/page/266. 
• Ruiz, Sebastián Martín (Νοεμβρίου 1996). «80.52 An algebraic identity leading to Wilson’s theorem». The Mathematical Gazette 80 (489): 579–582. doi:10.2307/3618534. https://archive.org/details/sim_mathematical-gazette_1996-11_80_489/page/579. 
• Wilf, Herbert S.; Herzig, Florian (Φεβρουαρίου 1999). «Wilson's Theorem in Disguise: 10578». The American Mathematical Monthly 106 (2): 169. doi:10.2307/2589065. https://archive.org/details/sim_american-mathematical-monthly_1999-02_106_2/page/169. 
• Christian Aebi; Grant Cairns (2015). «Generalizations of Wilson’s Theorem for Double-, Hyper-, Sub- and Superfactorials». The American Mathematical Monthly 122 (5): 433. doi:10.4169/amer.math.monthly.122.5.433. https://archive.org/details/sim_american-mathematical-monthly_2015-05_122_5/page/433. 

Παραπομπές

1. Βλάμος, Π.· Ραππος, Ε.· Ψαρρακος, Π. (2000). Θεωρία αριθμών. Αθήνα: Ελληνική Μαθηματική Εταιρεία. ISBN 960-7341-18-X. 
2. Hardy, Godfrey H.· Wright, Edward Maitland. An introduction to the theory of numbers (5η έκδοση). Oxford: Clarendon Press. ISBN 9780198531715. 
3. Davenport, Harold. The higher arithmetic: an introduction to the theory of numbers (8η έκδοση). Cambridge: Cambridge university press. ISBN 978-0-521-72236-0. 
4. Graham, Ronald Lewis· Knuth, Donald Ervin· Patashnik, Oren. Concrete mathematics: a foundation for computer science (2η έκδοση). Upper Saddle River, NJ: Addison-Wesley. ISBN 978-0-201-55802-9. 
5. Θεοχάρη Αποστολίδου, Θεοδώρα (2015). Εισαγωγή στη θεωρία ομάδων. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. 
6. Γκότσης, Κ. «Σημειώσεις στοιχειώδους θεωρίας αριθμών» (PDF). Πανεπιστήμιο Αθηνών. Ανακτήθηκε στις 21 Οκτωβρίου 2023. 
7. Παπαδημητράκης, Μιχάλης. «Θεωρία αριθμών: Πρόχειρες σημειώσεις» (PDF). Τμήμα Μαθηματικών, Πανεπιστήμιο Κρήτης. Ανακτήθηκε στις 21 Οκτωβρίου 2023.