Τετάρτη 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=11^{31}17^{71}$ και υποθέτουμε ότι θέλουμε να βρούμε το υπόλοιπο της διαίρεσης του a δια του 6. Αν το υπόλοιπο αυτό είναι x, τότε οι αριθμοί a και x είναι ισοϋπόλοιποι, δηλαδή θα ισχύει η σχέση
a≡x(mod6).
Επομένως ουσιαστικά θέλουμε να λύσουμε μια εξίσωση με άγνωστο τον ακέραιο x. Παρατηρούμε ότι ισχύει 11−5=6, δηλαδή 11≡5(mod6). Από τη σχέση αυτή, και με βάση τις ιδιότητες που αναφέραμε, θα έχουμε
$11≡5(mod6)⇒11^2≡5^2(mod6)⇒11^2≡1(mod6).$
Χρησιμοποιώντας την ισοτιμία αυτή θα έχουμε
$11^{31}=11^{2⋅15+1}=(11^2)^{15}11≡1^{15}11(mod6)$
$≡11(mod6)≡5(mod6).$
Επίσης, από την ισότητα 17−5=12 προκύπτει 17≡5(mod6), οπότε θα έχουμε και τις σχέσεις
$17≡5(mod6)⇒17^2≡5^2(mod6)⇒17^2≡1(mod6).$
Χρησιμοποιώντας την ισοτιμία αυτή θα έχουμε
$17^{71}=17^{2⋅35+1}=(17^2)^{35}17≡1^{35}17(mod6)$
$≡17(mod6)≡5(mod6).$
Επομένως, θα έχουμε τελικά
$a=11^{31}17^{71}≡5⋅5(mod6)≡1(mod6)$
δηλαδή το υπόλοιπο της διαίρεσης του a δια του 6 είναι 1.
Πηγή: auth.gr/epsom

3 σχόλια:

  1. Μπορείτε να με βοηθήσετε με την παραγοντοποιηση της
    f(x)=x^4-17x^3+90x^2-108x-216;

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Αν είστε μαθητής( το πλέον πιθανόν), μας λέτε την τάξη που φοιτάτε για να σας προτείνουμε την κατάλληλη λύση..

      Διαγραφή
  2. Η έννοια του μέτρου στους ισοϋπόλοιπους αριθμούς συνδέεται με την απόλυτη τιμή του υπολοίπου; Για παράδειγμα, το 8 ≡ -3 (mod 5) είναι αληθές ή ψευδές;

    ΑπάντησηΔιαγραφή