3. Διαιρετότητα στο Ζ

 

Θεώρημα 3.1. (Αλγόριθμος διαίρεσης). Έστω a, b Z με b 0. Τότε υπάρχουν μοναδικά q, r Z τ.ω. a = qb + r και 0 r < .

 

Αν a = qb, όπου a, b, q είναι ακέραιοι, τότε λέμε ότι ο b διαιρεί τον a ή ότι ο a είναι πολλαπλάσιος του b, και γράφουμε b a.

 

Λήμμα 3.1. a b .

 

Λήμμα 3.2. " a, b, λ, μ Z, c a, c b c λa + μb.

 

Eστω a, b, d Z. Ο d λέγεται ο μέγιστος κοινός διαιρέτης των a, b (και γράφουμε μκδ(a, b) = d ) αν ισχύουν οι τρείς συνθήκες :

(1) d > 0

(2) d a και d b

(3) c a, c b c d.

 

Θεώρημα 3.2. Έστω a, b Z με a ή b 0. Τότε υπάρχει ο μκδ(a, b) και γράφεται στη μορφή λa + μb για κάποιους λ, μ Z .

 

Αν ο μκδ(a, b) = 1, οι a, b λέγονται σχετικά πρώτοι.

 

Θεώρημα 3.3. a, b είναι σχετικά πρωτοι ανν λa + μb = 1 για κάποιους λ, μ Z .

 

Ενας ακέραιος p > 1 λεγεται πρώτος αν οι μόνοι διαιρέτες του είναι οι 1, - 1, p και - p.

 

Λήμμα 3.3. Kάθε ακέραιος a > 1 διαιρείται από ένα τουλάχιστον πρώτο.

 

Θεώρημα 3.4. (Ευκλείδης). Υπάρχουν άπειροι το πλήθος πρώτοι.

 

Λήμμα 3.4. Ενας πρώτος p διαιρεί ένα ακέραιο a ή μκδ(a, p) = 1.

 

Λήμμα 3.5. μκδ(a, b) = 1, a bc a c.

 

Λήμμα 3.6. p πρώτος , p ab p a ή p b.

 

Λήμμα 3.7. Αν ένας πρώτος διαιρεί το γινόμενο ακεραίων, τότε διαιρεί ένα απ΄ αυτούς.

 

Λήμμα 3.8.Αν ένας πρώτος διαιρεί το γινόμενο πρώτων, τότε ισούται με ένα απ΄ αυτούς.

 

Θεώρημα 3.5. (Το Θεμελιώδες Θεώρημα της Αριθμητικής ή Θεώρημα Μοναδικής Παραγοντοποίησης για το Ζ). Εστω a ακέραιος 2. Toτε

(ι) ο a ισούται με το γινόμενo κάποιων πρώτων p1, p2, ., pn.

(ιι) αν ο a γράφεται επίσης ως το γινόμενo πρώτων q1, q2, ., qm, τότε n = m και κάθε pi ισούται με κάποιο qj.

 

Πόρισμα 3.1. Κάθε ακέραιος a 2 γράφεται με μονάδικό τρόπο ως γινόμενο δυνάμεων διακεκριμένων πρώτων.

 

Θεώρημα 3.6. (Ο Ευκλείδειος αλγόριθμος). Εστω a, b, q1, q2, , qn+1, r1, r2, , rn ακέραιοι με rn > 0 και

 

a = q1b + r1

b = q2r1 + r2

r1 = q3r2 + r3

rn-2 = qnrn-1 + rn

rn-1 = qn+1rn + 0.

Tότε rn = μκδ(a, b).

Aσκήσεις

 

3.1. Υπάρχει ο μκδ(0, 0) ;

Λύση

3.2. Ποιος είναι ο μκδ(0, a) για a 0 ;

Λύση

3.3. Οι λ και μ στο θεώρημα 3.2. είναι μοναδικοί ;

Λύση

3.4. Δείξτε ότι ο αριθμός είναι άρρητος.

Λύση

3.5. Δείξτε ότι αν η τετραγωνική ρίζα φυσικού αριθμού n είναι ρητός αριθμός, τότε ο n ισούται με το τετράγωνο ακεραίου.

Λύση

3.6. Δείξτε ότι ο αριθμός + είναι άρρητος.

Λύση

3.7. Βρείτε τον μκδ(a, b), όπου a = 15 και b = 365.

Λύση

3.8. Βρείτε τον μκδ(a, b), όπου a = 27 και b = 766.

Λύση

3.9. Βρείτε τον μκδ(a, b), όπου a = 365 και b = 25671.

Λύση

3.10. Βρείτε τον μκδ(a, b), όπου a = 31447 και b = 720685.

Λύση

3.11. Στις ασκήσεις 3.7, 3.8 και 3.9. να εκφράσετε τον μκδ(a, b) ως γραμμικό συνδυασμό των a, b.

Λύση

3.12. Στην άσκηση 3.10. να γράψετε το κλάσμα a / b σε ανάγωγο μορφή.

Λύση

3.13. Εστω ότι μκδ(a, b) = 1, a c και b c. Δείξτε ότι ab c.

Λύση

3.14. (Birkhoff and Mac Lane).

Σ ένα εξωτικό νησί, πέντε άνδρες και μια μαϊμού όλη μέρα μάζευαν καρύδες. To βράδυ ενώ κοιμούνταν, ξυπνάει ο πρώτος άνδρας και αποφασίζει να πάρει το μερίδιό του και να φύγει. Μοιράζοντας τις καρύδες σε 5 ίσα μέρη, βρίσκει ότι περισσεύει μια την οποία δίνει στη μαϊμού. Παίρνει το μερίδιό του και αποχωρεί, χωρίς να γίνει αντιληπτός από τους άλλους. Σε λίγο, ξυπνάει ο δεύτερος άνδρας, ο οποίος επίσης αποφασίζει να πάρει το μερίδιό του και να φύγει. Δίνει μια καρύδα στη μαϊμού, μοιράζει τις υπόλοιπες σε 5 ίσα μέρη, παίρνει το μερίδιό του και αποχωρεί, χωρίς να γίνει αντιληπτός από τους άλλους. Η ίδια διαδικασία επαναλαμβάνεται με τον τρίτο, τέταρτο και πέμπτο άνδρα.

Ποιος είναι ο ελάχιστος αριθμός καρύδων που είχαν μαζέψει;

Υπόδειξη

Λύση

Επιστροφή στα περιεχόμενα