Για δύο ακεραίους α και β θα λέμε ότι ο α διαιρεί τον β και1 θα συμβολίζουμε α|β όταν το αποτέλεσμα β/α είναι ακέραιος αριθμός.
Παράδειγμα ο 3 διαιρεί το 15 δηλαδή 3|15 γιατί 15/3=5 ακέραιος
Αν α, β, γ ακέραιοι αριθμοί, α|β και β|γ τότε α|γ 3|15 & 15|30 άρα 3|30
Επέκτασή του α, β, γ, χ, ψ ακέραιοι αριθμοί α|β, β|γ τότε α|(βχ+γψ)
Ευκλείδεια διαίρεση : για τους ακεραίους α και Δ με α>0 υπάρχουν δύο μοναδικοί ακέραιοι οι δ και υ τέτοιοι ώστε Δ = α x δ + υ. Ο υ, το υπόλοιπο της διαίρεσης, παίρνει τιμές 0 < υ < δ.
Παράδειγμα για α=8 και Δ=131 έχουμε 131 = 8x 16 + 3
Το υπόλοιπο της διαίρεσης των αριθμών α με τον n γράφεται mod^n)
Παράδειγμα mod (131,8) είναι 3. Δηλαδή το υπόλοιπο της διαίρεση του 131 με το 8 αφήνει υπόλοιπο 3.
Ισοϋπόλοιποι λέγονται δύο αριθμοί α και β κατά n αν η διαφορά τους α-β διαιρείται ακριβώς με τον n. Συμβολίζονται α≡β mod n.
Παράδειγμα 131 και 99 είναι ισοϋπόλοιποι κατά 8 γιατί το 131-99=32 διαιρείται ακριβώς με το 8.
α ±γ ≡ β ± ε mod n α x γ ≡ β x ε mod n συμπέρασμα αν ≡ βν mod n
Παραδείγματα : α=20 β=4 n=8 γ=131 ε=3
(20+131=151) ≡ (4+3=7) mod 8 151=18 x 8 + 7 και
(20x131=2620) ≡ (4x3=12) mod 8 2620=327 x 8 + 4 και 12=1 x 8 + 4 και (205=3200000)≡(45 =1024) mod8
Με βάση τον ορισμό των ισοϋπόλοιπων αριθμών mod(-a,n) το υπόλοιπο είναι ο θετικός εκείνος αριθμός β έτσι ώστε n|(p+a).
Παράδειγμα mod (-3,8) είναι 5 και mod (-30,8) είναι 2
Επομένως (131-20=111)≡(3-4=-1) mod 8 111=13 x 8 + 7 mod(-1,8)=7
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
Παράδειγμα ο 3 διαιρεί το 15 δηλαδή 3|15 γιατί 15/3=5 ακέραιος
Αν α, β, γ ακέραιοι αριθμοί, α|β και β|γ τότε α|γ 3|15 & 15|30 άρα 3|30
Επέκτασή του α, β, γ, χ, ψ ακέραιοι αριθμοί α|β, β|γ τότε α|(βχ+γψ)
Ευκλείδεια διαίρεση : για τους ακεραίους α και Δ με α>0 υπάρχουν δύο μοναδικοί ακέραιοι οι δ και υ τέτοιοι ώστε Δ = α x δ + υ. Ο υ, το υπόλοιπο της διαίρεσης, παίρνει τιμές 0 < υ < δ.
Παράδειγμα για α=8 και Δ=131 έχουμε 131 = 8x 16 + 3
Το υπόλοιπο της διαίρεσης των αριθμών α με τον n γράφεται mod^n)
Παράδειγμα mod (131,8) είναι 3. Δηλαδή το υπόλοιπο της διαίρεση του 131 με το 8 αφήνει υπόλοιπο 3.
Ισοϋπόλοιποι λέγονται δύο αριθμοί α και β κατά n αν η διαφορά τους α-β διαιρείται ακριβώς με τον n. Συμβολίζονται α≡β mod n.
Παράδειγμα 131 και 99 είναι ισοϋπόλοιποι κατά 8 γιατί το 131-99=32 διαιρείται ακριβώς με το 8.
Ιδιότητες ισοϋπόλοιπων αριθμών:
Έστω ότι α≡β mod n και γ≡ε mod n τότε ισχύουν :α ±γ ≡ β ± ε mod n α x γ ≡ β x ε mod n συμπέρασμα αν ≡ βν mod n
Παραδείγματα : α=20 β=4 n=8 γ=131 ε=3
(20+131=151) ≡ (4+3=7) mod 8 151=18 x 8 + 7 και
(20x131=2620) ≡ (4x3=12) mod 8 2620=327 x 8 + 4 και 12=1 x 8 + 4 και (205=3200000)≡(45 =1024) mod8
Με βάση τον ορισμό των ισοϋπόλοιπων αριθμών mod(-a,n) το υπόλοιπο είναι ο θετικός εκείνος αριθμός β έτσι ώστε n|(p+a).
Παράδειγμα mod (-3,8) είναι 5 και mod (-30,8) είναι 2
Επομένως (131-20=111)≡(3-4=-1) mod 8 111=13 x 8 + 7 mod(-1,8)=7
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
by: Πληροφορική Online
Πληροφορική Online Updated at: 2:04 μ.μ.