Θεωρία Αριθμών

Μιχάλης Κολουντζάκης

Τμήμα Μαθηματικών και Εφαρμοσμένων Μαθηματικών,
Πανεπιστήμιο Κρήτης,
Βούτες, 70013 Ηράκλειο, E-mail: kolount AT gmail.com

Άνοιξη 2014-15

Περιεχόμενα

• 1 Ωράριο
• 2 Περιγραφή του μαθήματος
  • 2.1 Σημειώσεις μαθήματος
  
  
• 3 Βαθμολογικό Σύστημα - Εξετάσεις
• 4 Ημερολόγιο Μαθήματος
  • 4.1 Τε, 18/2/2015, και Τε, 25/2/2015
  • 4.2 Δε, 2/3/2015
  • 4.3 Τε, 4/3/2015
  • 4.4 Δε, 9/3/2015
  • 4.5 Τε, 11/3/2015
  • 4.6 Δε, 16/3/2015
  • 4.7 Τε, 18/3/2015
  • 4.8 Δε, 23/3/2015
  • 4.9 Δε, 30/3/2015
  • 4.10 Τε, 1/4/2015
    • 4.10.1 Δε, 6/4/2015: Φυλλάδιο ασκήσεων
  • 4.11 Δε, 21/4/2015
  • 4.12 Τε, 23/4/2015
  • 4.13 Δε, 28/4/2015
  • 4.14 Τε, 30/4/2015
  • 4.15 Δε, 4/5/2015
  • 4.16 Τε, 8/5/2015
  • 4.17 Δε, 11/5/2015
  • 4.18 Τε, 13/5/2015
  • 4.19 Δε, 18/5/2015
    • 4.19.1 ΑΝΑΚΟΙΝΩΣΗ: Συνέχεια μαθήματος
  • 4.20 Τε, 20/5/2015
  • 4.21 Δε, 25/5/2015
  • 4.22 Τε, 27/5/2015
  • 4.23 Τελικό διαγώνισμα και τελικοί βαθμοί
    • 4.23.1 ΑΝΑΚΟΙΝΩΣΗ: Γραπτά
    • 4.23.2 Διαγώνισμα και βαθμοί Σεπτεμβρίου.
    • 4.23.3 ΑΝΑΚΟΙΝΩΣΗ: Γραπτά
    • 4.23.4 ΑΝΑΚΟΙΝΩΣΗ: Ειδική Εξεταστική, Ιανουάριος 2016

1 Ωράριο

Δευτέρα 11-1, Τετάρτη 11-1 στην αίθουσα Ε204.

Ώρες γραφείου: Τρίτη 11-1 (στο εργαστήριο υπολογιστών Γ109).

2 Περιγραφή του μαθήματος

2.1 Σημειώσεις μαθήματος

Μπορείτε να συμβουλεύεστε τις παρακάτω σημειώσεις:

1. Μιχ. Παπαδημητράκη
2. Νικ. Τζανάκη

Δεν ακολουθώ πιστά κάποιο από τα παραπάνω συγγράματα αλλά εκεί μέσα θα βρείτε ό,τι χρειάζεστε για το μάθημα (αρκεί φυσικά να ξέρετε τι ψάχνετε).

3 Βαθμολογικό Σύστημα - Εξετάσεις

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

4 Ημερολόγιο Μαθήματος

4.1 Τε, 18/2/2015, και Τε, 25/2/2015

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

Είδαμε τι είναι πρώτος αριθμός (φυσικός αριθμός, $\ge 2$, που δεν έχει άλλους διαιρέτες εκτός τον εαυτό του και τη μονάδα) και αποδείξαμε το θεμελιώδες θεώρημα της αριθμητικής, ότι δηλ. κάθε φυσικός αριθμός γράφεται με μοναδικό τρόπο (εκτός από τη σειρά των παραγόντων) ως γινόμενο πρώτων αριθμών.

Για τις πρώτες δύο διαλέξεις στηρίχτηκα και στις σημειώσεις εδώ.

4.2 Δε, 2/3/2015

Ορίσαμε το ελάχιστο κοινό πολλαπλάσιο $[a,b]$ δύο αριθμών $a, b$ και είπαμε πώς ορίζεται ο μέγιστος κοινός διαιρέτης και το ελάχιστο κοινό πολλαπλάσιο παραπάνω από δύο αριθμών.

Έπειτα είδαμε τον τύπο

$$[a,b](a,b) = a\cdot b$$ (1)

που ισχύει για οποιουσδήποτε φυσικούς αριθμούς $a, b$, και παρατηρήσαμε ότι δεν ισχύει για παραπάνω από δύο αριθμούς. Είδαμε αρκετά παραδείγματα το πώς αποδεικνύεται αυτός ο τύπος αφού πρώτα είδαμε το πώς μπορεί κανείς να γράψει τον ΜΚΔ και το ΕΚΠ δύο αριθμών τους οποίους πρώτα έχει αναλύσει σε γινόμενο πρώτων. Θυμηθήκαμε την αρχή εγκλεισμού-αποκλεισμού (principle of inclusion-exclusion) και τη χρησιμοποιήσαμε για να δείξουμε τον παραπάνω τύπο (1). Επίσης χρησιμοποιήσαμε την αρχή εγκλεισμού-αποκλεισμού για να βρούμε ένα τύπο που συνδέει το $(a, b, c)$ με το $[a, b, c]$.

Αναφερθήκαμε μετά στο λεγόμενο πρόβλημα των Sylverster και Frobenius (δείτε εδώ). Δείξαμε ότι αν $a_1, a_2, \ldots, a_k$ είναι φυσικοί αριθμοί με ΜΚΔ ίσο με 1 τότε υπάρχει ένας φυσικός αριθμός $n_0$ ώστε για κάθε $n\ge n_0$ να μπορούμε να γράψουμε το $n$ ως

$$n = r_1 a_1 + r_2 a_2 + \cdots + r_k a_k,$$

όπου $r_1, r_2, \ldots, r_k \in {\left\{{0, 1, 2, \ldots}\right\}}$.

4.3 Τε, 4/3/2015

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

Συγκεκριμένα λύσαμε τις ασκήσεις 1, 3, 4, 7 (και παραλλαγές τους) από τη σελ. 8 στις σημειώσεις Παπαδημητράκη και τις ασκήσεις 8 και 13 από τη σελ. 16.

Επίσης την: Αν διαλέξουμε πάνω από $n$ από τους αριθμούς $1, 2, \ldots, 2n$ τότε αναγκαστικά δύο από αυτούς που διαλέξαμε είναι μεταξύ τους πρώτοι.

Δείξαμε επίσης στην αρχή ότι ο αριθμός $\sqrt{2}$ είναι άρρητος και επίσης ότι αν η τετραγωνική ρίζα ενός ακεραίου δεν είναι ακέραια (ο αριθμός δηλ. δεν είναι τέλειο τετράγωνο) τότε είναι άρρητος αριθμός.

4.4 Δε, 9/3/2015

Σήμερα μιλήσαμε για ισοτιμίες, το συμβολισμό δηλ. $a \equiv b \bmod m$ ή $a \equiv b (m)$. Είδαμε ότι για σταθερό $m$ η σχέση $x \equiv y (m)$ είναι μια σχέση ισοδυναμίας πάνω στο ${\mathbb{Z}}$. Είδαμε επίσης ότι οι ισοτιμίες μπορούν να προστίθενται και να πολλαπλασιονται κατά μέρη (για το ίδιο $m$) και είδαμε πώς αυτό μπορεί να μας διευκολύνει πάρα πολύ σε διάφορους υπολογισμούς.

Ορίσαμε τι σημαίνει πολλαπλασιαστικό αντίστροφο $\bmod m$ και είδαμε ότι το $a$ έχει πολλαπλασιαστικό αντίστροφο $\bmod m$ αν και μόνο αν $(a, m)=1$.

Είδαμε το πώς βρίσκεται (χρησιμοποιώντας τον αλγόριθμο του Ευκλείδη) το πολλαπλασιαστικό αντίστροφο $\bmod m$ όταν αυτό υπάρχει.

Ορίσαμε τη συνάρτηση $\phi$ του Euler και είδαμε πώς να την υπολογίζουμε αν το $n$ είναι δύναμη πρώτου. Αναφέραμε το ότι η $\phi$ είναι πολλαπλασιαστική συνάρτηση:

$$(a,b) = 1 \Longrightarrow \phi(ab) = \phi(a) \phi(b)$$

και είδαμε πώς μπορούμε να το χρησιμοποιήσουμε αυτό για να υπολογίσουμε το $\phi$ οποιουδήποτε ακεραίου αρκεί να ξέρουμε το ποιοι πρώτοι τον διαιρούν. Την πολλαπλασιαστική ιδιότητα θα την αποδείξουμε την επόμενη φορά.

4.5 Τε, 11/3/2015

Αποδείξαμε σήμερα κατ αρχήν την πολαλπλασιαστικότητα της συνάρτησης $\varphi$ του Euler.

Έπειτα ασχοληθήκαμε με διάφορα κριτήρια διαιρετότητας και είδαμε το πώς χρησιμοποιούμε την αριθμητική υπολοίπων (modular arithmetic) για να τα εξηγήσουμε. Μπορείτε να διαβάσετε σχετικά εδώ.

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

4.6 Δε, 16/3/2015

Σήμερα μιλήσαμε για τη γραμμική διοφαντική εξίσωση

$$Ax+By = C,$$

και είδαμε ότι αυτή

1. Δεν έχει λύσεις αν $(A, B) \nmid C$,
2. Αν $(A,B) \mid C$ τότε έχει άπειρες λύσεις. Σε αυτή την περίπτωση είδαμε ακριβώς ποιες είναι αυτές.

Συνεχίσαμε με τη διοφαντική εξίσωση $x^2+y^2 = z^2$, οι λύσεις $(x, y, z)$ της οποίας ονομάζονται Πυθαγόρειες τριάδες (γιατί είναι ακριβώς τα μήκη των πλευρών ορθογωνίων τριγώνων που τυγχάνει να είναι και ακέραιοι.)

Βρήκαμε όλες τις λύσεις της εξίσωσης αυτής σε παραμετρική μορφή.

4.7 Τε, 18/3/2015

Σήμερα μιλήσαμε για τη μέθοδο της καθόδου (method of descent) με την οποία δείχνουμε ότι κάποια διοφαντική εξίσωση δεν έχει λύση (ή έχει μόνο τετριμμένες λύσεις) υποθέτοντας πρώτα ότι έχει κάποια λύση και δείχνοντας από αυτό ότι έχει κι άλλη λύση η οποία είναι ``μικρότερη'' υπό μία έννοια. Επαναλαμβάνοντας αυτό το βήμα καταλήγουμε τελικά σε άτοπο.

Είδαμε διάφορα παραδείγματα χρήσης της μεθόδου αυτής και τέλος το εφαρμόσαμε στο να δείξουμε ότι η εξίσωση $x^4+y^4=z^2$ δεν έχει μη τετριμμένες λύσεις (λύσεις δηλ. όπου καμιά μεταβλητή δεν είναι 0).

4.8 Δε, 23/3/2015

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

4.9 Δε, 30/3/2015

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

4.10 Τε, 1/4/2015

Λύσαμε διάφορες ασκήσεις σχετικές με συνέλιξη και πολλαπλασιαστικές συναρτήσεις.

4.10.1 Δε, 6/4/2015: Φυλλάδιο ασκήσεων

Μπορείτε να κατεβάσετε το φυλλάδιο ασκήσεων από εδώ.

Η λύση αυτών των ασκήσεων αποτελεί κεντρικό κομμάτι της προετοιμασίας σας (προσοχή: η λύση, όχι η αποστήθιση μιας λύσης που θα διαβάσετε από κάπου).

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

4.11 Δε, 21/4/2015

Σήμερα αρχίσαμε να κοιτάμε τις ασκήσεις του φυλλαδίου (κάναμε τις 10 πρώτες).

4.12 Τε, 23/4/2015

Σήμερα συνεχίσαμε να κοιτάμε τις ασκήσεις του φυλλαδίου (κάναμε μέχρι και την Άσκ. 17).

4.13 Δε, 28/4/2015

Σήμερα συνεχίσαμε να κοιτάμε τις ασκήσεις του φυλλαδίου.

4.14 Τε, 30/4/2015

Σήμερα συνεχίσαμε να κοιτάμε τις ασκήσεις του φυλλαδίου.

4.15 Δε, 4/5/2015

Σήμερα συνεχίσαμε να κοιτάμε τις ασκήσεις του φυλλαδίου. Έχουμε λύσει μέχρι και την άσκηση 41.

4.16 Τε, 8/5/2015

Σήμερα συνεχίσαμε να κοιτάμε τις ασκήσεις του φυλλαδίου. Έχουμε λύσει μέχρι και την άσκηση 47.

4.17 Δε, 11/5/2015

Σήμερα συνεχίσαμε να κοιτάμε τις ασκήσεις του φυλλαδίου. Έχουμε λύσει μέχρι και την άσκηση 55. Δε λύσαμε την άσκηση 48 γιατί κανείς φοιτητής δεν είχε ασχοληθεί μαζί της.

4.18 Τε, 13/5/2015

Δεν έγινε μάθημα λόγω φοιτητικών εκλογών.

4.19 Δε, 18/5/2015

Συνεχίσαμε τις ασκήσεις του φυλλαδίου. Λύσαμε μέχρι και την άσκηση 65. Η άσκηση 48 εξακολουθεί να παραμένει άλυτη.

4.19.1 ΑΝΑΚΟΙΝΩΣΗ: Συνέχεια μαθήματος

Το μάθημα θα συνεχιστεί και την επόμενη εβδομάδα τις ίδιες ώρες (επειδή δεν άρχισε από την αρχή του εξαμήνου).

4.20 Τε, 20/5/2015

Συνεχίσαμε τις ασκήσεις του φυλλαδίου.

4.21 Δε, 25/5/2015

Συνεχίσαμε τις ασκήσεις του φυλλαδίου.

4.22 Τε, 27/5/2015

Συνεχίσαμε τις ασκήσεις του φυλλαδίου. Έμειναν μόνο 2-3 ασκήσεις από το φυλλάδιο τις οποίες δεν προλάβαμε να λύσουμε.

4.23 Τελικό διαγώνισμα και τελικοί βαθμοί

Το τελικό διαγώνισμα είναι εδώ και οι τελικοί βαθμοί εδώ.

4.23.1 ΑΝΑΚΟΙΝΩΣΗ: Γραπτά

Όσοι θέλουν να δουν το γραπτό τους μπορούν να έρθουν στο γραφείο Γ213 την Παρασκευή 3 Ιουλίου και ώρα 12:00.

4.23.2 Διαγώνισμα και βαθμοί Σεπτεμβρίου.

Το διαγώνισμα είναι εδώ μαζί με τις λύσεις και οι τελικοί βαθμοί είναι εδώ (υπάρχουν δύο που θα πέρναγαν το μάθημα αλλά δεν είναι εγγεγραμμένοι).

4.23.3 ΑΝΑΚΟΙΝΩΣΗ: Γραπτά

Μπορείτε να δείτε τα γραπτά σας την Παρασκευή 2/10/2015, 9-10 το πρωί.

4.23.4 ΑΝΑΚΟΙΝΩΣΗ: Ειδική Εξεταστική, Ιανουάριος 2016

Οι βαθμοί είναι εδώ.