Μαθηματικό έργο με θέμα

"Μοντέλο σύγκρισης"

Zaripova Aisylu

Περιοχή Σοβέτσκι του Καζάν

ΜΠΟΥ «Γυμνάσιο Νο 166», 7α τάξη

Επιστημονική υπεύθυνη: Antonova N.A.

Πίνακας περιεχομένων

Εισαγωγή________________________________________________________________3

    Τι είναι οι συγκρίσεις_________________________________________________4

    1. Η έννοια των συγκρίσεων modulo________________________4

      Ιστορία της εμφάνισης της έννοιας των συγκρίσεων modulo_____4

      Ιδιότητες συγκρίσεων______________________________________4

    Εφαρμογή συγκρίσεων στην επίλυση προβλημάτων________________________________6

    1. Η απλούστερη χρήση των συγκρίσεων modulo είναι ο προσδιορισμός της διαιρετότητας των αριθμών___________________________6

      Μία εργασία σύγκρισης_________________________________8

      Η χρήση συγκρίσεων modulo σε επαγγελματικές δραστηριότητες________________________________________________9

Συμπέρασμα________________________________________________10

Κατάλογος χρησιμοποιημένης βιβλιογραφίας_____________________________________11

Εισαγωγή.

Θέμα: Συγκρίσεις ενοτήτων.

Πρόβλημα: Πολλοί μαθητές αντιμετωπίζουν προβλήματα κατά την προετοιμασία για τις Ολυμπιάδες, η λύση των οποίων βασίζεται στη γνώση των υπολοίπων από τη διαίρεση ακεραίων με έναν φυσικό αριθμό. Μας ενδιέφεραν αυτού του είδους τα προβλήματα και οι πιθανές μέθοδοι επίλυσής τους. Αποδεικνύεται ότι μπορούν να λυθούν χρησιμοποιώντας συγκρίσεις modulo.

Στόχος: Μάθετε την ουσία των συγκρίσεων modulo, τις κύριες μεθόδους εργασίας με συγκρίσεις modulo.

Στόχοι: βρείτε θεωρητικό υλικό για αυτό το θέμα, εξετάστε προβλήματα που επιλύονται χρησιμοποιώντας συγκρίσεις modulo, δείξτε τις πιο συνηθισμένες μεθόδους για την επίλυση τέτοιων προβλημάτων, εξάγετε συμπεράσματα.

Αντικείμενο μελέτης: θεωρία αριθμών.

Αντικείμενο έρευνας: θεωρία συγκρίσεων συντελεστών.

Η εργασία σχετίζεται με θεωρητική έρευνα και μπορεί να χρησιμοποιηθεί στην προετοιμασία για μαθηματικές Ολυμπιάδες. Το περιεχόμενό του αποκαλύπτει τις βασικές έννοιες των συγκρίσεων modulo και τις κύριες ιδιότητές τους, και παρέχει παραδείγματα επίλυσης προβλημάτων σχετικά με αυτό το θέμα.

Εγώ . Τι είναι οι συγκρίσεις;

    1. Η έννοια των συγκρίσεων modulo.

Οι αριθμοί και λέγεται ότι είναι συγκρίσιμοι σε συντελεστή αν διαιρούνται με, με άλλα λόγια, το a και το b έχουν τα ίδια υπόλοιπα όταν διαιρούνται με.

Ονομασία

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

    Το 12 και το 32 είναι συγκρίσιμα modulo 5, αφού το 12 όταν διαιρείται με το 5 έχει υπόλοιπο 2 και το 32 όταν διαιρείται με το 2 έχει υπόλοιπο 2. Είναι γραμμένο12 ;

    101 και 17 είναι συγκρίσιμα modulo 21.

    1. Ιστορία της εμφάνισης της έννοιας των συγκρίσεων modulo.

Η θεωρία της διαιρετότητας δημιουργήθηκε σε μεγάλο βαθμό από τον Euler. Ο ορισμός της σύγκρισης διατυπώθηκε στο βιβλίο του K.F. Gauss «Arithmetic Studies». Αυτό το έργο, γραμμένο στα λατινικά, άρχισε να τυπώνεται το 1797, αλλά το βιβλίο δημοσιεύτηκε μόλις το 1801 λόγω του γεγονότος ότι η διαδικασία εκτύπωσης εκείνη την εποχή ήταν εξαιρετικά εντατική και χρονοβόρα. Η πρώτη ενότητα του βιβλίου του Gauss ονομάζεται: «Σχετικά με τη σύγκριση των αριθμών». Ήταν ο Gauss που πρότεινε τον συμβολισμό των συγκρίσεων modulo που έχει καθιερωθεί στα μαθηματικά.

    1. Ιδιότητες συγκρίσεων.

Αν

Απόδειξη:

  1. Αν προσθέσουμε το δεύτερο στην πρώτη ισότητα, παίρνουμε

είναι το άθροισμα δύο ακεραίων, επομένως είναι ακέραιος, επομένως.

    Αν αφαιρέσουμε τη δεύτερη από την πρώτη ισότητα, παίρνουμε

αυτή είναι η διαφορά δύο ακεραίων, που σημαίνει ότι είναι ακέραιος, επομένως.

    Σκεφτείτε την έκφραση:

Αυτή είναι η διαφορά των προϊόντων των ακεραίων, που σημαίνει ότι είναι ακέραιος, επομένως.

    Αυτό είναι συνέπεια της τρίτης ιδιότητας των συγκρίσεων.

Q.E.D.

5) Αν.

Απόδειξη: Ας βρούμε το άθροισμα αυτών των δύο εκφράσεων:

είναι το άθροισμα δύο ακεραίων, επομένως είναι ακέραιος, επομένως .

Q.E.D.

6) Αν είναι ακέραιος τότε

Απόδειξη: , πούΠ– έναν ακέραιο, πολλαπλασιάστε αυτήν την ισότητα με, παίρνουμε: . Εφόσον είναι γινόμενο ακεραίων, αυτό έπρεπε να αποδειχθεί.

7) Αν

Απόδειξη: ο συλλογισμός είναι παρόμοιος με την απόδειξη της ιδιότητας 6.

8) Αν - Συμπρώτες αριθμοί, λοιπόν

Απόδειξη: , διαιρούμε αυτήν την έκφραση με, παίρνουμε: - συμπρώτοι αριθμοί, που σημαίνει ότι διαιρούνται με έναν ακέραιο, δηλ. =. Και αυτό σημαίνει ότι αυτό που έπρεπε να αποδειχτεί.

II . Εφαρμογή συγκρίσεων στην επίλυση προβλημάτων.

2.1. Η απλούστερη χρήση των συγκρίσεων modulo είναι ο προσδιορισμός της διαιρετότητας των αριθμών.

Παράδειγμα. Βρείτε το υπόλοιπο του 2 2009 στις 7.

Λύση: Εξετάστε τις δυνάμεις του 2:

ανεβάζοντας τη σύγκριση στη δύναμη του 668 και πολλαπλασιάζοντας με, παίρνουμε: .

Απάντηση: 4.

Παράδειγμα. Αποδείξτε ότι 7+7 2 +7 3 +…+7 4 n διαιρείται με το 100 για οποιοδήποτεnαπό ένα σύνολο ακεραίων.

Λύση: Εξετάστε τις συγκρίσεις

και τα λοιπά. Η κυκλική φύση των υπολοίπων εξηγείται από τους κανόνες για τον πολλαπλασιασμό των αριθμών σε μια στήλη. Προσθέτοντας τις τέσσερις πρώτες συγκρίσεις, παίρνουμε:

Αυτό σημαίνει ότι αυτό το ποσό διαιρείται με το 100 χωρίς υπόλοιπο. Ομοίως, προσθέτοντας τις ακόλουθες συγκρίσεις για τέσσερις, παίρνουμε ότι κάθε τέτοιο άθροισμα διαιρείται με το 100 χωρίς υπόλοιπο. Αυτό σημαίνει ότι ολόκληρο το άθροισμα που αποτελείται από 4nΟι όροι διαιρούνται με το 100 χωρίς υπόλοιπο. Q.E.D.

Παράδειγμα. Προσδιορίστε σε ποια τιμήnη έκφραση διαιρείται με το 19 χωρίς υπόλοιπο.

Λύση: .

Ας πολλαπλασιάσουμε αυτή τη σύγκριση επί 20. Παίρνουμε.

Ας προσθέσουμε λοιπόν τις συγκρίσεις. . Έτσι, η δεξιά πλευρά της σύγκρισης διαιρείται πάντα με το 19 για οποιονδήποτε φυσικό αριθμόn, που σημαίνει ότι η αρχική έκφραση διαιρείται με το 19 με το φυσικόn.

Απάντηση n – οποιοδήποτε φυσικό αριθμό.

Παράδειγμα. Με ποιο ψηφίο τελειώνει ο αριθμός;

Λύση. Για να λύσουμε αυτό το πρόβλημα, θα παρακολουθήσουμε μόνο το τελευταίο ψηφίο. Εξετάστε τις δυνάμεις του αριθμού 14:

Μπορείτε να παρατηρήσετε ότι αν ο εκθέτης είναι περιττός, η τιμή του βαθμού τελειώνει στο 4, και αν ο εκθέτης είναι άρτιος, τελειώνει στο 6. Τότε τελειώνει στο 6, δηλ. είναι ζυγός αριθμός. Άρα θα τελειώσει στις 6.

Απάντηση 6.

2.2. Μία εργασία σύγκρισης.

Το άρθρο του N. Vilenkin “Comparisons and classes of residues” παρουσιάζει ένα πρόβλημα που έλυσε ο διάσημος Άγγλος φυσικός Dirac στα φοιτητικά του χρόνια.

Υπάρχει επίσης μια σύντομη λύση σε αυτό το πρόβλημα χρησιμοποιώντας συγκρίσεις modulo. Όμως αντιμετωπίσαμε μια σειρά από παρόμοια προβλήματα. Για παράδειγμα.

Ένας περαστικός βρήκε ένα σωρό μήλα κοντά σε ένα δέντρο στο οποίο καθόταν μια μαϊμού. Αφού τα μέτρησε, συνειδητοποίησε ότι αν δοθεί 1 μήλο στον πίθηκο, τότε ο αριθμός των υπολοίπων μήλων θα χωριστεί σε n χωρίς ίχνος. Έχοντας δώσει το επιπλέον μήλο στη μαϊμού, πήρε 1/ n υπόλοιπα μήλα και αριστερά. Αργότερα, ο επόμενος περαστικός πλησίασε το σωρό, μετά ο επόμενος κ.λπ. Κάθε επόμενος περαστικός, έχοντας μετρήσει τα μήλα, παρατήρησε ότι ο αριθμός τους διαιρείται με n δίνει το υπόλοιπο 1 και, έχοντας δώσει το επιπλέον μήλο στη μαϊμού, πήρε 1 για τον εαυτό του n τα υπόλοιπα μήλα και προχώρησε. Αφού έφυγε ο τελευταίος, n ο περαστικός, ο αριθμός των μήλων που είχαν απομείνει στο σωρό διαιρέθηκε με n χωρίς ίχνος. Πόσα μήλα ήταν στο σωρό στην αρχή;

Εκτελώντας τον ίδιο συλλογισμό με τον Dirac, αποκτήσαμε έναν γενικό τύπο για την επίλυση μιας κατηγορίας παρόμοιων προβλημάτων: , όπουn- φυσικός αριθμός.

2.3. Εφαρμογή συγκρίσεων ενοτήτων σε επαγγελματικές δραστηριότητες.

Η θεωρία σύγκρισης εφαρμόζεται στη θεωρία κωδικοποίησης, επομένως όλοι οι άνθρωποι που επιλέγουν ένα επάγγελμα που σχετίζεται με τους υπολογιστές θα σπουδάσουν και, ενδεχομένως, θα εφαρμόσουν συγκρίσεις στις επαγγελματικές τους δραστηριότητες. Για παράδειγμα, μια σειρά από έννοιες της θεωρίας αριθμών, συμπεριλαμβανομένων των συγκρίσεων modulo, χρησιμοποιούνται για την ανάπτυξη αλγορίθμων κρυπτογράφησης δημόσιου κλειδιού.

Συμπέρασμα.

Η εργασία περιγράφει τις βασικές έννοιες και τις ιδιότητες των συγκρίσεων modulo και επεξηγεί τη χρήση των συγκρίσεων modulo με παραδείγματα. Το υλικό μπορεί να χρησιμοποιηθεί για την προετοιμασία για ολυμπιάδες στα μαθηματικά και την Ενιαία Κρατική Εξέταση.

Ο δεδομένος κατάλογος αναφορών επιτρέπει, εάν είναι απαραίτητο, να εξετάσουμε μερικές πιο σύνθετες πτυχές της θεωρίας των συγκρίσεων modulo και των εφαρμογών της.

Κατάλογος χρησιμοποιημένης βιβλιογραφίας.

    Alfutova N.B. Άλγεβρα και θεωρία αριθμών./N.B.Alfutova, A.V.Ustinov. M.:MCNMO, 2002, 466 σελ.

    Bukhshtab A.A. Θεωρία αριθμών. /A.A.Bukhshtab. Μ.: Εκπαίδευση, 1960.

    Vilenkin N. Συγκρίσεις και κατηγορίες υπολειμμάτων./N. Vilenkin.//Quantum. – 1978.- 10.

    Fedorova N.E. Μελέτη άλγεβρας και μαθηματική ανάλυση. Βαθμός 10.http:// www. prosv. ru/ ηλεκτρονικά βιβλία/ Φεντόροβα_ Αλγεβρα_10 kl/1/ xht

    ru. wikipedia. org/ wiki/Comparison_modulo.

Εξετάστε μια σύγκριση της φόρμας Χ 2 ≡ένα(τροπ Πα), όπου Π– απλός περιττός αριθμός. Όπως φαίνεται στην παράγραφο 4 της §4, η λύση σε αυτή τη σύγκριση μπορεί να βρεθεί λύνοντας τη σύγκριση Χ 2 ≡ένα(τροπ Π). Επιπλέον, η σύγκριση Χ 2 ≡ένα(τροπ Πα) θα έχει δύο λύσεις αν έναείναι ένας τετραγωνικός συντελεστής υπολειμμάτων Π.

Παράδειγμα:

Επίλυση τετραγωνικής σύγκρισης Χ 2 ≡86 (mod 125).

125 = 5 3, το 5 είναι πρώτος αριθμός. Ας ελέγξουμε αν το 86 είναι τετράγωνο modulo 5.

Η αρχική σύγκριση έχει 2 λύσεις.

Ας βρούμε μια λύση στη σύγκριση Χ 2 ≡86 (τροπ. 5).

Χ 2 ≡1 (τροπ. 5).

Αυτή η σύγκριση θα μπορούσε να λυθεί με τον τρόπο που υποδεικνύεται στην προηγούμενη παράγραφο, αλλά θα χρησιμοποιήσουμε το γεγονός ότι η τετραγωνική ρίζα του 1 modulo είναι ±1 και η σύγκριση έχει ακριβώς δύο λύσεις. Έτσι, η λύση του συντελεστή σύγκρισης 5 είναι

Χ≡±1 (mod 5) ή, διαφορετικά, Χ=±(1+5 t 1).

Ας αντικαταστήσουμε τη λύση που προκύπτει με συντελεστή σύγκρισης 5 2 =25:

Χ 2 ≡86 (mod 25)

Χ 2 ≡11 (mod 25)

(1+5t 1) 2 ≡11 (mod 25)

1+10t 1 +25t 1 2 ≡11 (mod 25)

10t 1 ≡10 (mod 25)

2t 1 ≡2 (τροπ. 5)

t 1 ≡1 (mod 5), ή, τι είναι το ίδιο, t 1 =1+5t 2 .

Τότε η λύση του συντελεστή σύγκρισης 25 είναι Χ=±(1+5(1+5 t 2))=±(6+25 t 2). Ας αντικαταστήσουμε τη λύση που προκύπτει με συντελεστή σύγκρισης 5 3 = 125:

Χ 2 ≡86 (mod 125)

(6+25t 2) 2 ≡86 (mod 125)

36+12·25 t 2 +625t 2 2 ≡86 (mod 125)

12·25 t 2 ≡50 (mod 125)

12t 2 ≡2 (τροπ. 5)

2t 2 ≡2 (τροπ. 5)

t 2 ≡1 (mod 5), ή t 2 =1+5t 3 .

Τότε η λύση στο modulo σύγκρισης 125 είναι Χ=±(6+25(1+5 t 3))=±(31+125 t 3).

Απάντηση: Χ≡±31 (mod 125).

Ας εξετάσουμε τώρα μια σύγκριση της φόρμας Χ 2 ≡ένα(mod 2 α). Μια τέτοια σύγκριση δεν έχει πάντα δύο λύσεις. Για μια τέτοια ενότητα είναι δυνατές οι ακόλουθες περιπτώσεις:

1) α=1. Τότε η σύγκριση έχει λύση μόνο όταν ένα≡1 (mod 2), και η λύση είναι Χ≡1 (mod 2) (μία λύση).

2) α=2. Η σύγκριση έχει λύσεις μόνο όταν ένα≡1 (mod 4), και η λύση είναι Χ≡±1 (mod 4) (δύο λύσεις).

3) α≥3. Η σύγκριση έχει λύσεις μόνο όταν ένα≡1 (mod 8), και θα υπάρχουν τέσσερις τέτοιες λύσεις. Σύγκριση Χ 2 ≡ένα(mod 2 α) για το α≥3 λύνεται με τον ίδιο τρόπο όπως οι συγκρίσεις της φόρμας Χ 2 ≡ένα(τροπ Πα), μόνο οι λύσεις modulo 8 λειτουργούν ως αρχική λύση: Χ≡±1(mod 8) και Χ≡±3 (mod 8). Θα πρέπει να συγκριθούν το modulo 16, μετά το modulo 32, κ.λπ. μέχρι το modulo 2 α.

Παράδειγμα:

Επίλυση σύγκρισης Χ 2 ≡33 (mod 64)

64=2 6 . Ας ελέγξουμε αν η αρχική σύγκριση έχει λύση. 33≡1(mod 8), που σημαίνει ότι η σύγκριση έχει 4 λύσεις.

Modulo 8 αυτές οι λύσεις θα είναι: Χ≡±1(mod 8) και Χ≡±3(mod 8), το οποίο μπορεί να αναπαρασταθεί ως Χ=±(1+4 t 1). Ας αντικαταστήσουμε αυτήν την έκφραση με το modulo σύγκρισης 16

Χ 2 ≡33 (mod 16)

(1+4t 1) 2 ≡1 (mod 16)

1+8t 1 +16t 1 2 ≡1 (mod 16)

8t 1 ≡0 (mod 16)

t 1 ≡0 (mod 2)

Τότε η λύση θα πάρει τη μορφή Χ=±(1+4 t 1)=±(1+4(0+2 t 2))=±(1+8 t 2). Ας αντικαταστήσουμε τη λύση που προκύπτει με το modulo σύγκρισης 32:

Χ 2 ≡33 (mod 32)

(1+8t 2) 2 ≡1 (mod 32)

1+16t 2 +64t 2 2 ≡1 (mod 32)

16t 2 ≡0 (mod 32)

t 2 ≡0 (mod 2)

Τότε η λύση θα πάρει τη μορφή Χ=±(1+8 t 2) =±(1+8(0+2t 3)) =±(1+16 t 3). Ας αντικαταστήσουμε τη λύση που προκύπτει με το modulo σύγκρισης 64:

Χ 2 ≡33 (mod 64)

(1+16t 3) 2 ≡33 (mod 64)

1+32t 3 +256t 3 2 ≡33 (mod 64)

32t 3 ≡32 (mod 64)

t 3 ≡1 (mod 2)

Τότε η λύση θα πάρει τη μορφή Χ=±(1+16 t 3) =±(1+16(1+2t 4)) =±(17+32 t 4). Έτσι, modulo 64, η αρχική σύγκριση έχει τέσσερις λύσεις: Χ≡±17(mod 64)i Χ≡±49 (mod 64).

Ας δούμε τώρα μια γενική σύγκριση: Χ 2 ≡ένα(τροπ Μ), (ένα,Μ)=1, - κανονική επέκταση της ενότητας Μ. Σύμφωνα με το Θεώρημα της παραγράφου 4 της §4, αυτή η σύγκριση είναι ισοδύναμη με το σύστημα

Εάν κάθε σύγκριση αυτού του συστήματος είναι επιλύσιμη, τότε ολόκληρο το σύστημα είναι επιλύσιμο. Έχοντας βρει τη λύση σε κάθε σύγκριση αυτού του συστήματος, θα λάβουμε ένα σύστημα συγκρίσεων πρώτου βαθμού, λύνοντας το οποίο χρησιμοποιώντας το κινεζικό θεώρημα υπολοίπου, θα λάβουμε μια λύση στην αρχική σύγκριση. Επιπλέον, ο αριθμός των διαφορετικών λύσεων στην αρχική σύγκριση (αν είναι επιλύσιμη) είναι 2 κ, αν α=1, 2 κ+1 αν α=2, 2 κ+2 αν α≥3.

Παράδειγμα:

Επίλυση σύγκρισης Χ 2 ≡4 (mod 21).

Ορισμός 1. Αν δύο αριθμοί είναι 1) έναΚαι σιόταν διαιρείται με Πδώστε το ίδιο υπόλοιπο r, τότε αυτοί οι αριθμοί ονομάζονται εξισορροπημένο ή συγκρίσιμο σε συντελεστή Π.

Δήλωση 1. Αφήνω Πκάποιο θετικό νούμερο. Στη συνέχεια, κάθε αριθμός έναπάντα και, επιπλέον, με τον μόνο τρόπο μπορεί να αναπαρασταθεί στη μορφή

Αλλά αυτοί οι αριθμοί μπορούν να ληφθούν με ρύθμιση rίσο με 0, 1, 2,..., Π−1. Ως εκ τούτου sp+r=aθα πάρει όλες τις πιθανές ακέραιες τιμές.

Ας δείξουμε ότι αυτή η αναπαράσταση είναι μοναδική. Ας το προσποιηθούμε Πμπορεί να αναπαρασταθεί με δύο τρόπους a=sp+rΚαι a=s 1 Π+r 1 . Επειτα

(2)

Επειδή rΤο 1 δέχεται έναν από τους αριθμούς 0,1, ..., Π−1, τότε η απόλυτη τιμή r 1 −rπιο λιγο Π. Όμως από το (2) προκύπτει ότι r 1 −rπολλαπλούς Π. Ως εκ τούτου r 1 =rΚαι μικρό 1 =μικρό.

Αριθμός rπου ονομάζεται μείοναριθμοί ένα modulo Π(με άλλα λόγια, ο αριθμός rονομάζεται το υπόλοιπο ενός αριθμού έναεπί Π).

Δήλωση 2. Αν δύο αριθμοί έναΚαι σισυγκρίσιμο σε συντελεστή Π, Οτι α−βδιαιρείται με Π.

Πραγματικά. Αν δύο αριθμοί έναΚαι σισυγκρίσιμο σε συντελεστή Π, τότε όταν διαιρείται με Πέχουν το ίδιο υπόλοιπο Π. Επειτα

διαιρείται με Π, επειδή η δεξιά πλευρά της εξίσωσης (3) διαιρείται με Π.

Δήλωση 3. Αν η διαφορά δύο αριθμών διαιρείται με Π, τότε αυτοί οι αριθμοί είναι συγκρίσιμοι σε συντελεστή Π.

Απόδειξη. Ας υποδηλώσουμε με rΚαι r 1 διαίρεση υπόλοιπο έναΚαι σιεπί Π. Επειτα

Παραδείγματα 25≡39 (mod 7), −18≡14 (mod 4).

Από το πρώτο παράδειγμα προκύπτει ότι το 25 όταν διαιρείται με το 7 δίνει το ίδιο υπόλοιπο με το 39. Πράγματι, 25 = 3·7+4 (υπόλοιπο 4). 39=3·7+4 (υπόλοιπο 4). Όταν εξετάζετε το δεύτερο παράδειγμα, πρέπει να λάβετε υπόψη ότι το υπόλοιπο πρέπει να είναι ένας μη αρνητικός αριθμός μικρότερος από το συντελεστή (δηλαδή 4). Τότε μπορούμε να γράψουμε: −18=−5·4+2 (υπόλοιπο 2), 14=3·4+2 (υπόλοιπο 2). Επομένως, το −18 όταν διαιρείται με το 4 αφήνει υπόλοιπο 2 και το 14 όταν διαιρείται με το 4 αφήνει ένα υπόλοιπο 2.

Ιδιότητες συγκρίσεων modulo

Ιδιοκτησία 1. Για οποιονδηποτε έναΚαι ΠΠάντα

δεν υπάρχει πάντα σύγκριση

Οπου λ είναι ο μεγαλύτερος κοινός διαιρέτης των αριθμών ΜΚαι Π.

Απόδειξη. Αφήνω λ μεγαλύτερος κοινός διαιρέτης αριθμών ΜΚαι Π. Επειτα

Επειδή m(a−b)διαιρείται με κ, Οτι

Ως εκ τούτου

Και Μείναι ένας από τους διαιρέτες του αριθμού Π, Οτι

Οπου h=pqs.

Σημειώστε ότι μπορούμε να επιτρέψουμε συγκρίσεις με βάση αρνητικές ενότητες, π.χ. σύγκριση α≡β mod( Π) σημαίνει σε αυτή την περίπτωση ότι η διαφορά α−βδιαιρείται με Π. Όλες οι ιδιότητες των συγκρίσεων παραμένουν σε ισχύ για αρνητικές ενότητες.

Στο n δίνουν τα ίδια υπόλοιπα.

Ισοδύναμα σκευάσματα: α και β συγκρίσιμο σε συντελεστή n αν η διαφορά τους ένα - σιδιαιρείται με το n ή αν το a μπορεί να παρασταθεί ως ένα = σι + κn , Οπου κ- κάποιο ακέραιο. Για παράδειγμα: 32 και −10 είναι συγκρίσιμα modulo 7, αφού

Η δήλωση "a και b είναι συγκρίσιμα modulo n" γράφεται ως:

Ιδιότητες ισότητας Modulo

Η σχέση σύγκρισης modulo έχει τις ιδιότητες

Τυχόν δύο ακέραιοι αριθμοί έναΚαι σισυγκρίσιμο modulo 1.

Για τους αριθμούς έναΚαι σιήταν συγκρίσιμα σε συντελεστή n, είναι απαραίτητο και αρκετό η διαφορά τους να διαιρείται με n.

Εάν οι αριθμοί και είναι συγκρίσιμοι κατά ζεύγη σε συντελεστή n, τότε τα αθροίσματά τους και , καθώς και τα γινόμενα και είναι επίσης συγκρίσιμα σε συντελεστή n.

Αν οι αριθμοί έναΚαι σισυγκρίσιμο σε συντελεστή n, μετά τα πτυχία τους ένα κΚαι σι κείναι επίσης συγκρίσιμα σε συντελεστή nκάτω από κάθε φυσικό κ.

Αν οι αριθμοί έναΚαι σισυγκρίσιμο σε συντελεστή n, Και nδιαιρείται με Μ, Οτι έναΚαι σισυγκρίσιμο σε συντελεστή Μ.

Για τους αριθμούς έναΚαι σιήταν συγκρίσιμα σε συντελεστή n, παρουσιάζεται με τη μορφή της κανονικής αποσύνθεσής του σε απλούς παράγοντες Π Εγώ

απαραίτητο και επαρκές για να

Η σχέση σύγκρισης είναι μια σχέση ισοδυναμίας και έχει πολλές από τις ιδιότητες των συνηθισμένων ισοτήτων. Για παράδειγμα, μπορούν να προστεθούν και να πολλαπλασιαστούν: αν

Οι συγκρίσεις, ωστόσο, δεν μπορούν, σε γενικές γραμμές, να διαιρεθούν μεταξύ τους ή με άλλους αριθμούς. Παράδειγμα: , ωστόσο, μειώνοντας κατά 2, έχουμε μια λανθασμένη σύγκριση: . Οι κανόνες συντομογραφίας για συγκρίσεις είναι οι εξής.

Επίσης, δεν μπορείτε να εκτελέσετε λειτουργίες σε συγκρίσεις εάν οι μονάδες τους δεν ταιριάζουν.

Άλλες ιδιότητες:

Σχετικοί ορισμοί

Μαθήματα έκπτωσης

Το σύνολο όλων των αριθμών που μπορούν να συγκριθούν με ένα modulo nπου ονομάζεται τάξη έκπτωσης ένα modulo n , και συνήθως συμβολίζεται [ ένα] nή . Έτσι, η σύγκριση είναι ισοδύναμη με την ισότητα των κατηγοριών υπολειμμάτων [ένα] n = [σι] n .

Από τη σύγκριση modulo nείναι μια σχέση ισοδυναμίας στο σύνολο των ακεραίων, τότε οι κλάσεις υπολειμμάτων modulo nαντιπροσωπεύουν τάξεις ισοδυναμίας. ο αριθμός τους είναι ίσος n. Το σύνολο όλων των κατηγοριών υπολειμμάτων modulo nσυμβολίζεται με ή.

Οι πράξεις πρόσθεσης και πολλαπλασιασμού με επαγωγή αντίστοιχων πράξεων στο σύνολο:

[ένα] n + [σι] n = [ένα + σι] n

Σε σχέση με αυτές τις πράξεις το σύνολο είναι ένας πεπερασμένος δακτύλιος, και αν nαπλό - πεπερασμένο πεδίο.

Συστήματα έκπτωσης

Το σύστημα υπολειμμάτων σάς επιτρέπει να εκτελείτε αριθμητικές πράξεις σε ένα πεπερασμένο σύνολο αριθμών χωρίς να υπερβείτε τα όριά του. Πλήρες σύστημα εκπτώσεων modulo n είναι οποιοδήποτε σύνολο n ακεραίων που είναι ασύγκριτα modulo n. Συνήθως, τα μικρότερα μη αρνητικά υπολείμματα λαμβάνονται ως ένα πλήρες σύστημα υπολειμμάτων modulo n

0,1,...,n − 1

ή τις απόλυτες μικρότερες αφαιρέσεις που αποτελούνται από αριθμούς

,

σε περίπτωση περιττών nκαι αριθμοί

σε περίπτωση ακόμη n .

Επίλυση συγκρίσεων

Συγκρίσεις πρώτου βαθμού

Στη θεωρία αριθμών, στην κρυπτογραφία και σε άλλους τομείς της επιστήμης, το πρόβλημα της εύρεσης λύσεων σε συγκρίσεις πρώτου βαθμού της μορφής εμφανίζεται συχνά:

Η επίλυση μιας τέτοιας σύγκρισης ξεκινά με τον υπολογισμό του gcd (α, μ)=δ. Σε αυτήν την περίπτωση, είναι δυνατές 2 περιπτώσεις:

  • Αν σιόχι πολλαπλάσιο ρε, τότε η σύγκριση δεν έχει λύσεις.
  • Αν σιπολλαπλούς ρε, τότε η σύγκριση έχει ένα μοναδικό modulo λύσης Μ / ρε, ή, τι είναι το ίδιο, ρελύσεις modulo Μ. Σε αυτή την περίπτωση, ως αποτέλεσμα της μείωσης της αρχικής σύγκρισης κατά ρεη σύγκριση είναι:

Οπου ένα 1 = ένα / ρε , σι 1 = σι / ρε Και Μ 1 = Μ / ρε είναι ακέραιοι, και ένα 1 και Μ 1 είναι σχετικά πρώτοι. Επομένως ο αριθμός ένα 1 μπορεί να αναστραφεί modulo Μ 1, δηλαδή, βρείτε έναν τέτοιο αριθμό ντο, αυτό (με άλλα λόγια, ). Τώρα η λύση βρίσκεται πολλαπλασιάζοντας τη σύγκριση που προκύπτει επί ντο:

Πρακτικός υπολογισμός της αξίας ντομπορεί να εφαρμοστεί με διάφορους τρόπους: χρησιμοποιώντας το θεώρημα του Euler, τον αλγόριθμο του Ευκλείδη, τη θεωρία των συνεχιζόμενων κλασμάτων (βλ. αλγόριθμο) κ.λπ. Ειδικότερα, το θεώρημα του Euler σάς επιτρέπει να γράψετε την τιμή ντοόπως και:

Παράδειγμα

Για σύγκριση έχουμε ρε= 2, άρα modulo 22 η σύγκριση έχει δύο λύσεις. Ας αντικαταστήσουμε το 26 με το 4, συγκρίσιμο με αυτό το modulo 22, και στη συνέχεια να μειώσουμε και τους 3 αριθμούς κατά 2:

Εφόσον το 2 είναι συνπρωτογενές στο modulo 11, μπορούμε να μειώσουμε την αριστερή και τη δεξιά πλευρά κατά 2. Ως αποτέλεσμα, λαμβάνουμε ένα modulo λύσης 11: , που ισοδυναμεί με δύο λύσεις modulo 22: .

Συγκρίσεις δευτέρου βαθμού

Η επίλυση συγκρίσεων του δεύτερου βαθμού καταλήγει στο να ανακαλύψουμε αν ένας δεδομένος αριθμός είναι τετραγωνικό υπόλειμμα (χρησιμοποιώντας τον νόμο της τετραγωνικής αμοιβαιότητας) και στη συνέχεια στον υπολογισμό του συντελεστή τετραγωνικής ρίζας.

Ιστορία

Το θεώρημα του κινεζικού υπολοίπου, γνωστό εδώ και πολλούς αιώνες, δηλώνει (στη σύγχρονη μαθηματική γλώσσα) ότι ο συντελεστής δακτυλίου υπολειμμάτων το γινόμενο πολλών συμπρώτων αριθμών είναι