Διαιρέτης

Για τον ορισμό του διαιρέτη μπορούμε να χρησιμοποιήσουμε την πράξη του πολλαπλασιασμού ή την πράξη της διαίρεσης. Ο δεύτερος ορισμός πρέπει να αποφεύγεται γιατί δημιουργεί ασάφειες σε θέματα που αφορούν το 0 και αυτό γιατί δεν μπορεί να υπάρξει διαίρεση με 0. Η διαιρετότητα είναι μια σχέση μεταξύ των ακεραίων και όχι μια πράξη. Είναι μια σχέση όπως η ανισότητα, όπου λέμε ${\displaystyle a>\beta }$ (διότι από τον ορισμό της ανισότητας ${\displaystyle a-\beta >0}$ ), αλλά δεν «ταυτίζεται» με το αποτέλεσμα της πράξης της αφαίρεσης, που είναι ο αριθμός ${\displaystyle \mu =a-\beta }$ .^[3][4][5]

Ορισμός με την πράξη του πολλαπλασιασμού

Ένας ακέραιος αριθμός ${\displaystyle \delta }$ ονομάζεται διαιρέτης ενός ακέραιου αριθμού ${\displaystyle \alpha }$ , αν και μόνο αν υπάρχει ακέραιος αριθμός ${\displaystyle \pi }$ , ο οποίος πολλαπλασιαζόμενος με τον ${\displaystyle \delta }$ δίνει αποτέλεσμα ${\displaystyle \alpha }$ , δηλαδή ${\displaystyle \,a=\pi \times \delta }$ , όπου (${\displaystyle \times }$ ) το σύμβολο της πράξης του πολλαπλασιασμού.^{[Σημ 1]} Συμβολίζεται ${\displaystyle \,\delta |a}$ , δηλαδή με μια κάθετο ανάμεσα στο ${\displaystyle \delta }$ και το ${\displaystyle \alpha }$ , ^[1][2][6][7]

Το σύμβολο της διαιρετότητας ${\displaystyle \,\delta |a}$ δεν πρέπει να συγχέεται με το σύμβολο της διαίρεσης (${\displaystyle a/\delta }$ ή ${\displaystyle {\frac {a}{\delta }}}$ ).^[8]

Στην περίπτωση που ο ${\displaystyle \delta }$ δεν είναι διαιρέτης του ${\displaystyle \alpha }$ συμβολίζεται ${\displaystyle \,\delta \nmid a}$ και διαβάζεται: ο ${\displaystyle \delta }$ δεν διαιρεί τον ${\displaystyle \alpha }$ .^[1]

Διατύπωση του ορισμού με μαθηματική σημειογραφία: ${\displaystyle a,\delta \in \mathbb {Z} }$ , ${\displaystyle \,\delta |a}$ ${\displaystyle \Longleftrightarrow }$ ${\displaystyle \exists \ \pi \in \mathbb {Z} :a=d\times \pi }$ ^[9] και ${\displaystyle a,\delta \in \mathbb {Z} }$ , ${\displaystyle \,\delta \nmid a}$ ${\displaystyle \Longleftrightarrow }$ ${\displaystyle \nexists \ \pi \in \mathbb {Z} :a=d\times \pi }$ ^{[Σημ 2]}

Ο ${\displaystyle \pi }$ , γενικά στην πράξη της διαίρεσης λέγεται πηλίκο. Στην περίπτωση που ${\displaystyle \delta \not \in \{1,a,-1,-a\}}$ , το ${\displaystyle \delta }$ λέγεται και παράγοντας του ${\displaystyle \alpha }$ .^[1][2]

Ορισμός με την πράξη της διαίρεσης

Ένας άλλος ορισμός είναι με την χρήση της διαίρεσης: «Ένας ακέραιος αριθμός ${\displaystyle \delta \neq 0}$ ονομάζεται διαιρέτης ενός ακέραιου αριθμού ${\displaystyle \alpha }$ , αν και μόνο αν η διαίρεση ${\displaystyle {\frac {a}{\delta }}}$ είναι τέλεια. Δηλαδή το αποτέλεσμα είναι ακέραιος (${\displaystyle \delta \neq 0,a,\delta \in \mathbb {Z} ,\delta |a\Longleftrightarrow {\frac {a}{\delta }}\in \mathbb {Z} }$ )», θέτοντας έτσι τον σημαντικό περιορισμό του ${\displaystyle \delta \neq 0}$ .^[10][11][12]

Ο ορισμός αυτός μας οδηγεί στα ίδια αποτελέσματα με τον προηγούμενο απορρίπτοντας όμως την ιδιότητα: «αν ${\displaystyle 0|a}$ , τότε ${\displaystyle a=0}$ », που λέει ότι το 0 είναι διαιρέτης του εαυτού του και αυτό διότι η διαίρεση ${\displaystyle {\frac {a}{0}}}$ δεν ορίζεται.^[12]

Στην βιβλιογραφία συναντάμε ορισμό της διαιρετότητας με την πράξη της διαίρεσης και επιπλέον μπορεί να δέχεται ότι κάθε ακέραιος είναι διαιρέτης του μηδενός («${\displaystyle a|0}$ για κάθε ${\displaystyle a\in \mathbb {Z} }$  »), θέση που είναι λάθος.^[13]

• Συνήθως αναφερόμαστε μόνο στους θετικούς διαιρέτες ενός ακεραίου αριθμού, ενώ στην πραγματικότητα διαιρέτες είναι και οι αντίστοιχοι αρνητικοί.^[14] Για παράδειγμα, οι διαιρέτες του 4 δεν είναι μόνο οι 1, 2, και 4, αλλά και οι -1, -2 και -4. Δηλαδή το 4 έχει 6 διαιρέτες.^[1][15] Επειδή ότι ισχύει για τους θετικούς διαιρέτες ισχύει και για τους αρνητικούς, συνήθως για λόγους απλοποίησης αναφερόμαστε μόνο στους θετικούς.^[16][17]
• Ένας ακέραιος και ο αντίθετος του έχουν τους ίδιους διαιρέτες. Για παράδειγμα αντίθετος του 4, δηλαδή ο -4 έχει τους ίδιους διαιρέτες με τον 4.
• Οι ακέραιοι που διαιρούνται με το 2 ονομάζονται άρτιοι ή ζυγοί, ενώ αυτοί που δεν διαιρούνται με το 2 ονομάζονται περιττοί ή μονοί. Επειδή κάθε ακέραιος είναι διαιρέτης του 0 (μηδέν),^[18] το 0 διαιρείται με το 2, οπότε το 0 συγκαταλέγεται στους άρτιους αριθμούς.
• Κάθε ακέραιος ${\displaystyle \alpha }$ διαιρείται με τον εαυτό του, με τον αντίθετό του (${\displaystyle -\alpha }$ ) , το 1 και το -1. Αυτοί οι διαιρέτες ενός ακεραίου ονομάζονται τετριμμένοι διαιρέτες. Δηλαδή, οι τετριμμένοι διαιρέτες του ακεραίου ${\displaystyle \alpha }$ είναι οι ${\displaystyle \alpha ,-\alpha ,-1}$ και ${\displaystyle -1}$ .^[1][2]
• Οι μή τεριμμένοι διαιρέτες ενός ακεραίου ονομάζονται παράγοντες του ακεραίου.^[1][2]
• Το σύνολο των διαιρετών ενός αριθμού μπορεί να βρεθεί με την ανάλυση σε γινόμενο πρώτων παραγόντων (βλ. και θεμελιώδες θεώρημα αριθμητικής).

Λόγω του ορισμού για ${\displaystyle a,b,c\in \mathbb {Z} }$ ισχύουν τα ακόλουθα:

• ${\displaystyle a|0}$ για κάθε ${\displaystyle a\neq 0}$ (διότι: ${\displaystyle \exists 0\in \mathbb {Z} :0=a\times 0}$ ).^[9][10][18] Από αυτή την ιδιότητα προκύπτει ότι το 0 είναι άρτιος, διότι ${\displaystyle 2\in \mathbb {Z} }$ και άρα ${\displaystyle 2|0}$ .
• Αν ${\displaystyle 0|a}$ , τότε ${\displaystyle a=0}$ .^[9] Είναι μια «ξεχωριστή» ιδιότητα που μας λέει ότι ${\displaystyle 0|0}$ (το μηδέν είναι διαιρέτης του μηδέν). Δεν ισχύει αν στον ορισμό του διαιρέτη κάνουμε χρήση της έννοιας της διαίρεσης (βλ. ορισμός με την πράξη της διαίρεσης, παραπάνω).^[19] Άλλο ${\displaystyle 0|0}$ και άλλο το μη οριζόμενο^[20] ${\displaystyle {\frac {0}{0}}}$ .^[12]
• ${\displaystyle a|b\Leftrightarrow -a|b\Leftrightarrow a|-b\Leftrightarrow \left\vert a\right\vert |\left\vert b\right\vert }$ ^[9]
• ${\displaystyle 1|a}$ , ${\displaystyle -1|a}$ , ${\displaystyle a|a}$ και ${\displaystyle -a|a}$ για κάθε α (τετριμμένοι διαιρέτες).^[9][10]
• Αν ${\displaystyle a|b}$ , τότε ${\displaystyle ac|bc}$ για κάθε c.^[9][10]

Για ${\displaystyle a,b,c,d\in \mathbb {Z} }$ εύκολα αποδεικνύονται τα ακόλουθα:

• Αν ${\displaystyle a|b}$ και ${\displaystyle b|a}$ , τότε ${\displaystyle a=b}$ ή ${\displaystyle a=-b}$ (δηλαδή ${\displaystyle |a|=|b|}$ .^[21][22][9]

• Αν ${\displaystyle a|b}$ και ${\displaystyle c|d}$ , τότε ${\displaystyle ac|bd}$ ^[9]
• Αν ${\displaystyle a|b}$ τότε ${\displaystyle a|bc}$ ^[9] (βλ. θεώρημα 1 παρακάτω)
• Αν ${\displaystyle a|b}$ και ${\displaystyle a|c}$ , τότε ${\displaystyle a|(b+c)}$ .^[9] Γενικότερα ${\displaystyle a|(mb+nc)}$ για κάθε ${\displaystyle m,n\in \mathbb {Z} }$ (βλ. θεώρημα 3 παρακάτω). Ο ${\displaystyle a}$ λέγεται κοινός διαιρέτης των ${\displaystyle b}$ και ${\displaystyle c}$ .^[21][22] Ο ακέραιος ${\displaystyle mb+nc}$ , λέγεται ${\displaystyle \mathbb {Z} }$ -γραμμικός συνδυασμός (linear combination) των ${\displaystyle b}$ και ${\displaystyle c}$ .^[23][24]

Ειδική περίπτωση της προηγούμενης ιδιότητας είναι ότι: αν ${\displaystyle a|b}$ και ${\displaystyle a|c}$ , τότε ${\displaystyle a|(b-c)}$ .^[25]

• Αν ${\displaystyle a|b}$ και ${\displaystyle b|c}$ , τότε ${\displaystyle a|c}$ (μεταβατικότητα)^[9][10] (βλ. θεώρημα 2 παρακάτω)
• Αν ${\displaystyle a|b}$ και ${\displaystyle b\neq 0}$ , τότε ${\displaystyle |a|\leq |b|}$ ^[9][21]
• Αν ${\displaystyle a>0}$ και ${\displaystyle a|b}$ τότε ${\displaystyle |a|\leq b}$ ^[1]

Στο παράδειγμα θα χρησιμοποιήσουμε τον θετικό ακέραιο 42 επειδή είναι εύκολος στους υπολογισμούς.

• 7 είναι διαιρέτης του 42 γιατί υπάρχει ο ακέραιος 6 έτσι ώστε ${\displaystyle 7\times 6=42}$ και γράφεται συμβολικά: ${\displaystyle 7\mid 42}$ . Μπορεί να λεχθεί ότι ο 42 διαιρείται ακριβώς ή απλά διαιρείται με τον 7, ή ότι ο 42 είναι πολλαπλάσιος του 7, ή ότι ο 7 διαιρεί τον 42.
• Οι διαιρέτες του 42 είναι οι 1, 2, 3, 6, 7, 21, 42, -1, -2, -3, -6, -7, -21 και -42. Οι ίδιοι ακέραιοι είναι και διαιρέτες του -42.
• Οι τετριμμένοι διαιρέτες του 42 είναι οι 42, -42, 1 και -1.
• Οι μη τετριμμένοι διαιρέτες του 42 είναι οι 2, 3, 6, 7, 21, 42, -1, -2, -3, -6, -7 και -21.
• Επειδή ο 7 δεν είναι τετριμμένος διαιρέτης του 42, ο 7 είναι παράγοντας του 42.

Εύκολα αποδεικνύονται τα θεωρήματα:

• Θεώρημα 1: «Ο διαιρέτης ενός ακεραίου είναι και διαιρέτης κάθε πολλαπλασίου του». Δηλαδή, αν ${\displaystyle a,b\in \mathbb {Z} }$ και ${\displaystyle a|b}$ ${\displaystyle \Longrightarrow }$ ${\displaystyle a|bc}$ , ${\displaystyle \forall c\in \mathbb {Z} }$ .

Απόδειξη: ${\displaystyle a|b}$ ${\displaystyle {\xrightarrow {o\rho .}}}$ ${\displaystyle \exists \ \kappa \in \mathbb {Z} :b=a\kappa }$ ${\displaystyle {\xrightarrow[{}]{\forall c\in \mathbb {Z} ,\ bc=(a\kappa )c=a(\kappa c)}}}$ ${\displaystyle \exists \ \mu =\kappa c\in \mathbb {Z} :bc=a\mu }$ ${\displaystyle {\xrightarrow {o\rho .}}}$ ${\displaystyle a|bc}$ .^[26]

• Θεώρημα 2: «Μεταβατικότητα». Δηλαδή, αν ${\displaystyle a,b,c\in \mathbb {Z} }$ όταν ${\displaystyle a|b}$ και ${\displaystyle b|c}$ ${\displaystyle \Longrightarrow }$ ${\displaystyle a|c}$ .

Απόδειξη: ${\displaystyle a|b}$ και ${\displaystyle b|c}$ ${\displaystyle {\xrightarrow {o\rho .}}}$ ${\displaystyle \exists \ \kappa ,\lambda \in \mathbb {Z} :b=a\kappa ,\ c=b\lambda }$ ${\displaystyle \longrightarrow }$ ${\displaystyle c=b\lambda =(a\kappa )\lambda =a(\kappa \lambda )}$ ${\displaystyle \longrightarrow }$ ${\displaystyle \exists \ \mu =\kappa \lambda \in \mathbb {Z} :c=a\mu }$ ${\displaystyle {\xrightarrow {o\rho .}}}$ ${\displaystyle a|c}$ .^[27]

• Θεώρημα 3: «Ο κοινός διαιρέτης δύο ακεραίων είναι και διαιρέτης κάθε ${\displaystyle \mathbb {Z} }$ -γραμμικού συνδυασμού τους». Δηλαδή, αν ${\displaystyle a|b}$ και ${\displaystyle a|c}$ ${\displaystyle \Longrightarrow }$ ${\displaystyle a|(mb+nc)}$ , ${\displaystyle \forall \ m,n\in \mathbb {Z} }$ .

Απόδειξη: ${\displaystyle a|b}$ , ${\displaystyle a|c}$ ${\displaystyle {\xrightarrow {o\rho .}}}$ ${\displaystyle \exists \ \kappa ,\lambda \in \mathbb {Z} :b=a\kappa ,\ c=a\lambda }$ ${\displaystyle \longrightarrow }$ ${\displaystyle \forall \ m,n\in \mathbb {Z} }$ , ${\displaystyle mb+nc=m(a\kappa )+n(a\lambda )}$ ${\displaystyle =a(m\kappa )+a(n\lambda )}$ ${\displaystyle =a(m\kappa +n\lambda )}$ ${\displaystyle {\xrightarrow {o\rho .}}}$ ${\displaystyle a|(mb+nc)}$ .^[23]

• Αριθμητική
• Διαίρεση
• Μέγιστος κοινός διαιρέτης
• Ελάχιστο κοινό πολλαπλάσιο

• Κάτος, Β., Στεφανίδης, Γ., (2003). «Τεχνικές Κρυπτογραφίας και Κρυπτανάλυσης. 3.Θεωρία αριθμών - αλγεβρικές δομές», σελ. 1, Εκδόσεις: ΖΥΓΟΣ, (ISBN 960-8065-40-2). Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.

• Δρ. Κίτσος Παρασκευάς, Επίκουρος Καθηγητής, (Αντίρριο 2017). «Κρυπτογραφία και ασφάλεια υπολογιστών» από openeclass.teimes.gr. Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.
• Συγκελάκης Γ. Αλέξανδρος, (Νοέμβριος 2012) «Εισαγωγή στη Θεωρία Αριθμών για το Λύκειο» από emekorinthias.files.wordpress.com. Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.
• (Αγγλικά) Conrad Keith. Divisibility and greatest common divisor από kconrad.math.uconn.edu. Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.