<
Μαθηματικά (Β΄ Λυκείου Θετικών Σπουδών) - Βιβλίο Μαθητή

4.4 ΜΕΓΙΣΤΟΣ ΚΟΙΝΟΣ ΔΙΑΙΡΕΤΗΣ - ΕΛΑΧΙΣΤΟ ΚΟΙΝΟ ΠΟΛΛΑΠΛΑΣΙΟ

Μέγιστος Κοινός Διαιρέτης

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

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


ΟΡΙΣΜΟΣ

Έστω α και β δύο ακέραιοι, από τους οποίους ένας τουλάχιστον είναι διάφορος του μηδενός. Ορίζουμε ως μέγιστο κοινό διαιρέτη (Μ.Κ.Δ.) των α και β , και τον συμβολίζουμε με (α, β) , το μεγαλύτερο1 από τους θετικούς κοινούς διαιρέτες τους.

Δηλαδή, ο Μ.Κ.Δ. δύο ακεραίων α και β είναι ο μοναδικός θετικός ακέραιος δ που έχει τις επόμενες δύο ιδιότητες:

Εικόνα

Από τον παραπάνω ορισμό προκύπτει ότι

Εικόνα

Έτσι ,για παράδειγμα, αν α= -12 και β=30, τότε ( -12,30)=(12,30)=6 , αφού οι θετικοί διαιρέτες του 12 είναι οι 1,2,3,4,6,12 , του 30 οι 1,2,3,5,6,10,15,30 και ο μεγαλύτερος κοινός διαιρέτης τους είναι ο 6.

Παρατηρούμε επίσης ότι:

• Για κάθε θ ε τ ι κ ό ακέραιο α ισχύει (α,α)= α, (α,0)=α και (α,1)=1 .

• Αν α, β είναι δύο θ ε τ ι κ ο ί ακέραιοι με Εικόνα , τότε (α,β)= β .

Δύο ακέραιοι α και β , που έχουν μέγιστο κοινό διαιρέτη τη μονάδα, για τους οποίους δηλαδή ισχύει (α,β)= 1 , λέγονται πρώτοι μεταξύ τους. Για παράδειγμα, οι 28 και 15 είναι πρώτοι μεταξύ τους, αφού (28,15)=1 .

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


ΘΕΩΡΗΜΑ 3

Αν α, β είναι δύο φυσικοί αριθμοί και υ είναι το υπόλοιπο της ευκλείδειας διαίρεσης του α με τον β , τότε

1 Αποδεικνύεται ότι: "Κάθε πεπερασμένο υποσύνολο του R έχει μέγιστο στοιχείο".

Εικόνα

ΑΠΟΔΕΙΞΗ

Έστω Εικόνα η ισότητα της ευκλείδειας διαίρεσης του α με τον β . Αν και Εικόνα , τότε:

Εικόνα

Ας χρησιμοποιήσουμε το παραπάνω θεώρημα στον υπολογισμό του Μ.Κ.Δ. των 111 και 78. Εφαρμόζοντας διαδοχικά την ευκλείδεια διαίρεση έχουμε:

Εικόνα

Επομένως,

Εικόνα


δηλαδή (111,78)=3 , που είναι και το τελευταίο μη μηδενικό υπόλοιπο των διαδοχικών διαιρέσεων.

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

Εικόνα


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

Εικόνα
Εικόνα


Τότε ισχύει (α,β)=υv . Αυτό προκύπτει από τη διαδοχική εφαρμογή του προηγούμενου θεωρήματος, σύμφωνα με το οποίο

Εικόνα


Επομένως, ο Μ.Κ.Δ. των α και β είναι το τελευταίο θετικό υπόλοιπο των παραπάνω αλγοριθμικών διαίρεσεων.

Η διαδικασία αυτή αποτελεί τον ευκλείδειο αλγόριθμο και χρησιμοποιείται γενικότερα για τον προσδιορισμό του Μ.Κ.Δ. δύο οποιωνδήποτε ακεραίων.

Από τον παραπάνω αλγόριθμο μπορεί να προκύψει η πολύ σημαντική ιδιότητα του Μ.Κ.Δ. δύο αριθμών α, β, ότι δηλαδή αυτός μπορεί να εκφραστεί ως γραμμικός συνδυασμός των α και β.

Για παράδειγμα, από τη διαδικασία προσδιορισμού του Μ.Κ.Δ. των α=111 και β=78 έχουμε:

Εικόνα

Επομένως,

Εικόνα

Ώστε

Εικόνα

Γενικά, ισχύει:


ΘΕΩΡΗΜΑ 4

Αν δ είναι ο Μ.Κ.Δ. των α και β , τότε υπάρχουν ακέραιοι κ και λ, τέτοιοι, ώστε
                                                            Εικόνα

Δηλαδή, ο Μ.Κ.Δ. δύο ακέραιων μπορεί να γραφεί ως γραμμικός συνδυασμός των ακεραίων αυτών.

Οι ακέραιοι κ και λ δεν είναι μοναδικοί. Για παράδειγμα για το Μ.Κ.Δ. των 111 και 78 είναι Εικόνα αλλά και Εικόνα.

ΠΟΡΙΣΜΑ 1

Δύο ακέραιοι α, β είναι πρώτοι μεταξύ τους, αν και μόνο αν υπάρχουν ακέραιοι κ, λ , τέτοιοι, ώστε
                                                            Εικόνα

ΑΠΟΔΕΙΞΗ

Εικόνα

Αν κα + λβ= δ είναι η γραμμική έκφραση του μέγιστου κοινού διαιρέτη των ακεραίων α και β, τότε Εικόνα , που σημαίνει ότι Εικόνα.

Δηλαδή:

"Αν διαιρέσουμε δύο ακέραιους με το Μ.Κ.Δ. τους, προκύπτουν αριθμοί πρώτοι μεταξύ τους".


ΠΟΡΙΣΜΑ 2

Οι κοινοί διαιρέτες δύο ακεραίων α και β είναι οι διαιρέτες του μέγιστου κοινού διαιρέτη τους.

ΑΠΟΔΕΙΞΗ

Έστω δ=(α,β) . Προφανώς κάθε διαιρέτης του δ είναι και κοινός διαιρέτης των α και β . Αλλά και αντιστρόφως, κάθε κοινός διαιρέτης δ' των α και β είναι και διαιρέτης του Μ.Κ.Δ. των α,β. Πράγματι, αν κα + λβ=δ είναι η γραμμική έκφραση του δ , τότε Εικόνα

Για παράδειγμα, επειδή (150,120)=30 , οι θετικοί κοινοί διαιρέτες των 150 και 120 είναι οι διαιρέτες του 30, δηλαδή οι ακέραιοι 1,2,3,5,6,10,15 και 30.

ΠΟΡΙΣΜΑ 3

Αν για τους ακεραίους α,β,γ ισχύει Εικόνα και (α,β)=1 , τότε Εικόνα.

Δηλαδή, αν ένας ακέραιος διαιρεί το γινόμενο δύο ακεραίων και είναι πρώτος προς τον έναν, τότε διαιρεί τον άλλο.

ΑΠΟΔΕΙΞΗ

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


Η συνθήκη (α,β)=1 είναι αναγκαία, για να ισχύει το θεώρημα. Για παράδειγμα, ενώ Εικόνα.


Η έννοια του μέγιστου κοινού διαιρέτη γενικεύεται και για περισσότερους από δύο ακεραίους. Συγκεκριμένα, αν α123,...αv, ακέραιοι με έναν τουλάχιστον διάφορο του μηδενός, τότε ορίζουμε ως μέγιστο κοινό διαιρέτη αυτών, και τον συμβολίζουμε με 123,...αv), τον μεγαλύτερο από τους θετικούς κοινούς διαιρέτες τους. Αποδεικνύεται ότι:

"Ο Μ.Κ.Δ. τριών ή περισσότερων ακεραίων δε μεταβάλλεται αν αντικαταστήσουμε δύο από αυτούς με το μέγιστο κοινό διαιρέτη τους".

Για παράδειγμα (24,12,16)=((24,16),12)=(8,12)=4


Για το Μ.Κ.Δ. περισσότερων από δύο ακεραίους ισχύουν ανάλογες ιδιότητες με τις ιδιότητες του Μ.Κ.Δ. δύο ακεραίων. Έτσι ,για παράδειγμα, για τρεις ακέραιους α,β,γ αποδεικνύεται ότι:

Εικόνα

ΕΦΑΡΜΟΓΕΣ

1. Να αποδειχτεί ότι για τους ακεραίους α,β,κ ισχύουν

(i) (α,β)=(α -κβ,β)

(ii) (α,β)=(α -β,β)

(iii) (α,α +1)=1.

(i) Έστω δ=(α,β) και δ'=(α -κβ,β) , τότε

Εικόνα

Από (1) και (2) έπεται ότι δ=δ'.
(ii) Λόγω της (i) , για κ=1 , ισχύει (α,β)=(α -β,β) .
(iii) Είναι: (α,α +1)=(α,α+1 -α)=1 .


2. Αν για τους ακεραίους α,β,γ ισχύει Εικόνα.

ΑΠΟΔΕΙΞΗ

Επειδή (α,β)=1 , υπάρχουν ακέραιοι κ,λ με κα + λβ=1 . Επομένως,

Εικόνα

Όμως, Εικόνα, επομένως, γ=μα και γ=νβ . Έτσι, η (1) γίνεται κν(αβ)+λ(αβ)=γ . Άρα Εικόνα .


3. (i) Αν Εικόνα , να αποδειχτεί ότι (κα,κβ)=κ(α,β) .
(ii) Να βρεθεί ο Μ.Κ.Δ. των 63 και 84.

ΑΠΟΔΕΙΞΗ

(i) Έστω (α,β)=δ και (κα,κβ)=δ' . Αρκεί να δείξουμε ότι Εικόνα.Επειδή Εικόνα, έχουμε Εικόνα. Άρα Εικόνα .

Αφού δ=(α,β) , υπάρχουν ακέραιοι μ και ν με μα+νβ=δ και επομένως, κμα+κνβ=κδ . Όμως Εικόνα. Άρα Εικόνα .

(ii) Έχουμε

Εικόνα

Ελάχιστο Κοινό Πολλαπλάσιο Ακεραίων

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


ΟΡΙΣΜΟΣ

Έστω δύο ακέραιοι α και β, διαφορετικοί από το μηδέν. Ορίζουμε ως ελάχιστο κοινό πολλαπλάσιο (Ε.Κ.Π.) των α και β, και το συμβολίζουμε με Εικόνα , το μικρότερο από τα θετικά κοινά πολλαπλάσια των α και β.

Επομένως, το Ε.Κ.Π. δύο μη μηδενικών ακεραίων α και β είναι ο μοναδικός θετικός ακέραιος ε που έχει τις επόμενες δύο ιδιότητες:

Εικόνα


Από τον ορισμό προκύπτει ότι

Εικόνα


Έτσι, για παράδειγμα, για τους ακεραίους -4 και 6 έχουμε [ -4,6]=[4,6]=12 , αφού τα θετικά πολλαπλάσια του 4 είναι 4,8,12,16,20,24,28,..., του 6 είναι τα 6,12,18,24,30,36,..., τα θετικά κοινά τους πολλαπλάσια είναι 12,24,36,... και το μικρότερο θετικό κοινό πολλαπλάσιο είναι το 12.

Παρατηρούμε επίσης ότι για θ ε τ ι κ ο ύ ς ακεραίους α, β ισχύει:

• Αν Εικόνα , τότε [α,β]= α .
• [α,1]=α.


ΘΕΩΡΗΜΑ 5

Αν α, β είναι δύο θ ε τ ι κ ο ί ακέραιοι, τότε
Εικόνα


ΑΠΟΔΕΙΞΗ *

Αν (α,β)=δ , αρκεί να δείξουμε ότι Εικόνα , αρκεί δηλαδή να δείξουμε ότι

Εικόνα

Επειδή (α,β)=δ , υπάρχουν θετικοί ακέραιοι μ και ν με α=μδ και β=vδ . Επομένως,

Εικόνα


Αν x είναι ένα θετικό κοινό πολλαπλάσιο των α και β , τότε x=ρα και x=σβ , όπου ρ και σ θετικοί ακέραιοι. Ξέρουμε επίσης ότι υπάρχουν ακέραιοι κ,λ με δ=κα+λβ . Έτσι, αν θέσουμε Εικόνα , τότε θα έχουμε

Εικόνα

Αν Εικόνα , τότε από τις ισότητες Εικόνα, έχουμε

Εικόνα

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

• Αν οι ακέραιοι α και β είναι πρώτοι μεταξύ τους, τότε Εικόνα.

Δηλαδή:

"Το Ε.Κ.Π. δύο πρώτων μεταξύ τους ακεραίων είναι το γινόμενο των απόλυτων τιμών τους".

Για παράδειγμα, Εικόνα.


• Το Ε.Κ.Π. δύο ακέραιων α,β διαιρεί κάθε άλλο κοινό πολλαπλάσιο x των α και β, δηλαδή είναι x=πολ[α,β]. Άρα:

"Τα κοινά πολλαπλάσια δύο ακεραίων είναι τα πολλαπλάσια του Ε.Κ.Π.".

Για παράδειγμα, τα κοινά πολλαπλάσια των 4 και 6 είναι πολλαπλάσια του [4,6]=12 , δηλαδή οι ακέραιοι Εικόνα

Η έννοια του ελάχιστου κοινού πολλαπλάσιου γενικεύεται και για περισσότερους από δύο ακεραίους. Συγκεκριμένα, αν Εικόνα, τότε ορίζουμε ως ελάχιστο κοινό πολλαπλάσιο (Ε.Κ.Π.) των ,α123,...,αv , και το συμβολίζουμε με [α123,...,αv] , το μικρότερο από τα θετικά κοινά τους πολλαπλάσια. Αποδεικνύεται ότι:

"Το ελάχιστο κοινό πολλαπλάσιο τριών ή περισσότερων ακεραίων δε μεταβάλλεται, αν αντικαταστήσουμε δύο από αυτούς με το ελάχιστο κοινό τους πολλαπλάσιο".

Για παράδειγμα, [4,6,16]= [[4,6],16]=[12,16]=48 .


ΕΦΑΡΜΟΓΗ

1. i) Να αποδειχτεί ότι [κα,κβ]=κ[α,β] για κάθε θετικό ακέραιο κ.

ii) Να βρεθεί το Ε.Κ.Π. των 120 και 150.

ΑΠΟΔΕΙΞΗ

(i) Έχουμε Εικόνα

(ii) Έχουμε Εικόνα

Ασκήσεις

Α' ΟΜΑΔΑΣ
1.

Να βρείτε το Μ.Κ.Δ. των ακεραίων α,β και να τον εκφράσετε ως γραμμικό συνδυασμό των α,β σε καθεμιά από τις παρακάτω περιπτώσεις

Εικόνα
2.

Να αποδείξετε ότι:

Εικόνα
3.

Να αποδείξετε ότι Εικόνα .

4.

Έστω Εικόνα. Να αποδείξετε ότι (α+β, x+y)=1 .

5.

Να αποδείξετε ότι

Εικόνα
6.

Να αποδείξετε ότι για κάθε Εικόνα ισχύει:

Εικόνα
7.

Να αποδείξετε ότι (α, β, α+β)=(α,β)

8.

Να βρείτε το θετικό ακέραιο α για τον οποίο ισχύει

Εικόνα
9.

Αν Εικόνα, να αποδείξετε ότι (α,γ)=(β,γ)=1 .


Β' ΟΜΑΔΑΣ
1.

Αν (α,β)=1 , να αποδείξετε ότι:

Εικόνα
2.

Αν (α,4)=2 και(β,4)=2 , να αποδείξετε ότι (α +β,4)=4 .

3.

Να εξετάσετε αν υπάρχουν θετικοί ακέραιοι ν , για τους οποίους το κλάσμα Εικόνα απλοποιείται.

4.

Έστω Εικόνα. Να αποδείξετε ότι: Εικόνα.

5.

Ένας μαθητής στην προσπάθειά του να βρει το Μ.Κ.Δ. τριών ακεραίων α,β,γ βρήκε:

Εικόνα

Μπορείτε να απαντήσετε αν έκανε ή όχι λάθος;

6.

Έστω Εικόνα με (α,β)=δ . Να αποδείξετε ότι οι αριθμοί Εικόνα για τους οποίους ισχύει δ=κα+λβ είναι πρώτοι μεταξύ τους.

7.

Έστω Εικόνα με (α,κ)=1. Να αποδείξετε ότι

Εικόνα
8.

Έστω Εικόνα. Να αποδείξετε ότι Εικόνα .