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

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

$(p-1)!\equiv p-1modp$,

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

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

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

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

Απόδειξη

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

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

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

$a^2\equiv 1(\mathrm{mod}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,\dots ,p-2$ έχουν πολλαπλασιαστικούς αντιστρόφους που έρχονται σε ζεύγη και έτσι χρησιμοποιώντας την αντιμεταθετική ιδιότητα του πολλαπλασιασμού απαλείφονται, άρα

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

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

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

• Περίπτωση 1η ($a\ne b$): Τότε και το $a$ και το $b$ εμφανίζεται στο γινόμενο $(p-1)!=1\cdot 2\cdot \dots \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 \dots \cdot (p-1)$, και άρα $p\mid (p-1)!$.

Εφαρμογές

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

Δείτε επίσης

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

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

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

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

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

• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal