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

 

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

 

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 και τον εαυτό του. Για παράδειγμα οι αριθμοί 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

Ξενάγηση στο Μουσείο Γρίφων Μεγίστης!

 

Φέτος το "εις το άπειρον" επισκέφτηκε το Μουσείο Γρίφων Μεγίστης, που βρίσκεται στο πανέμορφο και ακριτικό Καστελλόριζο. Πρόκειται για το πρώτο και μοναδικό μουσείο γρίφων στην Ελλάδα και το τέταρτο σε όλο τον κόσμο. Με τον ιδρυτή του, κ. Πανταζή Χούλη, μαθηματικό και γριφολόγο, ζήσαμε μια όμορφη διαδραστική εμπειρία και σας προσφέρουμε μια ξενάγηση στον κόσμο των γρίφων.

Στην είσοδο μας περιμένει ένας καθρέφτης με οφθαλμαπάτες, προϊόντα 3D εκτύπωσης... 

Όταν ο κ. Πανταζής Χούλης επισκεπτόταν την ιδιαίτερη πατρίδα του, το Καστελλόριζο, είχε πάντα στο πίσω μέρος του μυαλού του ότι κάποτε θα επιστρέψει στο νησί του για να ζήσει μόνιμα. Το Καστελλόριζο, λοιπόν, επέλεξε για να ιδρύσει το Μουσείο Γρίφων Μεγίστης το 2020 και έκτοτε να διοργανώνει εργαστήρια, μέσω των οποίων δίνει την ευκαιρία στα παιδιά να λύνουν γρίφους και να κατασκευάζουν τους δικούς τους. Καθηγητής του Πανεπιστημίου της Δυτικής Αυστραλίας έως και το 2012 και γνωστός στην κοινότητα των γρίφων με πολλές τιμητικές διακρίσεις, κατέχει μια εκτενή συλλογή από 4.000 γρίφους, 700 από τους οποίους είναι δικές του επινοήσεις και πρωτότυπα. 

Ένα μικρό μέρος της συλλογής... 

Ο κ. Χούλης μας εξηγεί ότι υπάρχουν πολλά είδη γρίφων:

✅Οι ταιριαστικοί γρίφοι, που μοιάζουν με παζλ, όπως είναι το τάνγκραμ και το οστομάχιον του Αρχιμήδη.

✅Οι αναδιπλούμενοι γρίφοι, στους οποίους πρέπει να γίνει αναδίπλωση του σχήματος. Τέτοιοι είναι ο "Θρόνος των θεών" και ο "Φατσούλας", που συνδέεται με τη διεδρική ομάδα \(D_4\), με 8 στοιχεία.

Ο "Θρόνος των θεών" πριν και μετά την αναδίπλωση 

Ο "Φατσούλας" και τα μαθηματικά που κρύβονται πίσω από τον γρίφο 

✅Οι διασυνδεδεμένοι γρίφοι, όπου στόχος είναι να τους ανοίξουμε.

✅Οι λαβύρινθοι. Λέγεται ότι ο λαβύρινθος του Δαίδαλου θεωρείται ως το πρώτο escape room στην ανθρωπότητα.

✅Οι ακολουθιακοί γρίφοι, οι οποίοι θέλουν συγκεκριμένη ακολουθία κινήσεων για να επιλυθούν. Τέτοιοι είναι οι κύβοι Rubik, που σχετίζονται με τη Θεωρία Ομάδων και οι "Πυραμίδες μέσα στη Σφαίρα".

Οι συγκεκριμένοι κύβοι Ρούμπικ, επινοημένοι από τον Πανταζή Χούλη, παραμένουν αναλλοίωτοι με τις περιστροφές-μεταθέσεις. 

Οι "Πυραμίδες μέσα στη Σφαίρα"

✅Οι ανοιγόμενοι γρίφοι, όπως το "Σπιτάκι του Καστελλόριζου", ή ο γρίφος που χρησιμοποιεί τη φυγόκεντρο για να ανοιχτεί.

Το "Σπιτάκι του Καστελλόριζου" 

✅Το ανεξήγητο αντικείμενο, όπως το "Καραβάκι μέσα σε μπουκαλάκι". 

✅Οι εκλιπόμενοι ή εξαφανιζόμενοι γρίφοι, όπως ο γρίφος με το κομμάτι σοκολάτας που λείπει. 

...και τόσοι άλλοι... 

Τρισδιάστατο Τέτρις

Το "Γριφοπούλι" 

Τα "Πανταζάρια", ζάρια σχεδιασμένα έτσι, ώστε να κερδίζεις πάντα τον αντίπαλό σου, με βάση τη Θεωρία Πιθανοτήτων. 

Οι κωνικές τομές 

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

Ένας αναγραμματισμός της λέξης "ΚΑΣΤΕΛΛΟΡΙΖΟ" είναι το "ΖΕΣΤΟ ΚΟΡΑΛΛΙ".

🧮Θεσμός έχει γίνει πλέον το Φεστιβάλ Γρίφων, που διοργανώνεται από το Μουσείο Γρίφων. Στις 11-13 Οκτωβρίου 2024 θα διεξαχθεί το 4ο Φεστιβάλ Γρίφων στο Καστελλόριζο, όπου μεταξύ των προσκεκλημένων θα είναι και ο εφευρέτης του πασίγνωστου "Κύβου του Ρούμπικ", Έρνο Ρούμπικ.

🌐Μπορείτε να μαθαίνετε τα νέα του Μουσείου Γρίφων μέσα από τη σελίδα του στο Facebook: Ένωση Ιδεών, Γρίφων, Μαθηματικών (ΕΝ.Ι.Γ.ΜΑ.).

 

Ο αλγόριθμος υπολογισμού της ημερομηνίας του ορθόδοξου Πάσχα από τον Gauss

 

Πότε πέφτει φέτος το Πάσχα; Του χρόνου;

Στο βίντεο του μαθηματικού Θανάση Δρούγα (Μαθημαγικά) παρουσιάζεται ο αλγόριθμος του Gauss, με τον οποίο μπορούμε να βρούμε πότε πέφτει το Πάσχα των ορθοδόξων οποιαδήποτε χρονιά μέχρι το 2099.

Ο τύπος υπολογισμού της ημερομηνίας του Πάσχα είναι:

όπου \(x\) το έτος, \(H(x)\) η ημερομηνία που πέφτει το Πάσχα το έτος \(x\) και \(AmodB\) το υπόλοιπο της Ευκλείδειας Διαίρεσης του \(A\) με το \(B\).

Πατώντας εδώ: ("GeeksforGeeks"), μπορείτε να δείτε τον αλγόριθμο σε C++, Java, Python3, C#, Javascript.

Επαληθεύστε το για \(x=2022\) !