Θεώρημα Wilson - Ενδιάμεσο

Συντονιστής: polysot

Απάντηση
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 9010
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:
Επικοινωνία Demetres

Θεώρημα Wilson - Ενδιάμεσο

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Οκτ 04, 2016 1:23 pm

Προαπαιτούμενα: Πρώτοι αριθμοί, Αριθμητική υπολοίπων (modular arithmetic)
Άλλες επιθυμητές γνώσεις: Αντίστροφοι modulo p. (Για την απόδειξη.)
Επίπεδο: Απολύτως απαραίτητο σε όσους λαμβάνουν μέρος στον Αρχιμήδη των μεγάλων και πάνω. Το ίδιο και για όσους juniors θα λάβουν μέρος σε διεθνείς διαγωνισμούς.

Θεώρημα Wilson: Έστω φυσικός n > 1. Ο n είναι πρώτος αν και μόνο αν (n-1)! \equiv -1 \bmod n

Παράδειγμα 1: Είναι (5-1)! = 24 \equiv -1 \bmod 5 άρα ο 5 είναι πρώτος.

Παράδειγμα 2: Είναι (4-1)! = 6 \equiv 2 \not \equiv -1 \bmod 4 άρα ο 4 δεν είναι πρώτος.

Απόδειξη:
Ας υποθέσουμε αρχικά ότι ο n είναι σύνθετος. Θέλουμε να δείξουμε ότι (n-1)! \not \equiv -1 \bmod n. Ας υποθέσουμε λοιπόν προς άτοπο ότι (n-1)! \equiv -1 \bmod n. Επειδή ο n είναι σύνθετος, τότε υπάρχει a \in \{2,3,\ldots,n-1\} με a|n. Τότε a|(n-1)!. Επειδή a|n και a|(n-1)! και αφού επιπλέον (n-1)! \equiv -1 \bmod n τότε παίρνουμε a=1, άτοπο.

Ας πάμε τώρα και στο κυρίως κομμάτι όπου θα δείξουμε ότι αν ο n είναι πρώτος, τότε (n-1)! \equiv -1 \bmod n. Για n=2 είναι άμεσο οπότε θα υποθέσουμε ότι n>2. Θα χρησιμοποιήσουμε ότι αν ο n είναι πρώτος και αν a \in \{1,2,\ldots,n-1\} τότε υπάρχει μοναδικό b \in \{1,2,\ldots,n-1\} με ab \equiv 1 \bmod n. (Τοποθέτηση συνδέσμου όταν γραφτεί το σχετικό άρθρο.)

Αν στο πιο πάνω έχουμε a=b τότε a^2 \equiv 1 \bmod n και άρα (a-1)(a+1) \equiv 0 \bmod n. Δηλαδή n|(a-1)(a+1) και αφού n πρώτος τότε a \equiv 1 \bmod n ή a \equiv -1 \bmod n. Δηλαδή a=1 ή a=n-1.

Άρα μπορούμε να χωρίσουμε τους αριθμούς \{2,\ldots,n-2\} σε ζεύγη \{a,b\} ώστε ab \equiv 1 \bmod n. [Π.χ. για n=7 τα ζεύγη είναι τα \{2,4\} και \{3,5\}.] Οπότε πολλαπλασιάζοντας όλους τους αριθμούς του συνόλου \{2,\ldots,n-2\} το γινόμενο θα είναι επίσης ισότιμο με 1 \bmod n. Δηλαδή (n-2)! \equiv 1 \bmod n και άρα (n-1)! \equiv (n-1) \equiv -1 \bmod n.
Άλλα παραδείγματα:
viewtopic.php?p=44148#p44148
viewtopic.php?p=217680#p217680
viewtopic.php?f=182&t=7328
viewtopic.php?p=147969#p147969
viewtopic.php?p=161782#p161782
viewtopic.php?p=53853#p53853
viewtopic.php?f=182&t=50428 (Άλυτο υποερώτημα)
Προκριματικός Μεγάλων 2015 - Πρόβλημα 1
ΒΜΟ 2016 - Πρόβλημα 3

Άλλη εφαρμογή

Θεώρημα: Αν p πρώτος με p \equiv 1 \bmod 4 τότε υπάρχει a με a^2 \equiv -1 \bmod p.

Απόδειξη:
Χωρίζουμε τους αριθμούς 1,2,\ldots,p-1 στα ζεύγη

\{1,p-1\},\{2,p-2\},\ldots,\{(p-1)/2,(p+1)/2\}.

Το γινόμενο των αριθμών του ζεύγους \{k,p-k\} ισούται με -k^2 \bmod p. Οπότε το γινόμενο των αριθμών όλων των ζευγών ισούται με

\displaystyle{ (-1^2)(-2^2) \cdots \left(- ((p-1)/2)^2 \right) \equiv (-1)^{(p-1)/2} \left[ ((p-1)/2)!\right]^2 \equiv \left[\left( \tfrac{p-1}{2} \right)!\right]^2 }

όπου στην τελευταία ισοδυναμία χρησιμοποιήσαμε ότι p \equiv 1 \bmod 4.

Όμως από το θεώρημα Wilson το γινόμενο ισούται με -1 \bmod p. Άρα μπορούμε να πάρουμε \displaystyle{ a = \left( \tfrac{p-1}{2} \right)!}


Λέξεις Κλειδιά:
πρώτοι-αριθμοί
αριθμητική-υπολοίπων
Θεώρημα-Wilson
Κορυφή
Απάντηση

Επιστροφή σε “Θεωρία Αριθμών”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης