Θεωρία Αριθμών — Πρώτοι, Διαιρετότητα & Αριθμητική Modulo

Η θεωρία αριθμών είναι η μελέτη των ακεραίων αριθμών. Αν θέλεις να καταλάβεις τους πρώτους αριθμούς, τη διαιρετότητα ή την αριθμητική modulo, τότε ήδη εξετάζεις τον πυρήνα της θεωρίας αριθμών.

Ένας πρώτος αριθμός είναι ένας ακέραιος μεγαλύτερος από το $1$ με ακριβώς δύο θετικούς διαιρέτες: το $1$ και τον εαυτό του. Η διαιρετότητα εξετάζει αν ένας ακέραιος διαιρεί έναν άλλον χωρίς υπόλοιπο. Η αριθμητική modulo παρακολουθεί τα υπόλοιπα, γι’ αυτό συχνά λέγεται και αριθμητική του ρολογιού.

Τι Καλύπτει η Θεωρία Αριθμών

Αυτές οι τρεις ιδέες συνδέονται μεταξύ τους:

• Οι πρώτοι είναι τα βασικά δομικά στοιχεία των θετικών ακεραίων.
• Η διαιρετότητα σου λέει πότε ένας ακέραιος χωρά ακριβώς μέσα σε έναν άλλον.
• Η αριθμητική modulo μετατρέπει ερωτήματα διαιρετότητας σε ερωτήματα υπολοίπων.

Για παράδειγμα, το να πούμε ότι «το $a$ διαιρείται με το $n$» είναι το ίδιο με το να πούμε

$$a \equiv 0 \pmod n$$

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

Πρώτοι Αριθμοί: Τα Δομικά Στοιχεία

Οι πρώτοι αριθμοί αρχίζουν ως εξής:

$$2, 3, 5, 7, 11, 13, \dots$$

Ο αριθμός $2$ είναι ο μόνος άρτιος πρώτος. Κάθε άλλος άρτιος αριθμός διαιρείται με το $2$, άρα δεν μπορεί να είναι πρώτος.

Αν ένας θετικός ακέραιος μεγαλύτερος από το $1$ δεν είναι πρώτος, λέγεται σύνθετος. Για παράδειγμα, το $21$ είναι σύνθετος επειδή

$$21 = 3 \cdot 7$$

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

Διαιρετότητα: Πότε Ένας Αριθμός Χωρά Ακριβώς σε Έναν Άλλον

Αν τα $a$ και $b$ είναι ακέραιοι με $b \ne 0$, τότε το «το $b$ διαιρεί το $a$» σημαίνει ότι υπάρχει ένας ακέραιος $k$ τέτοιος ώστε

$$a = bk$$

Αυτό γράφεται ως

$$b \mid a$$

Για παράδειγμα, $4 \mid 20$ επειδή $20 = 4 \cdot 5$. Όμως $4 \nmid 22$ επειδή η διαίρεση του $22$ με το $4$ αφήνει υπόλοιπο.

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

• Ένας αριθμός διαιρείται με το $2$ αν το τελευταίο του ψηφίο είναι άρτιο.
• Ένας αριθμός διαιρείται με το $5$ αν το τελευταίο του ψηφίο είναι $0$ ή $5$.
• Ένας αριθμός διαιρείται με το $3$ αν το άθροισμα των ψηφίων του διαιρείται με το $3$.

Αυτός ο τελευταίος κανόνας δεν είναι κόλπο. Προκύπτει από την αριθμητική modulo.

Αριθμητική Modulo: Υπολογισμοί με Υπόλοιπα

Όταν δύο ακέραιοι αφήνουν το ίδιο υπόλοιπο όταν διαιρούνται με το $n$, λέμε ότι είναι ισοδύναμοι modulo $n$. Γράφουμε

$$a \equiv b \pmod n$$

Αυτό σημαίνει ότι το $n$ διαιρεί το $a-b$.

Για παράδειγμα,

$$17 \equiv 5 \pmod{12}$$

επειδή το $17$ και το $5$ αφήνουν και τα δύο υπόλοιπο $5$ όταν διαιρούνται με το $12$, και επίσης επειδή το $12$ διαιρεί το $17 - 5 = 12$.

Αυτό είναι χρήσιμο επειδή μπορείς να αντικαταστήσεις έναν αριθμό με έναν απλούστερο ισοδύναμο. Σε ένα ρολόι $12$ ωρών, η πρόσθεση $15$ ωρών έχει το ίδιο αποτέλεσμα με την πρόσθεση $3$ ωρών επειδή

$$15 \equiv 3 \pmod{12}$$

Λυμένο Παράδειγμα: Γιατί το $231$ Διαιρείται με το $3$;

Πάρε τον αριθμό $231$.

Πρώτα, γράψ’ τον σε αναπτυγμένη μορφή θέσης:

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

Τώρα δούλεψε modulo $3$. Αφού

$$10 \equiv 1 \pmod 3$$

έπεται ότι

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

Άρα

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

Επειδή $231 \equiv 0 \pmod 3$, ο αριθμός διαιρείται με το $3$.

Αυτό εξηγεί τον κανόνα του αθροίσματος ψηφίων: στη βάση $10$, κάθε δύναμη του $10$ είναι ισοδύναμη με το $1$ modulo $3$, άρα ολόκληρος ο αριθμός έχει το ίδιο υπόλοιπο με το άθροισμα των ψηφίων του.

Και μόλις κάνεις τη διαίρεση,

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

οπότε το $231$ είναι σύνθετος και όχι πρώτος.

Συνηθισμένα Λάθη στη Θεωρία Αριθμών

Να Θεωρείς το $1$ Πρώτο

Το $1$ δεν είναι πρώτος. Ένας πρώτος πρέπει να έχει ακριβώς δύο θετικούς διαιρέτες, και το $1$ έχει μόνο έναν.

Να Ξεχνάς τη Συνθήκη στη Διαιρετότητα

Η πρόταση $b \mid a$ έχει νόημα μόνο όταν $b \ne 0$. Η διαίρεση με το μηδέν δεν επιτρέπεται.

Να Μπερδεύεις την Ισότητα με την Ισοδυναμία

Το $17 \equiv 5 \pmod{12}$ δεν σημαίνει ότι $17 = 5$. Σημαίνει ότι διαφέρουν κατά ένα πολλαπλάσιο του $12$.

Υπερβολική Χρήση Κριτηρίων Διαιρετότητας

Μερικά κριτήρια είναι γρήγορα επειδή η αριθμητική στη βάση $10$ τα κάνει να λειτουργούν όμορφα. Αυτό δεν σημαίνει ότι κάθε διαιρέτης έχει έναν απλό κανόνα ψηφίων.

Πού Εμφανίζεται η Θεωρία Αριθμών

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

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

Δοκίμασε τη Δική σου Εκδοχή

Δοκίμασε την ίδια λογική με το $462$. Πρώτα χρησιμοποίησε το άθροισμα των ψηφίων του για να ελέγξεις αν διαιρείται με το $3$, και μετά παραγοντοποίησέ το όσο χρειάζεται για να αποφασίσεις αν είναι πρώτος ή σύνθετος.

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