Click to Translate Whole Page to Read and Solve

Τετάρτη 20 Ιουνίου 2012

Ισοϋπόλοιποι Αριθμοί

Ξεκινώντας με ένα φυσικό αριθμό m>1, και χρησιμοποιώντας τη σχέση
a∼b⇔a−b=km, για κάποιο k∈Z,
σχηματίζουμε μια σχέση ισοδυναμίας στο σύνολο Z των ακεραίων. Ειδικά για τη σχέση αυτή έχει επικρατήσει ο συμβολισμός
a≡b(modm),
ο οποίος διαβάζεται: a ισότιμος του b modulo m ή a ισοδύναμος του b modulo m. Μερικές φορές η φράση modulo m αντικαθίσταται με τη φράση κατά μέτρο m. Έτσι, με τον νέο συμβολισμό θα έχουμε
a≡b(modm)⇔a−b=km, για κάποιο k∈Z.
Αν a και b είναι δύο ισοδύναμοι modm ακέραιοι, μερικές φορές λέγονται και ισοϋπόλοιποι αριθμοί. Ο λόγος για την ονομασία αυτή βρίσκεται στο παρακάτω αποτέλεσμα.
Ισοϋπόλοιποι Αριθμοί 
Έστω m>1 ένας φυσικός αριθμός. Οι ακέραιοι a και b είναι ισότιμοι modulo m αν και μόνον αν αφήνουν το ίδιο υπόλοιπο διαιρούμενοι δια m . Δηλαδή
a≡b(modm) ⇔ οι ακέραιοι a και b αφήνουν το ίδιο υπόλοιπο διαιρούμενοι δια m 
Ο συμβολισμός ≡ που χρησιμοποιείται για τις ισοτιμίες, θυμίζει την ισότητα και αυτό δεν είναι τυχαίο. Είναι εύκολο να δείξει κανείς ότι οι ισοτιμίες έχουν πολλές από τις ιδιότητες της ισότητας.
Ιδιότητες Ισοτιμιών 
Έστω m>1 ένας φυσικός αριθμός. Αν a≡b(modm) και c≡d(modm), τότε θα ισχύουν και οι σχέσεις
(i) a+c≡b+d(modm) 
(ii) a−c≡b−d(modm) 
(iii) a⋅c≡b⋅d(modm) 
(iv) a+x≡b+x(modm), για κάθε x∈Z 
(v) a−x≡b−x(modm), για κάθε x∈Z 
(vi) a⋅x≡b⋅x(modm), για κάθε x∈Z 
Είναι προφανές ότι η ιδιότητα (i) ισχύει και για περισσότερους από δύο προσθετέους, αρκεί να χωρίσουμε τους προσθετέους σε δύο ομάδες και να εφαρμόσουμε την ιδιότητα (i). Κάτι ανάλογο ισχύει και για την ιδιότητα (iii), δηλαδή ισχύει για περισσότερους από δύο παράγοντες. Αν τώρα οι προσθετέοι ή οι παράγοντες είναι όλοι ίδιοι, και k σε πλήθος, καταλήγουμε στις σχέσεις
a≡b(modm)⇒ka≡kb(modm)
a≡b(modm)⇒ak≡bk(modm)
Η έννοια της ισοτιμίας συμπληρώνει κατά κάποιο τρόπο την έννοια της διαιρετότητας, διότι διευκολύνει μερικές φορές την επίλυση προβλημάτων διαιρετότητας. Ας δούμε κάποια παραδείγματα προς αυτή την κατεύθυνση.
Παράδειγμα 
Θεωρούμε το θετικό ακέραιο a=11311771 και υποθέτουμε ότι θέλουμε να βρούμε το υπόλοιπο της διαίρεσης του a δια του 6. Αν το υπόλοιπο αυτό είναι x, τότε οι αριθμοί a και x είναι ισοϋπόλοιποι, δηλαδή θα ισχύει η σχέση
a≡x(mod6).
Επομένως ουσιαστικά θέλουμε να λύσουμε μια εξίσωση με άγνωστο τον ακέραιο x. Παρατηρούμε ότι ισχύει 11−5=6, δηλαδή 11≡5(mod6). Από τη σχέση αυτή, και με βάση τις ιδιότητες που αναφέραμε, θα έχουμε
115(mod6)11252(mod6)1121(mod6).
Χρησιμοποιώντας την ισοτιμία αυτή θα έχουμε
1131=11215+1=(112)151111511(mod6)
11(mod6)5(mod6).
Επίσης, από την ισότητα 17−5=12 προκύπτει 17≡5(mod6), οπότε θα έχουμε και τις σχέσεις
175(mod6)17252(mod6)1721(mod6).
Χρησιμοποιώντας την ισοτιμία αυτή θα έχουμε
1771=17235+1=(172)351713517(mod6)
17(mod6)5(mod6).
Επομένως, θα έχουμε τελικά
a=1131177155(mod6)1(mod6)
δηλαδή το υπόλοιπο της διαίρεσης του a δια του 6 είναι 1.
Πηγή: auth.gr/epsom