Θεώρημα 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 κάποιων πρώτων p₁, p₂, …., p_n.

(ιι) αν ο a γράφεται επίσης ως το γινόμενo πρώτων q₁, q₂, …., q_m, τότε n = m και κάθε p_i ισούται με κάποιο q_j.

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

Θεώρημα 3.6. (Ο Ευκλείδειος αλγόριθμος). Εστω a, b, q₁, q₂, …, q_n+1, r₁, r₂, …, r_n ακέραιοι με r_n > 0 και

a = q₁b + r₁

b = q₂r₁ + r₂

r₁ = q₃r₂ + r₃

………………

r_n-2 = q_nr_n-1 + r_n

r_n-1 = q_n+1r_n + 0.

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

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 ίσα μέρη, παίρνει το μερίδιό του και αποχωρεί, χωρίς να γίνει αντιληπτός από τους άλλους. Η ίδια διαδικασία επαναλαμβάνεται με τον τρίτο, τέταρτο και πέμπτο άνδρα.

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