Στο \(17\)ο μάθημα μιλήσαμε για το Θεώρημα του Euler, το τρίτο και τελευταίο του τρίπτυχου κανονικών θεωρημάτων της Στοιχειώδους Θεωρίας Αριθμών, μαζί με το Θεώρημα του Fermat και το Θεώρημα του Wilson. Το Θεώρημα του Euler (Θεώρημα \(17.1.2\)) γενικεύει αυτό του Fermat. Είδαμε ως εφαρμογή του Θεωρήματος του Euler ότι κάθε αριθμητική πρόοδος της οποίας οι όροι είναι όλοι ακέραιοι περιέχει μία άπειρη γεωμετρική πρόοδο (Εφαρμογή \(17.1.5\)). Ακόμα, διατυπώσαμε και αποδείξαμε το Θεώρημα του Rédei (Θεώρημα \(17.1.6\)) το οποίο αποτελεί “γενίκευση” του Θεωρήματος του Euler. Κλείσαμε το θεωρητικό κομμάτι του μαθήματος διευκρινίζοντας την χρησιμότητα του Θεωρήματος του Euler σε ό,τι έχει σχέση με την εύρεση πολλαπλασιαστικών αντιστρόφων και την επίλυση (κάποιων) γραμμικών ισοτιμιών. Και στο μάθημα αυτό δόθηκαν αρκετές ασκήσεις για λύση.
Το βίντεο του μαθήματος:
Στο \(18\)ο μάθημα ορίσαμε την τάξη ενός ακεραίου \(a\) ως προς κάποιο μέτρο \(n\), όπου \(a\) και \(n\) είναι σχετικά πρώτοι, ως τον ελάχιστο φυσικό \(k\) που είναι τέτοιος ώστε \(a^k \equiv 1 \bmod{n}\). Προσέξτε εδώ ότι η τάξη ορίζεται μόνο στην περίπτωση που \(\gcd(a, n) = 1\). Βασική ιδιότητα της τάξης περιγράφεται στο Θεώρημα \(18.1.2\) σύμφωνα με το οποίο, αν ο \(a\) έχει τάξη \(k\) ως προς το μέτρο \(n\), τότε η ισοτιμία \(a^h \equiv 1 \bmod{n}\) ισχύει, αν και μόνο αν ο \(k\) διαιρεί τον \(h\). Συγκεκριμένα, έχουμε ότι \(k \mid \phi(n)\). Εν συνεχεία είδαμε το Θεώρημα \(18.1.3\) το οποία λέει ότι αν ο \(a\) έχει τάξη \(k\) ως προς το μέτρο \(n\), τότε η ισοτιμία \(a^i \equiv a^j \bmod{n}\) ισχύει, αν και μόνο αν \(i \equiv j \bmod{k}\). Δηλαδή δύο δυνάμεις του \(a\) είναι ισότιμες, αν και μόνο αν οι εκθέτες είναι ισότιμοι ως προς το μέτρο \(k\). Σύμφωνα με το Πόρισμα \(18.1.4\), αν ο \(a\) έχει τάξη \(k\) ως προς το μέτρο \(n\), τότε οι \(a, a^2, \ldots, a^k\) είναι ανισότιμοι ως προς το μέτρο \(n\). Το επόμενο αποτέλεσμα, Θεώρημα \(18.1.5\), μας δίνει την τάξη μιας οποιασδήποτε δύναμης του συναρτήσει του εκθέτη και της τάξης του \(a\). Συγκεκριμένα, αν ο \(a\) έχει τάξη \(k\) ως προς το μέτρο \(n\), τότε η τάξη του \(a^h\), όπου \(h>0\), είναι ίση με \(k/\gcd(h, k)\) ως προς το μέτρο \(n\). Έπεται ότι η τάξη του \(a^h\) είναι ίση με την τάξη του \(a\), αν και μόνο αν \(\gcd(h, k) = 1\). Σε περίπτωση που ο \(a\) έχει τη μεγαλύτερη δυνατή τάξη ως προς κάποιο μέτρο \(n\), δηλαδή η τάξη του \(a\) είναι ίση με \(\phi(n)\), ο \(a\) καλείται πρωταρχική ρίζα του \(n\). Προσέξτε ότι δεν έχουν όλοι οι φυσικοί πρωταρχικές ρίζες. Βασικό αποτέλεσμα εδώ αποτελεί το Θεώρημα \(18.2.3\) σύμφωνα με το οποίο, αν \(\gcd(a, n) = 1\) και οι \(a_{1}, a_{2}, \ldots, a_{\phi(n)}\) είναι οι φυσικοί που είναι μικρότεροι του \(n\) και σχετικά πρώτοι με τον \(n\) και ο \(a\) είναι πρωταρχική ρίζα του \(n\), τότε οι \(a, a^{2}, \ldots, a^{\phi(n)}\) είναι ισότιμοι ως προς το μέτρο \(n\) με τους \(a_{1}, a_{2}, \ldots, a_{\phi(n)}\) σε κάποια σειρά. Ως άμεσο πόρισμα παίρνουμε ότι, αν ο \(n\) έχει πρωταρχική ρίζα, τότε έχει ακριβώς \(\phi(\phi(n))\) πρωταρχικές ρίζες.
Το βίντεο του μαθήματος: