Διαιρέτης

Ένας ακέραιος αριθμός $\delta$ ονομάζεται διαιρέτης ενός ακέραιου αριθμού $\alpha$, αν και μόνο αν υπάρχει ακέραιος αριθμός $\pi$, ο οποίος πολλαπλασιαζόμενος με τον $\delta$ δίνει αποτέλεσμα $\alpha$, δηλαδή $\,a=\pi \times \delta$. Συμβολίζεται $\,\delta |a$ και διαβάζεται: ο $\delta$ διαιρεί τον $\alpha$. Άλλες εκφράσεις που μπορούν να χρησιμοποιηθούν είναι: ο $\alpha$ διαιρείται ακριβώς με τον $\delta$, ή ότι το $\alpha$ είναι πολλαπλάσιο του $\delta$.

Για παράδειγμα λέγεται: ο 2 διαιρεί τον 6 (με πηλίκο 3) ή ο 6 διαιρείται ακριβώς από τον 2 ή ο 6 είναι πολλαπλάσιο του 2, διότι υπάρχει ο ακέραιος 3 έτσι ώστε: 6 = 3 Χ 2. Ακόμη και ο -2 διαιρεί τον 6, διότι υπάρχει ο ακέραιος -3 έτσι ώστε 6 = (-3) Χ (-2).

Η διαιρετότητα είναι μια από της βασικές έννοιες της θεωρίας αριθμών και αναφέρεται στην διαίρεση ακεραίων.

Ορισμός

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

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

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

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

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

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

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

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

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

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

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

Γενικά

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

Ιδιότητες

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

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

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

• Αν $a|b$ και $b|a$, τότε $a=b$ ή $a=-b$(δηλαδή $|a|=|b|$.

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

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

• Αν $a|b$ και $b|c$, τότε $a|c$ (μεταβατικότητα) (βλ. θεώρημα 2 παρακάτω)
• Αν $a|b$ και $b\neq 0$, τότε $|a|\leq |b|$
• Αν $a>0$και $a|b$ τότε $|a|\leq b$

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

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

• 7 είναι διαιρέτης του 42 γιατί υπάρχει ο ακέραιος 6 έτσι ώστε $7\times 6=42$και γράφεται συμβολικά: $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: «Ο διαιρέτης ενός ακεραίου είναι και διαιρέτης κάθε πολλαπλασίου του». Δηλαδή, αν $a,b\in \mathbb {Z}$ και $a|b$ $\Longrightarrow$ $a|bc$, $\forall c\in \mathbb {Z}$.

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

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

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

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

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

Δείτε επίσης

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

Πηγές

• Κάτος, Β., Στεφανίδης, Γ., (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.