Πώς μπορούμε να ελέγξουμε αν ένας αριθμός είναι πρώτος;

 

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

 

Image credit: Michael Jay Berlin via Shutterstock

Πολλές φορές, χρειάζεται να ελέγξουμε αν ένας αριθμός n είναι πρώτος. Μια βασική διαδικασία είναι η δοκιμαστική διαίρεση, δηλαδή να ελέγξουμε αν ο αριθμός n είναι πολλαπλάσιο κάποιου αριθμού από το 2 έως και το \(\sqrt{n}\). Απαραίτητα εδώ είναι τα κριτήρια διαιρετότητας.

 

Παραδείγματα:

✅Θέλουμε να εξετάσουμε αν ο αριθμός 169 είναι πρώτος. Αρκεί να ελέγξουμε αν το 169 είναι πολλαπλάσιο κάποιου αριθμού από το 2 έως και το \(\sqrt{169}=13\).

Το 2 δεν διαιρεί το 169.

Το 3 δεν διαιρεί το 169.

Ομοίως, το 4, το 5, το 6, το 7, το 8, το 9, το 10, το 11 και το 12 δεν διαιρούν το 169.

Το 13 διαιρεί το 169.

Άρα το 169 δεν είναι πρώτος αριθμός.

 

✅Θέλουμε να εξετάσουμε αν ο αριθμός 51 είναι πρώτος. Επειδή 49<51 δηλαδή \(7<\sqrt{51}\),  αρκεί να ελέγξουμε αν το 51 είναι πολλαπλάσιο κάποιου αριθμού από το 2  έως και το 7.

Το 2 δεν διαιρεί το 51.

Το 3 διαιρεί το 51.

Άρα το 51 δεν είναι πρώτος αριθμός.

 

✅Θέλουμε να εξετάσουμε αν ο αριθμός 113 είναι πρώτος. Επειδή 100<113 δηλαδή \(10<\sqrt{113}\),  αρκεί να ελέγξουμε αν το 113 είναι πολλαπλάσιο κάποιου αριθμού από το 2 έως και το 10.

Βρίσκουμε ότι κανένας από τους αριθμούς 2, 3, 4, 5, 6, 7, 8, 9, 10 δεν διαιρεί το 113.

Άρα το 113 είναι πρώτος αριθμός.

 

💡Η μέθοδος της δοκιμαστικής διαίρεσης μπορεί να εφαρμοστεί πιο αποτελεσματικά αν είναι γνωστοί όλοι οι πρώτοι αριθμοί μέχρι και το \(\sqrt{n}\). Για παράδειγμα, για να ελέγξουμε αν ο 113 είναι πρώτος, αρκεί να ελέγξουμε αν διαιρείται μόνο από το 2, το 3, το 5 και το 7.

 

🚩Για πολύ μεγάλους αριθμούς, η μέθοδος αυτή γίνεται πολύ αργή και μη πρακτική, γιατί το πλήθος των πιθανών παραγόντων του n αυξάνεται ραγδαία καθώς αυξάνεται ο n. Για την ακρίβεια, το πλήθος των πρώτων αριθμών μικρότερων του \(\sqrt{n}\) είναι της τάξης \(\frac{\sqrt{n}}{ln(\sqrt{n})}\).  Για τον έλεγχο πολύ μεγάλων αριθμών, έχουν αναπτυχθεί διάφοροι αλγόριθμοι που τρέχουν σε υπολογιστικά συστήματα.

🔍Διάβασε εδώ περισσότερα γύρω από τους πρώτους αριθμούς.

Τριγωνικοί, τετραγωνικοί και εξαγωνικοί αριθμοί!

 

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

  

Τριγωνικός λέγεται κάθε αριθμός, ο οποίος, αν συμβολιστεί με σημεία –τόσα σημεία όσα υποδηλώνει ο αριθμός– σχηματίζεται τρίγωνο. Για να βρούμε τους τριγωνικούς αριθμούς, αρχίζουμε από το 1. Κάθε φορά προσθέτουμε και τον επόμενο φυσικό αριθμό. Δηλαδή:

1

1+2=3

1+2+3=6

1+2+3+4=10

1+2+3+4+5=15

1+2+3+4+5+6=21

…

Το άθροισμα που προκύπτει κάθε φορά (σημειωμένο με έντονο) είναι και ένας τριγωνικός αριθμός.

 

Μπορούμε να αναπαραστήσουμε τους τριγωνικούς αριθμούς με ισόπλευρα τρίγωνα, όπως φαίνεται στο παρακάτω σχήμα:

 

Ο n-οστός τριγωνικός αριθμός είναι το άθροισμα των n πρώτων θετικών ακεραίων. Συμβολίζεται με \(T_n\) και ισούται με

\(T_n=1+2+…+n=\frac{n(n+1)}{2}\)

π.χ. \(T_4=\frac{4 \cdot 5)}{2}=10\)

 

Για την ακολουθία των τριγωνικών αριθμών ισχύει και ο αναδρομικός τύπος:

\(T_1=1\)

\(T_n=T_{n-1}+n, n>1\)

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

Ένας τετραγωνικός αριθμός \(n\) αντιπροσωπεύεται από \(n\) σημεία (κουκκίδες), τα οποία σχηματίζουν τετράγωνο, με την κάθε πλευρά του να έχει \(\sqrt{n}\) σημεία.

Ο αριθμός \(n\) είναι τετραγωνικός, αν και μόνο αν μπορούμε να συνθέσουμε ένα τετράγωνο από \(n\) ίσα μεταξύ τους τετράγωνα.

π.χ. 

\(n=1=1^2\)

\(n=4=2^2\)

\(n=9=3^2\)

\(n=16=4^2\)

\(n=25=5^2\)

Οι πρώτοι τετραγωνικοί αριθμοί (τέλεια τετράγωνα) είναι:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...

 

Για έναν θετικό ακέραιο \(n\), ο n-οστός τετραγωνικός αριθμός είναι ο \(n^2\).

Κάποιοι τύποι που χρησιμεύουν για τον υπολογισμό ενός τετραγωνικού αριθμού όταν είναι γνωστός ο προηγούμενός του (αναδρομικοί τύποι), είναι:

\(n^2=(n-1)^2+(n-1)+n=(n-1)^2+(2n-1)\)

Το άθροισμα δύο διαδοχικών τριγωνικών αριθμών είναι τετραγωνικός αριθμός.

π.χ. \(T_3+T_4=6+10=16\), που είναι τετραγωνικός αριθμός.

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

 

Ο n-οστός εξαγωνικός αριθμός \(h_n\) είναι το πλήθος των κουκκίδων που «δημιουργούν» το εξαγωνικό σχήμα του. Στο μοτίβο αυτό, τα εξάγωνα δεν περιέχονται το ένα στο εσωτερικό του άλλου, αλλά έχουν όλα μία κοινή «κορυφή».

 

Οι πρώτοι εξαγωνικοί αριθμοί είναι:

1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, 276, 325, …

Ο τύπος που δίνει τον n-οστό εξαγωνικό αριθμό είναι:

\(h_n=2n^2-n=n(2n-1)=\frac{2n(2n-1)}{2} \)

 

Κάθε εξαγωνικός αριθμός είναι και τριγωνικός αριθμός.

Κάθε τριγωνικός αριθμός με περιττό πλήθος «πλευρών» (δηλαδή ο \(T_n\) με n περιττό) είναι εξαγωνικός αριθμός.

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

Για να ελέγξουμε αν ένας θετικός ακέραιος \(x\) είναι εξαγωνικός, μπορούμε να υπολογίσουμε τον αριθμό

\(n=\frac{\sqrt{8x+1}+1}{4}\).

Αν ο \(n\) είναι ακέραιος, τότε ο \(x\) είναι ο n-οστός εξαγωνικός αριθμός. Αλλιώς ο \(x\) δεν είναι εξαγωνικός.

👉Ανακαλύψτε περισσότερα στην "Online Εγκυκλοπαίδεια Ακολουθιών Ακέραιων Αριθμών" (OEIS).

Τα σύνολα των αριθμών

Σχηματική αναπαράσταση των συνόλων των αριθμών...

Πρώτοι αριθμοί: Από τα Μαθηματικά του Δημοτικού, στη σύγχρονη έρευνα

 

Οι πρώτοι αριθμοί είναι αυτοί που έχουν ακριβώς δύο διαιρέτες: τον εαυτό τους και το 1. Οι αρχικοί αριθμοί που είναι πρώτοι είναι οι: 2, 3, 5, 7, 11, 13.

Ο πρώτοι... πρώτοι αριθμοί

Τα δομικά στοιχεία των φυσικών αριθμών

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

Παραδείγματα:

\(15 = 3 \cdot 5\)

\(210 = 2 \cdot 3 \cdot 5 \cdot 7\)

\(396 = 2^2 \cdot 3^2 \cdot 11\)

 

✅Η παραπάνω γραφή ονομάζεται ανάλυση αριθμού σε γινόμενο πρώτων παραγόντων ή πρωτογενής ανάλυση του αριθμού. Επίσης λέμε ότι ο αριθμός είναι γραμμένος σε κανονική μορφή.

 

Πώς γίνεται η ανάλυση ενός αριθμού σε γινόμενο πρώτων παραγόντων;

Παράδειγμα: Θέλουμε να αναλύσουμε το 360 σε γινόμενο πρώτων παραγόντων. Θα χρησιμοποιήσουμε τη μέθοδο των διαδοχικών διαιρέσεων.

👣 Βήμα  1. Εξετάζουμε, σύμφωνα με τα κριτήρια διαιρετότητας, ποιος είναι ο μικρότερος πρώτος αριθμός που διαιρεί το 360. Βρίσκουμε ότι είναι το 2 και το γράφουμε στα δεξιά.

👣 Βήμα 2. Διαιρούμε το 360 με το 2 και γράφουμε από κάτω το πηλίκο, που είναι το 180.

👣 Βήμα 3. Συνεχίζουμε την ίδια διαδικασία για το 180. Το 180 διαιρείται κι αυτό με το 2. Διαιρούμε με το 2 και γράφουμε από κάτω το πηλίκο, που είναι το 90.

👣 Βήμα 4. Διαιρούμε το 90 με το 2 και γράφουμε από κάτω το πηλίκο, που είναι το 45.

👣 Βήμα 5. Το 45 τώρα δεν διαιρείται με το 2. Πηγαίνουμε στον επόμενο πρώτο αριθμό, που είναι το 3. Βρίσκουμε ότι το 45 διαιρείται με 3.

👣 Βήμα 6. Διαιρούμε το 45 με το 3 και γράφουμε από κάτω το πηλίκο, που είναι το 15.

👣 Βήμα 7. Το 15 διαιρείται με το 3. Διαιρούμε το 15 με το 3 και γράφουμε από κάτω το πηλίκο, που είναι το 5.

👣 Βήμα 8. Το 5 τώρα δεν διαιρείται με το 3. Πηγαίνουμε στον επόμενο πρώτο αριθμό, που είναι το 5.

👣 Βήμα 9. Το 5 προφανώς διαιρείται με το 5. Γράφουμε από κάτω το πηλίκο, που είναι το 1.

👣 Βήμα 10. Μόλις βρούμε πηλίκο το 1, η διαδικασία τελειώνει!

👣 Τελευταίο βήμα: Γράφουμε τον αριθμό 360 ως το γινόμενο των πρώτων αριθμών που έχουμε γράψει στην τελευταία στήλη:

360 = 2 · 2 · 2 · 3 · 3 · 5 = 2^3 · 3^2 · 5 

 

 👉Περισσότερα παραδείγματα μπορείτε να παρακολουθήσετε σε αυτό το βίντεο.

 

Εφαρμογές των πρώτων αριθμών στην Κρυπτογραφία

Κρυπτογραφία είναι η επιστήμη που ασχολείται με την κωδικοποίηση και αποκωδικοποίηση μυστικών μηνυμάτων. Στη σημερινή ψηφιακή εποχή, η ασφαλής επικοινωνία είναι ζωτικής σημασίας. Είτε στέλνουμε ένα e-mail, είτε πραγματοποιούμε μια ηλεκτρονική αγορά, η κρυπτογραφία διασφαλίζει ότι οι πληροφορίες μας παραμένουν εμπιστευτικές. Στον κόσμο της σύγχρονης κρυπτογραφίας, οι πρώτοι αριθμοί είναι οι «αφανείς ήρωες». Η κρυπτογράφηση και αποκρυπτογράφηση βασίζονται στη Θεωρία Αριθμών και ειδικότερα στους πρώτους αριθμούς και στο Θεμελιώδες Θεώρημα της Αριθμητικής.

Οι επιστήμονες του χώρου χρησιμοποιούν κατά κόρον φυσικούς αριθμούς που είναι γινόμενο τεράστιων πρώτων αριθμών. Ας πάρουμε για παράδειγμα τον αλγόριθμο RSA, ο οποίος χρησιμοποιεί δύο μεγάλους πρώτους αριθμούς p και q. Αφού τους πολλαπλασιάσει, χρησιμοποιεί το γινόμενό τους n = p · q ως μέρος των κλειδιών κρυπτογράφησης και αποκρυπτογράφησης. Ο αριθμός n είναι δημόσιος και ονομάζεται «δημόσιο κλειδί», είναι δηλαδή, όχι μόνο γνωστός, αλλά και δημοσιευμένος σε κάποιο βιβλίο ανάλογο του τηλεφωνικού καταλόγου. Για να μπορέσει κανείς να «χακάρει» ένα σύστημα, θα πρέπει να έχει βρει την πρωτογενή ανάλυση του n, δηλαδή θα πρέπει να υπολογίσει τους πρώτους αριθμούς p και q από τους οποίους «αποτελείται». Στην πράξη, αυτοί οι πρώτοι αριθμοί έχουν τόσο πολλά ψηφία που, ακόμη και με χρήση υπολογιστικών συστημάτων τελευταίας τεχνολογίας που δουλεύουν νυχθημερόν, χρειάζονται δεκάδες χρόνια προκειμένου να υπολογιστούν!

❓Άραγε, η ανάπτυξη υπερσύγχρονης τεχνολογίας θα «προλάβει» τις εξελίξεις στην έρευνα της Θεωρίας Αριθμών;

Πρώτοι και σύνθετοι αριθμοί: Το κόσκινο του Ερατοσθένη και μια απόδειξη του Ευκλείδη

 

Πρώτος καλείται ένας φυσικός αριθμός που διαιρείται μόνο με το 1 και τον εαυτό του. Για παράδειγμα οι αριθμοί 2, 3, 11, 17 είναι πρώτοι. Ένας αριθμός που δεν είναι πρώτος καλείται σύνθετος. Για παράδειγμα, ο αριθμός 9 είναι σύνθετος, αφού εκτός της μονάδας και του εαυτού του έχει διαιρέτη και το 3.

Επειδή το 1 έχει μόνο έναν διαιρέτη (το 1, που είναι και ο εαυτός του), δεν είναι ούτε πρώτος ούτε σύνθετος αριθμός. Το 2 είναι ο μοναδικός άρτιος πρώτος, ενώ όλοι οι υπόλοιποι πρώτοι αριθμοί είναι περιττοί.

Μπορούμε να βρούμε όλους τους πρώτους αριθμούς με ένα «κόσκινο»: Το κόσκινο του Ερατοσθένη κρατάει όλους τους σύνθετους αριθμούς και αφήνει να περάσουν όλοι οι πρώτοι.

Το κόσκινο του Ερατοσθένη: Από το βιβλίο Μαθηματικών της Α΄ Γυμνασίου, εκδόσεις Διόφαντος, 2023

Για να βρούμε τους πρώτους αριθμούς, εργαζόμαστε ως εξής:

1. Αφήνουμε απέξω το 1 (είπαμε: δεν είναι ούτε πρώτος, ούτε σύνθετος).

2. Παίρνουμε τον επόμενο αριθμό (το 2). Τον κρατάμε και σβήνουμε όλα τα πολλαπλάσιά του.

3. Παίρνουμε τον επόμενο άσβηστο αριθμό (το 3).
Τον κρατάμε και σβήνουμε όλα τα πολλαπλάσιά του (όσα δεν έχουν σβηστεί από πριν, ως πολλαπλάσια του 2).

​4. Παίρνουμε τον επόμενο άσβηστο αριθμό (το 5).
Τον κρατάμε και σβήνουμε όλα τα πολλαπλάσιά του (όσα έχουν σβηστεί από πριν).

5. Παίρνουμε τον επόμενο αριθμό που έμεινε (το 7).
Τον κρατάμε και σβήνουμε όλα τα πολλαπλάσιά του (όσα δεν είναι σβησμένα από πριν).

Με τον ίδιο τρόπο συνεχίζουμε για πάντα (αφού οι αριθμοί δεν τελειώνουν ποτέ)!

 

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

 

Οι πρώτοι αριθμοί μέχρι το 120 δίνονται παρακάτω:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113.

Γεννάται λοιπόν το ερώτημα: Πόσοι είναι οι πρώτοι αριθμοί; Τελειώνουν κάπου; Την απάντηση έδωσε ο Ευκλείδης στα "Στοιχεία" του (Πρόταση ΙΧ.20) αποδεικνύοντας ότι το πλήθος τους είναι άπειρο. Η απόδειξη παραφράζεται εδώ και είναι η εξής:

Εξετάστε οποιαδήποτε πεπερασμένη λίστα πρώτων αριθμών p1, p2 , ... , pn. Θα αποδειχθεί, ότι υπάρχει τουλάχιστον ένας πρόσθετος πρώτος αριθμός, που δεν υπάρχει στη λίστα. Έστω P το γινόμενο όλων των πρώτων αριθμών στη λίστα, δηλ. 

P =p1 · p2 ·  ... ·  pn 

 Ας είναι q = P + 1. Τότε ο q είναι είτε πρώτος ή όχι:

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

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

Η απόδειξη αυτή του Ευκλείδη θεωρείται από τις κομψότερες αποδείξεις στην ιστορία των μαθηματικών.

 

Ένα κομμάτι παπύρου των Στοιχείων του Ευκλείδη, που χρονολογείται περίπου στο 75-125 μ.Χ.

Πηγές: 

Σημειώσεις Θεωρίας Αριθμών, Α. Θωμά, Πανεπιστήμιο Ιωαννίνων

Μαθηματικά  Ομάδας Προσανατολισμού Θετικών Σπουδών Β΄ Γενικού Λυκείου, ΙΤΥΕ "ΔΙΟΦΑΝΤΟΣ", 2021

Wikipedia.org

Γιατί ο περιοδικός δεκαδικός 0,999... ισούται με 1;

Στην ταινία γερμανικής παραγωγής "Στο γραφείο των καθηγητών" (Das Lehrerzimmer, 2023), η δασκάλα θέτει το εξής πρόβλημα στους δωδεκάχρονους μαθητές της:

Ο περιοδικός δεκαδικός αριθμός \(0,\bar{9}=0,999...\) (άπειρα εννιάρια) ισούται ή όχι με το \(1\);

Οι περισσότεροι μαθητές πιστεύουν ότι υπάρχει αριθμός μεταξύ του 0,999... και του 1. Μετά από συζήτηση, ο Όσκαρ γράφει στον πίνακα την εξής απάντηση:

Γνωρίζω ότι

\[ \frac{1}{9} = 1:9 = 0,111... \]

Έτσι,

\[0,\bar{1}=\frac{1}{9}\]

Πολλαπλασιάζοντας και τα δύο μέλη της ισότητας με 9, παίρνουμε:

\[ 0,\bar{9}=9 \cdot \frac{1}{9}\]

άρα

\[ 0,\bar{9}=1\]

Η εξήγηση βασίζεται στο ότι τα εννιάρια στον περιοδικό δεκαδικό 0,999... είναι άπειρα. Δείτε παρακάτω τη μαθηματική απόδειξη.

Θέτουμε \( x=0,999... (1) \)

Πολλαπλασιάζουμε τα δύο μέλη της ισότητας με 10, οπότε \( 10x=9,999... (2) \)

Αφαιρούμε κατά μέλη τις ισότητες, \( (2)-(1) \) και έχουμε 

\( 10x - x = 9,999... - 0,999... \Leftrightarrow \)

\( 9x = 9 \Leftrightarrow \)

\( x = 1 \)

Άρα \( 0,999...  = 1 \).