Ένας ακέραιος $k$ λέγεται κοινός διαιρέτης των $a$ και $b$, όταν ο $k$ διαιρεί ταυτόχρονα και τους δύο ακεραίους $a$ και $b$. Ένας από τους κοινούς διαιρέτες παίζει ιδιαίτερο ρόλο.
Μέγιστος Κοινός Διαιρέτης | Έστω $a$ και $b$ τυχόντες ακέραιοι. Ένας θετικός ακέραιος $d$ λέγεται μέγιστος κοινός διαιρέτης των $a$ και $b$ αν ικανοποιεί τις παρακάτω συνθήκες.
|
Η πρώτη συνθήκη του ορισμού αυτού επιβάλλει το θετικό ακέραιο $d$ σαν ένας κοινός διαιρέτης των $a$ και $b$. Η δεύτερη συνθήκη απαιτεί το $d$ να
διαιρείται από κάθε άλλο κοινό διαιρέτη, οπότε θα είναι ο μεγαλύτερος από όλους. Ο μέγιστος κοινός διαιρέτης των $a$ και $b$ συμβολίζεται με $(α, β)$
ή $\text{ΜΚΔ}(a, b)$.
Ο μέγιστος κοινός διαιρέτης υπάρχει για οποιουσδήποτε ακεραίους $a$ και $b$, και μάλιστα μπορεί να γραφεί στη μορφή
$d = ax + by$,
για κάποιους ακεραίους $x$ και $y$. Πρέπει, όμως, να τονίσουμε ότι οι ακέραιοι $x$ και $y$ δεν είναι μοναδικοί. Για παράδειγμα, εύκολα διαπιστώνεται ότι αν ισχύει $d = ax + by$, τότε θα ισχύει και η σχέση
\[ d = a \left(x + \frac{b}{d} u \right) + b \left(y - \frac{a}{d} u \right) \] για κάθε ακέραιο $u$.Μέγιστος Κοινός Διαιρέτης | Ένας θετικός ακέραιος $d$ λέγεται μέγιστος κοινός διαιρέτης των ακεραίων $a_{1}, a_{2}, \dots, a_{n}$, και συμβολίζεται με $d = a_{1}, a_{2}, \dots, a_{n})$, αν ικανοποιεί τις παρακάτω συνθήκες.
|
Όπως και στην περίπτωση δύο ακεραίων, ο μέγιστος κοινός διαιρέτης $d$ οσωνδήποτε ακεραίων $a_{1}, a_{2}, \dots, a_{n}$ υπάρχει, είναι μοναδικός, και μπορεί να γραφεί στη μορφή
\[ d = a_{1} x_{1}+a_{2} x_{2}+ \cdots + a_{n} x_{n} \] για κάποιους ακεραίους $x_{1}, x_{2}, \dots, x_{n}$, όμως και πάλι η παράσταση αυτή δεν είναι μοναδική.Αν ο μέγιστος κοινός διαιρέτης κάποιων ακεραίων $a_{1}, a_{2}, \dots, a_{n}$ πάρει τη μικρότερη δυνατή τιμή, δηλαδή γίνει $1$, λέμε ότι οι ακέραιοι $a_{1}, a_{2}, \dots, a_{n}$ είναι πρώτοι μεταξύ τους. Είναι σχεδόν προφανές ότι, οι ακέραιοι $a_{1}, a_{2}, \dots, a_{n}$ είναι πρώτοι μεταξύ τους αν και μόνον αν υπάρχουν ακέραιοι $x_{1}, x_{2}, \dots, x_{n}$, τέτοιοι ώστε να ισχύει η σχέση
\[ a_{1} x_{1}+a_{2} x_{2}+ \cdots + a_{n} x_{n} =1 \]Για το ΜΚΔ ισχύουν | Αν $a$ και $b$ είναι ακέραιοι, όχι ταυτόχρονα μηδέν, και $d = (a, b)$, τότε θα ισχύουν οι παρακάτω σχέσεις,
|
Επίσης εύκολα αποδεικνύεται ότι ισχύει
$a \mid bc$ και $(a, b) = 1 \Rightarrow a \mid c$
Παράδειγμα |
Η προηγούμενη συνεπαγωγή δεν ισχύει αν οι ακέραιοι $a$ και $b$ δεν είναι πρώτοι μεταξύ τους. Πράγματι, αν αγνοήσουμε την υπόθεση αυτή, ενδέχεται να καταλήξουμε σε συμπεράσματα, τα οποία δεν ισχύουν. Για παράδειγμα, από τη σχέση $12 \mid 24 \cdot 1$, δεν μπορούμε να συμπεράνουμε ότι το $12$ διαιρεί το $1$, διότι οι ακέραιοι $12$ και $24$ δεν είναι πρώτοι μεταξύ τους. Επίσης, ενώ ο ακέραιος $6$ διαιρεί το γινόμενο $2 \cdot 3$, εντούτοις ο $6$ δεν διαιρεί ούτε τον ακέραιο $2$, ούτε τον ακέραιο $3$. |
Με ανάλογο τρόπο μπορεί να οριστεί και το ελάχιστο κοινό πολλαπλάσιο ακεραίων.
Ελάχιστο Κοινό Πολλαπλάσιο | Ένας θετικός ακέραιος $m$ λέγεται ελάχιστο κοινό πολλαπλάσιο των ακεραίων $a_{1}, a_{2}, \dots, a_{n}$, και συμβολίζεται με $m = [a_{1}, a_{2}, \dots, a_{n}]$, αν ικανοποιεί τις παρακάτω συνθήκες.
|
Από την πρώτη συνθήκη, ο ακέραιος $m$ είναι ένα κοινό πολλαπλάσιο των $a_{1}, a_{2}, \dots, a_{n}$, ενώ η δεύτερη συνθήκη περιορίζει τον $m$ να είναι ο μικότερος από όλα τα κοινά πολλαπλάσια.
Όπως και στην περίπτωση του $\text{ΜΚΔ}$ το ελάχιστο κοινό πολλαπλάσιο ακεραίων υπάρχει πάντοτε, και είναι μοναδικό.
Για το ΕΚΠ ισχύουν | Αν $a$ και $b$ είναι τυχόντες ακέραιοι, και $m$ είναι ένας θετικός ακέραιος, τότε θα ισχύουν οι σχέσεις
|