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

Στην θεωρία αριθμών, το θεώρημα Ουίλσον (αναφέρεται και ως θεώρημα Wilson) λέει ότι ένας φυσικός αριθμός $p$ είναι πρώτος αν και μόνο αν ισχύει ότι

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

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

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

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

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

Απόδειξη

Απόδειξη (με πολλαπλασιαστικά αντίστροφα)  

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

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

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

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

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

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

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

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

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

Εφαρμογές

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

Δείτε επίσης

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

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

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

• Εφαρμογές του θεωρήματος Ουίλσον
• Διάλεξη για το μικρό θεώρημα του Φερμά και το θεώρημα Ουίλσον
• Θεώρημα Ουίλσον στο 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.