Ορισμός 1. πρώτος αριθμός− είναι ένας φυσικός αριθμός μεγαλύτερος από έναν που διαιρείται μόνο με τον εαυτό του και το 1.

Με άλλα λόγια, ένας αριθμός είναι πρώτος εάν έχει μόνο δύο διακριτούς φυσικούς διαιρέτες.

Ορισμός 2. Κάθε φυσικός αριθμός που έχει άλλους διαιρέτες εκτός από τον εαυτό του και ένα ονομάζεται ένας σύνθετος αριθμός.

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

Από τους ορισμούς 1 και 2 προκύπτει ότι κάθε θετικός ακέραιος μεγαλύτερος από 1 είναι είτε πρώτος είτε σύνθετος αριθμός.

Παρακάτω είναι ένα πρόγραμμα για την εμφάνιση πρώτων αριθμών μέχρι το 5000. Συμπληρώστε τα κελιά, κάντε κλικ στο κουμπί "Δημιουργία" και περιμένετε μερικά δευτερόλεπτα.

Πίνακας πρώτων αριθμών

Δήλωση 1. Αν Π- πρώτος αριθμός και έναοποιοδήποτε ακέραιο, τότε είτε έναδιαιρείται με Π, ή ΠΚαι ένασυμπρώτες αριθμοί.

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

Δήλωση 2. Αν το γινόμενο πολλών αριθμών αριθμών ένα 1 , ένα 2 , έναΤο 3, ... διαιρείται με έναν πρώτο αριθμό Π, τότε τουλάχιστον ένας από τους αριθμούς ένα 1 , ένα 2 , ένα 3, ...διαιρείται με Π.

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

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

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

Ας υποθέσουμε ότι υπάρχουν δύο αποσυνθέσεις ενός αριθμού κ:

Επειδή k=p 1 Π 2 Π 3...διαιρείται με πρώτο αριθμό q 1, τότε τουλάχιστον ένας από τους παράγοντες, για παράδειγμα ΠΤο 1 διαιρείται με q 1 . Αλλά ΠΤο 1 είναι πρώτος αριθμός και διαιρείται μόνο με το 1 και τον εαυτό του. Ως εκ τούτου Π 1 =q 1 (γιατί q 1 ≠1)

Τότε από το (2) μπορούμε να εξαιρέσουμε Π 1 και q 1:

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

Επέκταση σύνθετου αριθμού κμπορεί να γραφτεί με την παρακάτω μορφή

(3)

Οπου Π 1 , Π 2, ... διάφοροι πρώτοι αριθμοί, α, β, γ ... θετικοί ακέραιοι αριθμοί.

Η επέκταση (3) ονομάζεται κανονική επέκτασηαριθμοί.

Οι πρώτοι αριθμοί εμφανίζονται άνισα στη σειρά των φυσικών αριθμών. Σε ορισμένα σημεία της σειράς υπάρχουν περισσότερα από αυτά, σε άλλα - λιγότερα. Όσο περισσότερο προχωράμε κατά μήκος της σειράς αριθμών, τόσο λιγότερο συνηθισμένοι είναι οι πρώτοι αριθμοί. Τίθεται το ερώτημα, υπάρχει ο μεγαλύτερος πρώτος αριθμός; Ο αρχαίος Έλληνας μαθηματικός Ευκλείδης απέδειξε ότι υπάρχουν άπειροι πρώτοι αριθμοί. Παραθέτουμε αυτήν την απόδειξη παρακάτω.

Θεώρημα 2. Ο αριθμός των πρώτων αριθμών είναι άπειρος.

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

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

Αυτό το θεώρημα είναι μια ειδική περίπτωση ενός γενικότερου θεωρήματος:

Θεώρημα 3. Ας δοθεί μια αριθμητική πρόοδος

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

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

Δήλωση 3. Αφήνω ένα 1 ,ένα 2 ,ένα 3,... διάφοροι πρώτοι αριθμοί περιλαμβάνονται σε ΜΈτσι

Οπου Εγώ=0,1,...α , ι=0,1,...,β , k=0,1,..., γ . σημειώσε ότι αiδέχεται α +1 τιμές, β j δέχεται β +1 τιμές, γ κ δέχεται γ Τιμές +1, ... .

Το άρθρο εξετάζει τις έννοιες των πρώτων και των σύνθετων αριθμών. Οι ορισμοί τέτοιων αριθμών δίνονται με παραδείγματα. Παρουσιάζουμε μια απόδειξη ότι ο αριθμός των πρώτων αριθμών είναι απεριόριστος και θα την καταγράψουμε στον πίνακα των πρώτων αριθμών με τη μέθοδο του Ερατοσθένη. Θα δοθούν στοιχεία για να καθοριστεί εάν ένας αριθμός είναι πρώτος ή σύνθετος.

Yandex.RTB R-A-339285-1

Πρώτοι και σύνθετοι αριθμοί - Ορισμοί και παραδείγματα

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

Ορισμός 1

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

Ορισμός 2

Οι σύνθετοι αριθμοί είναι ακέραιοι αριθμοί που είναι μεγαλύτεροι του ενός και έχουν τουλάχιστον τρεις θετικούς διαιρέτες.

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

Ορισμός 3

πρώτοι αριθμοίείναι φυσικοί αριθμοί που έχουν μόνο δύο θετικούς διαιρέτες.

Ορισμός 4

Σύνθετος αριθμός είναι ένας φυσικός αριθμός που έχει περισσότερους από δύο θετικούς διαιρέτες.

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

Ορισμός 5

Οι φυσικοί αριθμοί που δεν είναι πρώτοι ονομάζονται σύνθετοι αριθμοί.

Πρώτοι αριθμοί: 2, 3, 11, 17, 131, 523. Διαιρούνται μόνο με τον εαυτό τους και το 1. Σύνθετοι αριθμοί: 6, 63, 121, 6697. Δηλαδή, ο αριθμός 6 μπορεί να αποσυντεθεί σε 2 και 3, και 63 σε 1, 3, 7, 9, 21, 63 και 121 σε 11, 11, δηλαδή οι διαιρέτες του θα είναι 1, 11, 121. Ο αριθμός 6697 διασπάται σε 37 και 181. Σημειώστε ότι οι έννοιες των πρώτων αριθμών και των συνπρώτων αριθμών είναι διαφορετικές έννοιες.

Για να διευκολύνετε τη χρήση πρώτων αριθμών, πρέπει να χρησιμοποιήσετε έναν πίνακα:

Ένας πίνακας για όλους τους υπάρχοντες φυσικούς αριθμούς δεν είναι ρεαλιστικός, αφού υπάρχουν άπειρο σύνολο. Όταν οι αριθμοί φτάνουν σε μεγέθη 10000 ή 1000000000, τότε θα πρέπει να σκεφτείτε να χρησιμοποιήσετε το κόσκινο του Ερατοσθένη.

Ας εξετάσουμε το θεώρημα που εξηγεί την τελευταία πρόταση.

Θεώρημα 1

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

Αποδεικτικά στοιχεία 1

Ας υποθέσουμε ότι ο a είναι ένας φυσικός αριθμός που είναι μεγαλύτερος από 1, ο b είναι ο μικρότερος μη-ένας διαιρέτης του a. Είναι απαραίτητο να αποδειχθεί ότι ο b είναι πρώτος αριθμός χρησιμοποιώντας τη μέθοδο της αντίφασης.

Ας υποθέσουμε ότι το b είναι ένας σύνθετος αριθμός. Από εδώ έχουμε ότι υπάρχει διαιρέτης για το b, ο οποίος είναι διαφορετικός από το 1 καθώς και από το b. Ένας τέτοιος διαιρέτης συμβολίζεται ως b 1. Είναι απαραίτητη η προϋπόθεση 1< b 1 < b ολοκληρώθηκε.

Από την προϋπόθεση είναι σαφές ότι το a διαιρείται με το b, το b διαιρείται με το b 1, που σημαίνει ότι η έννοια της διαιρετότητας εκφράζεται ως εξής: a = b qκαι b = b 1 · q 1 , από όπου a = b 1 · (q 1 · q) , όπου q και q 1είναι ακέραιοι. Σύμφωνα με τον κανόνα του πολλαπλασιασμού των ακεραίων, έχουμε ότι το γινόμενο των ακεραίων είναι ένας ακέραιος αριθμός με ισότητα της μορφής a = b 1 · (q 1 · q) . Μπορεί να φανεί ότι το b 1 είναι ο διαιρέτης του αριθμού α. Ανισότητα 1< b 1 < b Δεναντιστοιχεί, γιατί βρίσκουμε ότι το b είναι ο μικρότερος θετικός και μη-1 διαιρέτης του a.

Θεώρημα 2

Υπάρχει άπειρος αριθμός πρώτων αριθμών.

Αποδεικτικά στοιχεία 2

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

Ας λάβουμε υπόψη τον αριθμό p, ο οποίος είναι ίσος με p 1, p 2, ..., p n + 1. Δεν ισούται με καθέναν από τους αριθμούς που αντιστοιχούν σε πρώτους αριθμούς της μορφής p 1, p 2, ..., p n. Ο αριθμός p είναι πρώτος. Τότε το θεώρημα θεωρείται αποδεδειγμένο. Εάν είναι σύνθετο, τότε πρέπει να πάρετε τον συμβολισμό p n + 1 και να δείξετε ότι ο διαιρέτης δεν συμπίπτει με κανένα από τα p 1, p 2, ..., p n.

Αν δεν ήταν έτσι, τότε, με βάση την ιδιότητα διαιρετότητας του γινομένου p 1, p 2, ..., p n , βρίσκουμε ότι θα διαιρείται με το pn + 1. Σημειώστε ότι η έκφραση p n + 1 διαιρώντας τον αριθμό p ισούται με το άθροισμα p 1, p 2, ..., p n + 1. Λαμβάνουμε ότι η έκφραση p n + 1 Ο δεύτερος όρος αυτού του αθροίσματος, που ισούται με 1, πρέπει να διαιρεθεί, αλλά αυτό είναι αδύνατο.

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

Δεδομένου ότι υπάρχουν πολλοί πρώτοι αριθμοί, οι πίνακες περιορίζονται στους αριθμούς 100, 1000, 10000 και ούτω καθεξής.

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

Ας το δούμε βήμα βήμα.

Εάν ξεκινήσετε με τον αριθμό 2, τότε έχει μόνο 2 διαιρέτες: 2 και 1, που σημαίνει ότι μπορεί να εισαχθεί στον πίνακα. Το ίδιο με τον αριθμό 3. Ο αριθμός 4 είναι σύνθετος, πρέπει να αποσυντεθεί σε 2 και 2. Ο αριθμός 5 είναι πρώτος, πράγμα που σημαίνει ότι μπορεί να καταγραφεί στον πίνακα. Κάντε αυτό μέχρι τον αριθμό 100.

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

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

Τώρα πρέπει να διαγράψετε όλους τους αριθμούς που είναι πολλαπλάσιοι του 2. Εκτελέστε διαδοχικές διαγραμμίσεις. Παίρνουμε έναν πίνακα όπως:

Προχωράμε στη διαγραφή αριθμών που είναι πολλαπλάσια του 5. Παίρνουμε:

Διαγράψτε αριθμούς που είναι πολλαπλάσιοι του 7, του 11. Τελικά ο πίνακας μοιάζει

Ας προχωρήσουμε στη διατύπωση του θεωρήματος.

Θεώρημα 3

Ο μικρότερος θετικός και μη-1 διαιρέτης του βασικού αριθμού a δεν υπερβαίνει το a, όπου a είναι η αριθμητική ρίζα του δεδομένου αριθμού.

Αποδεικτικά στοιχεία 3

Πρέπει να οριστεί β ελάχιστος διαιρέτηςσύνθετος αριθμός α. Υπάρχει ένας ακέραιος q, όπου a = b · q, και έχουμε ότι b ≤ q. Οι ανισότητες της μορφής είναι απαράδεκτες b > q,γιατί παραβιάζεται η προϋπόθεση. Και οι δύο πλευρές της ανίσωσης b ≤ q πρέπει να πολλαπλασιαστούν με οποιονδήποτε θετικό αριθμό b που δεν ισούται με 1. Παίρνουμε ότι b · b ≤ b · q, όπου b 2 ≤ a και b ≤ a.

Από το αποδεδειγμένο θεώρημα είναι σαφές ότι η διαγραφή αριθμών στον πίνακα οδηγεί στο γεγονός ότι είναι απαραίτητο να ξεκινήσετε με έναν αριθμό που είναι ίσος με b 2 και ικανοποιεί την ανίσωση b 2 ≤ a. Δηλαδή, αν διαγράψετε αριθμούς που είναι πολλαπλάσιο του 2, τότε η διαδικασία ξεκινά με το 4 και πολλαπλάσια του 3 με το 9 και ούτω καθεξής μέχρι το 100.

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

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

Παράδειγμα 1

Αποδείξτε ότι ο αριθμός 898989898989898989 είναι σύνθετος.

Λύση

Το άθροισμα των ψηφίων ενός δεδομένου αριθμού είναι 9 8 + 9 9 = 9 17. Αυτό σημαίνει ότι ο αριθμός 9 · 17 διαιρείται με το 9, με βάση το τεστ διαιρετότητας με το 9. Από αυτό προκύπτει ότι είναι σύνθετο.

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

Παράδειγμα 2

Προσδιορίστε τον σύνθετο ή πρώτο αριθμό 11723.

Λύση

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

Από εδώ βλέπουμε ότι το 11723< 200 , то 200 2 = 40 000 και 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Για πιο ακριβή εκτίμηση του αριθμού 11723, πρέπει να γράψετε την έκφραση 108 2 = 11 664 και 109 2 = 11 881 , Οτι 108 2 < 11 723 < 109 2 . Από αυτό προκύπτει ότι το 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

Κατά την επέκταση, βρίσκουμε ότι 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 είναι όλοι πρώτοι αριθμοί. Όλη αυτή η διαδικασία μπορεί να απεικονιστεί ως διαίρεση με μια στήλη. Δηλαδή, διαιρέστε το 11723 με το 19. Ο αριθμός 19 είναι ένας από τους παράγοντες του, αφού παίρνουμε διαίρεση χωρίς υπόλοιπο. Ας αναπαραστήσουμε τη διαίρεση ως στήλη:

Από αυτό προκύπτει ότι το 11723 είναι σύνθετος αριθμός, γιατί εκτός από τον εαυτό του και το 1 έχει διαιρέτη του 19.

Απάντηση:Το 11723 είναι ένας σύνθετος αριθμός.

Εάν παρατηρήσετε κάποιο σφάλμα στο κείμενο, επισημάνετε το και πατήστε Ctrl+Enter

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

Εξ ορισμού, το σύνολο όλων των διαιρετών ενός πρώτου αριθμού είναι δύο στοιχείων, δηλ. αντιπροσωπεύει ένα σύνολο.

Το σύνολο όλων των πρώτων αριθμών συμβολίζεται με το σύμβολο. Έτσι, λόγω του ορισμού του συνόλου των πρώτων αριθμών, μπορούμε να γράψουμε: .

Η ακολουθία των πρώτων αριθμών μοιάζει με αυτό:

Θεμελιώδες Θεώρημα Αριθμητικής

Θεμελιώδες Θεώρημα Αριθμητικήςδηλώνει ότι κάθε φυσικός αριθμός μεγαλύτερος του ενός μπορεί να αναπαρασταθεί ως γινόμενο πρώτων αριθμών και με μοναδικό τρόπο, μέχρι την τάξη των παραγόντων. Έτσι, οι πρώτοι αριθμοί είναι τα στοιχειώδη «δομικά στοιχεία» του συνόλου των φυσικών αριθμών.

Επέκταση φυσικού αριθμού title="Απόδοση από QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} κανονικός:

όπου είναι ένας πρώτος αριθμός και . Για παράδειγμα, η κανονική επέκταση ενός φυσικού αριθμού μοιάζει με αυτό: .

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

Ιδιότητες Πρώτων Αριθμών

Κόσκινο του Ερατοσθένη

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

Για να βρείτε όλους τους πρώτους αριθμούς μικρότερους από έναν δεδομένο αριθμό, ακολουθώντας τη μέθοδο του Ερατοσθένη, ακολουθήστε τα εξής βήματα:

Βήμα 1.Γράψτε όλους τους φυσικούς αριθμούς από το δύο έως το , δηλ. .
Βήμα 2.Αντιστοιχίστε στη μεταβλητή την τιμή , δηλαδή την τιμή ίση με τον μικρότερο πρώτο αριθμό.
Βήμα 3.Διαγράψτε στη λίστα όλους τους αριθμούς από έως εκείνους που είναι πολλαπλάσιοι του , δηλαδή οι αριθμοί: .
Βήμα 4.Βρείτε τον πρώτο μη σταυρωμένο αριθμό στη λίστα μεγαλύτερο από και εκχωρήστε την τιμή αυτού του αριθμού σε μια μεταβλητή.
Βήμα 5.Επαναλάβετε τα βήματα 3 και 4 μέχρι να φτάσετε τον αριθμό.

Η διαδικασία εφαρμογής του αλγορίθμου θα μοιάζει με αυτό:

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

Εικασία Γκόλντμπαχ

Εξώφυλλο του βιβλίου «Ο θείος Πέτρος και η υπόθεση Γκόλντμπαχ»

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

• Είναι αλήθεια ότι κάθε Ζυγός αριθμός, μεγαλύτερο από δύο, μπορεί να αναπαρασταθεί ως το άθροισμα δύο πρώτων αριθμών (δυαδική υπόθεση Goldbach);
• Είναι αλήθεια ότι κάθε περιττός αριθμός μεγαλύτερος του 5 μπορεί να αναπαρασταθεί ως το άθροισμα τριών πρώτων αριθμών (τριαδική υπόθεση του Γκόλντμπαχ);

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

Η εικασία του Goldbach έγινε ευρέως γνωστή εκτός της μαθηματικής κοινότητας το 2000 χάρη σε ένα διαφημιστικό κόλπο από τις εκδοτικές εταιρείες Bloomsbury USA (ΗΠΑ) και Faber and Faber (Ηνωμένο Βασίλειο). Αυτοί οι εκδοτικοί οίκοι, έχοντας κυκλοφορήσει το βιβλίο «Uncle Petros and Goldbach’s Conjecture», υποσχέθηκαν να πληρώσουν ένα βραβείο 1 εκατομμυρίου δολαρίων ΗΠΑ σε όποιον αποδείξει την υπόθεση του Goldbach εντός 2 ετών από την ημερομηνία έκδοσης του βιβλίου. Μερικές φορές το αναφερόμενο βραβείο από τους εκδότες συγχέεται με τα βραβεία για την επίλυση των Προβλημάτων του Βραβείου Χιλιετίας. Μην κάνετε λάθος, η υπόθεση του Goldbach δεν ταξινομείται από το Ινστιτούτο Clay ως «πρόκληση της χιλιετίας», αν και σχετίζεται στενά με Υπόθεση Riemann- μία από τις «προκλήσεις της χιλιετίας».

Το βιβλίο «Πρώτοι αριθμοί. Μακρύς δρόμος προς το άπειρο»

Εξώφυλλο του βιβλίου «The World of Mathematics. Πρώτοι αριθμοί. Μακρύς δρόμοςστο άπειρο"

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

Επιπλέον, θα παραθέσω την αρχή του δεύτερου κεφαλαίου αυτού του βιβλίου: «Οι πρώτοι αριθμοί είναι ένας από τους σημαντικά θέματα, που μας φέρνουν πίσω στις απαρχές των μαθηματικών και στη συνέχεια, σε μια πορεία αυξανόμενης πολυπλοκότητας, μας οδηγούν στο προσκήνιο σύγχρονη επιστήμη. Έτσι, θα ήταν πολύ χρήσιμο να ανιχνεύσουμε τη συναρπαστική και πολύπλοκη ιστορία της θεωρίας των πρώτων αριθμών: πώς ακριβώς αναπτύχθηκε, πώς ακριβώς συλλέχθηκαν τα γεγονότα και οι αλήθειες που είναι τώρα γενικά αποδεκτές. Σε αυτό το κεφάλαιο θα δούμε πώς γενιές μαθηματικών μελέτησαν προσεκτικά τους φυσικούς αριθμούς αναζητώντας έναν κανόνα που προέβλεπε την εμφάνιση των πρώτων αριθμών - ένας κανόνας που γινόταν όλο και πιο άπιαστος καθώς προχωρούσε η αναζήτηση. Θα εξετάσουμε επίσης λεπτομερώς το ιστορικό πλαίσιο: υπό ποιες συνθήκες εργάζονταν οι μαθηματικοί και σε ποιο βαθμό η δουλειά τους περιελάμβανε μυστικιστικές και ημιθρησκευτικές πρακτικές, που δεν μοιάζουν καθόλου με επιστημονικές μεθόδους, χρησιμοποιείται στις μέρες μας. Ωστόσο, αργά και με δυσκολία, προετοιμάστηκε το έδαφος για νέες απόψεις που ενέπνευσαν τον Fermat και τον Euler τον 17ο και τον 18ο αιώνα».

• Μετάφραση

Οι ιδιότητες των πρώτων αριθμών μελετήθηκαν για πρώτη φορά από μαθηματικούς Αρχαία Ελλάδα. Οι μαθηματικοί της Πυθαγόρειας σχολής (500 - 300 π.Χ.) ενδιαφέρθηκαν πρωτίστως για τις μυστικιστικές και αριθμητικές ιδιότητες των πρώτων αριθμών. Ήταν οι πρώτοι που σκέφτηκαν ιδέες για τέλειους και φιλικούς αριθμούς.

Ένας τέλειος αριθμός έχει ένα άθροισμα των δικών του διαιρετών ίσο με τον εαυτό του. Για παράδειγμα, οι σωστοί διαιρέτες του αριθμού 6 είναι 1, 2 και 3. 1 + 2 + 3 = 6. Οι διαιρέτες του αριθμού 28 είναι 1, 2, 4, 7 και 14. Επιπλέον, 1 + 2 + 4 + 7 + 14 = 28.

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

Μέχρι την εποχή των Στοιχείων του Ευκλείδη το 300 π.Χ. αρκετά έχουν ήδη αποδειχθεί σημαντικά γεγονότασχετικά με τους πρώτους αριθμούς. Στο Βιβλίο ΙΧ των Στοιχείων, ο Ευκλείδης απέδειξε ότι υπάρχει άπειρος αριθμός πρώτων αριθμών. Αυτό, παρεμπιπτόντως, είναι ένα από τα πρώτα παραδείγματα χρήσης απόδειξης με αντίφαση. Αποδεικνύει επίσης το Θεμελιώδες Θεώρημα της Αριθμητικής - κάθε ακέραιος αριθμός μπορεί να αναπαρασταθεί μοναδικά ως γινόμενο πρώτων αριθμών.

Έδειξε επίσης ότι αν ο αριθμός 2n-1 είναι πρώτος, τότε ο αριθμός 2n-1 * (2n-1) θα είναι τέλειος. Ένας άλλος μαθηματικός, ο Euler, μπόρεσε να δείξει το 1747 ότι όλοι οι ακόμη τέλειοι αριθμοί μπορούν να γραφτούν με αυτή τη μορφή. Μέχρι σήμερα είναι άγνωστο αν υπάρχουν περιττοί τέλειοι αριθμοί.

Το έτος 200 π.Χ. Ο Έλληνας Ερατοσθένης βρήκε έναν αλγόριθμο για την εύρεση πρώτων αριθμών που ονομάζεται κόσκινο του Ερατοσθένη.

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

Οι ακόλουθες ανακαλύψεις έγιναν ήδη στις αρχές του 17ου αιώνα από τον μαθηματικό Fermat. Απέδειξε την εικασία του Albert Girard ότι οποιοσδήποτε πρώτος αριθμός της μορφής 4n+1 μπορεί να γραφτεί μοναδικά ως άθροισμα δύο τετραγώνων, και επίσης διατύπωσε το θεώρημα ότι οποιοσδήποτε αριθμός μπορεί να γραφτεί ως άθροισμα τεσσάρων τετραγώνων.

Ανέπτυξε μια νέα μέθοδο για την παραγοντοποίηση μεγάλων αριθμών και την έδειξε στον αριθμό 2027651281 = 44021 × 46061. Απέδειξε επίσης το Μικρό Θεώρημα του Φερμά: αν το p είναι πρώτος αριθμός, τότε για οποιονδήποτε ακέραιο a θα είναι αληθές ότι a p = συντελεστής Π.

Αυτή η δήλωση αποδεικνύει το μισό από αυτό που ήταν γνωστό ως "κινεζική εικασία" και χρονολογείται πριν από 2000 χρόνια: ένας ακέραιος αριθμός n είναι πρώτος εάν και μόνο εάν το 2 n -2 διαιρείται με το n. Το δεύτερο μέρος της υπόθεσης αποδείχθηκε ψευδές - για παράδειγμα, το 2.341 - 2 διαιρείται με το 341, αν και ο αριθμός 341 είναι σύνθετος: 341 = 31 × 11.

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

Ο Φερμά αλληλογραφούσε πολύ με τους συγχρόνους του, ιδιαίτερα με έναν μοναχό ονόματι Maren Mersenne. Σε ένα από τα γράμματά του, υπέθεσε ότι οι αριθμοί της μορφής 2 n +1 θα είναι πάντα πρώτοι αν το n είναι δύναμη του δύο. Το δοκίμασε αυτό για n = 1, 2, 4, 8 και 16 και ήταν σίγουρος ότι στην περίπτωση που το n δεν ήταν δύναμη του δύο, ο αριθμός δεν ήταν απαραίτητα πρώτος. Αυτοί οι αριθμοί ονομάζονται αριθμοί του Fermat, και μόνο 100 χρόνια αργότερα ο Euler έδειξε ότι ο επόμενος αριθμός, 2 32 + 1 = 4294967297, διαιρείται με το 641 και επομένως δεν είναι πρώτος.

Οι αριθμοί της μορφής 2 n - 1 έχουν επίσης αποτελέσει αντικείμενο έρευνας, αφού είναι εύκολο να φανεί ότι αν το n είναι σύνθετο, τότε και ο ίδιος ο αριθμός είναι σύνθετος. Αυτοί οι αριθμοί ονομάζονται αριθμοί Mersenne επειδή τους μελέτησε εκτενώς.

Αλλά δεν είναι όλοι οι αριθμοί της μορφής 2 n - 1, όπου n είναι πρώτος, πρώτοι. Για παράδειγμα, 2 11 - 1 = 2047 = 23 * 89. Αυτό ανακαλύφθηκε για πρώτη φορά το 1536.

Για πολλά χρόνια, αριθμοί αυτού του είδους παρείχαν στους μαθηματικούς τους μεγαλύτερους γνωστούς πρώτους αριθμούς. Αυτό το M 19 αποδείχθηκε από τον Cataldi το 1588, και για 200 χρόνια ήταν ο μεγαλύτερος γνωστός πρώτος αριθμός, έως ότου ο Euler απέδειξε ότι ο M 31 ήταν επίσης πρώτος. Αυτό το ρεκόρ έμεινε για άλλα εκατό χρόνια και μετά ο Λούκας έδειξε ότι το M 127 είναι πρώτο (και αυτό είναι ήδη ένας αριθμός 39 ψηφίων) και μετά από αυτό η έρευνα συνεχίστηκε με την εμφάνιση των υπολογιστών.

Το 1952 αποδείχθηκε η πρωταρχικότητα των αριθμών M 521, M 607, M 1279, M 2203 και M 2281.

Μέχρι το 2005, είχαν βρεθεί 42 πρώτοι αριθμοί Mersenne. Το μεγαλύτερο από αυτά, το M 25964951, αποτελείται από 7816230 ψηφία.

Το έργο του Euler είχε τεράστιο αντίκτυπο στη θεωρία των αριθμών, συμπεριλαμβανομένων των πρώτων αριθμών. Επέκτεινε το Μικρό Θεώρημα του Φερμά και εισήγαγε τη συνάρτηση φ. Παραγοντοποίησε τον αριθμό 2 32 +1 του 5ου Fermat, βρήκε 60 ζεύγη φιλικών αριθμών και διατύπωσε (αλλά δεν μπόρεσε να αποδείξει) τον νόμο της τετραγωνικής αμοιβαιότητας.

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

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Το αποτέλεσμα που προκύπτει από το άθροισμα των αντίστροφων πρώτων αριθμών αποκλίνει επίσης. Το άθροισμα των n όρων της αρμονικής σειράς αυξάνεται περίπου ως log(n) και η δεύτερη σειρά αποκλίνει πιο αργά ως log[ log(n) ]. Αυτό σημαίνει ότι, για παράδειγμα, το άθροισμα των αντίστροφων όλων των πρώτων αριθμών που βρέθηκαν μέχρι σήμερα θα δώσει μόνο 4, αν και η σειρά εξακολουθεί να αποκλίνει.

Με την πρώτη ματιά, φαίνεται ότι οι πρώτοι αριθμοί κατανέμονται αρκετά τυχαία μεταξύ ακεραίων. Για παράδειγμα, μεταξύ των 100 αριθμών αμέσως πριν από το 10000000 υπάρχουν 9 πρώτοι, και μεταξύ των 100 αριθμών αμέσως μετά από αυτήν την τιμή υπάρχουν μόνο 2. Αλλά σε μεγάλα τμήματα οι πρώτοι αριθμοί κατανέμονται αρκετά ομοιόμορφα. Ο Legendre και ο Gauss ασχολήθηκαν με θέματα διανομής τους. Ο Γκάους είπε κάποτε σε έναν φίλο του ότι σε κάθε ελεύθερο 15λεπτο μετράει πάντα τον αριθμό των πρώτων στους επόμενους 1000 αριθμούς. Μέχρι το τέλος της ζωής του, είχε μετρήσει όλους τους πρώτους αριθμούς μέχρι τα 3 εκατομμύρια. Ο Legendre και ο Gauss υπολόγισαν εξίσου ότι για μεγάλα n η πρωταρχική πυκνότητα είναι 1/log(n). Ο Legendre υπολόγισε τον αριθμό των πρώτων αριθμών στην περιοχή από 1 έως n ως

π(n) = n/(log(n) - 1,08366)

Και το Gauss είναι σαν ένα λογαριθμικό ολοκλήρωμα

π(n) = ∫ 1/log(t) dt

Με διάστημα ολοκλήρωσης από 2 έως n.

Η δήλωση σχετικά με την πυκνότητα των πρώτων 1/log(n) είναι γνωστή ως Θεώρημα Πρωταρχικής Κατανομής. Προσπάθησαν να το αποδείξουν σε όλη τη διάρκεια του 19ου αιώνα, και η πρόοδος επιτεύχθηκε από τους Chebyshev και Riemann. Το συνέδεσαν με την υπόθεση Riemann, μια ακόμη αναπόδεικτη υπόθεση σχετικά με την κατανομή των μηδενικών της συνάρτησης Riemann zeta. Η πυκνότητα των πρώτων αριθμών αποδείχθηκε ταυτόχρονα από τους Hadamard και Vallée-Poussin το 1896.

Υπάρχουν ακόμη πολλά άλυτα ερωτήματα στη θεωρία των πρώτων αριθμών, μερικά από τα οποία είναι εκατοντάδων ετών:

• Η υπόθεση των δίδυμων πρώτων αριθμών αφορά έναν άπειρο αριθμό ζευγών πρώτων αριθμών που διαφέρουν μεταξύ τους κατά 2
• Εικασία του Goldbach: οποιοσδήποτε ζυγός αριθμός, που ξεκινά από το 4, μπορεί να αναπαρασταθεί ως το άθροισμα δύο πρώτων αριθμών
• Υπάρχει άπειρος αριθμός πρώτων αριθμών της μορφής n 2 + 1;
• Είναι πάντα δυνατό να βρεθεί ένας πρώτος αριθμός μεταξύ n 2 και (n + 1) 2; (το γεγονός ότι υπάρχει πάντα ένας πρώτος αριθμός μεταξύ n και 2n αποδείχθηκε από τον Chebyshev)
• Είναι άπειρος ο αριθμός των πρώτων αριθμών Fermat; Υπάρχουν πρώτοι Fermat μετά το 4;
• υπάρχει αριθμητική πρόοδος διαδοχικών πρώτων για οποιοδήποτε δεδομένο μήκος; για παράδειγμα, για μήκος 4: 251, 257, 263, 269. Το μέγιστο μήκος που βρέθηκε είναι 26.
• Υπάρχει άπειρος αριθμός συνόλων τριών διαδοχικών πρώτων αριθμών σε μια αριθμητική πρόοδο;
• Το n 2 - n + 41 είναι πρώτος αριθμός για 0 ​​≤ n ≤ 40. Υπάρχει άπειρος αριθμός τέτοιων πρώτων αριθμών; Η ίδια ερώτηση για τον τύπο n 2 - 79 n + 1601. Αυτοί οι αριθμοί είναι πρώτοι για 0 ​​≤ n ≤ 79.
• Υπάρχει άπειρος αριθμός πρώτων αριθμών της μορφής n# + 1; (το n# είναι το αποτέλεσμα του πολλαπλασιασμού όλων των πρώτων αριθμών μικρότερων από n)
• Υπάρχει άπειρος αριθμός πρώτων αριθμών της μορφής n# -1 ;
• Υπάρχει άπειρος αριθμός πρώτων αριθμών της μορφής n; + 1;
• Υπάρχει άπειρος αριθμός πρώτων αριθμών της μορφής n; - 1;
• αν το p είναι πρώτος, το 2 p -1 δεν περιέχει πάντα πρώτους τετραγώνους μεταξύ των παραγόντων του;
• περιέχει η ακολουθία Fibonacci άπειρο αριθμό πρώτων αριθμών;

Οι μεγαλύτεροι δίδυμοι πρώτοι αριθμοί είναι 2003663613 × 2 195000 ± 1. Αποτελούνται από 58711 ψηφία και ανακαλύφθηκαν το 2007.

Ο μεγαλύτερος παραγοντικός πρώτος αριθμός (του τύπου n! ± 1) είναι 147855! - 1. Αποτελείται από 142891 ψηφία και βρέθηκε το 2002.

Ο μεγαλύτερος αρχικός πρώτος αριθμός (ένας αριθμός της μορφής n# ± 1) είναι 1098133# + 1.

Αριθμός διαιρετών.Εξ ορισμού, αριθμός nείναι πρώτος μόνο αν δεν διαιρείται ομοιόμορφα με το 2 και άλλους ακέραιους εκτός από το 1 και τον εαυτό του. Ο παραπάνω τύπος αφαιρεί τα περιττά βήματα και εξοικονομεί χρόνο: για παράδειγμα, αφού ελέγξετε εάν ένας αριθμός διαιρείται με το 3, δεν χρειάζεται να ελέγξετε αν διαιρείται με το 9.

• Η συνάρτηση πάτωμα(x) στρογγυλοποιεί το x στον πλησιέστερο ακέραιο που είναι μικρότερος ή ίσος του x.

Μάθετε για την αρθρωτή αριθμητική.Η πράξη "x mod y" (το mod είναι συντομογραφία της λατινικής λέξης "modulo", δηλαδή "module") σημαίνει "διαιρέστε το x με το y και βρείτε το υπόλοιπο." Με άλλα λόγια, στην αρθρωτή αριθμητική, όταν φτάσει σε μια ορισμένη τιμή, η οποία ονομάζεται μονάδα μέτρησης, οι αριθμοί «γυρίζουν» ξανά στο μηδέν. Για παράδειγμα, ένα ρολόι κρατά την ώρα με συντελεστή 12: δείχνει 10, 11 και 12 η ώρα και μετά επιστρέφει στο 1.

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

Μάθετε για τις παγίδες του Μικρού Θεωρήματος του Φερμά.Όλοι οι αριθμοί για τους οποίους δεν πληρούνται οι προϋποθέσεις δοκιμής είναι σύνθετοι, αλλά οι υπόλοιποι αριθμοί είναι μόνο πιθανώςταξινομούνται ως απλές. Αν θέλετε να αποφύγετε λανθασμένα αποτελέσματα, ψάξτε για nστη λίστα των "αριθμών Carmichael" (σύνθετοι αριθμοί που ικανοποιούν αυτήν τη δοκιμή) και "ψευδοπρώτων αριθμών Fermat" (αυτοί οι αριθμοί πληρούν τις συνθήκες δοκιμής μόνο για ορισμένες τιμές ένα).

Εάν βολεύει, χρησιμοποιήστε τη δοκιμή Miller-Rabin.Αν και αυτή τη μέθοδοαρκετά δυσκίνητος κατά τον χειροκίνητο υπολογισμό, χρησιμοποιείται συχνά σε προγράμματα υπολογιστή. Παρέχει αποδεκτή ταχύτητα και παράγει λιγότερα σφάλματα από τη μέθοδο του Fermat. Ένας σύνθετος αριθμός δεν θα γίνει δεκτός ως πρώτος αριθμός εάν οι υπολογισμοί γίνονται για περισσότερες από το ¼ των τιμών ένα. Εάν επιλέξετε τυχαία διαφορετικές έννοιες ένακαι για όλα αυτά το τεστ θα δώσει θετικό αποτέλεσμα, μπορούμε να υποθέσουμε με αρκετά υψηλό βαθμό εμπιστοσύνης ότι nείναι πρώτος αριθμός.

Για μεγάλους αριθμούς, χρησιμοποιήστε αρθρωτή αριθμητική.Εάν δεν διαθέτετε αριθμομηχανή με λειτουργία mod ή η αριθμομηχανή δεν έχει σχεδιαστεί για λειτουργίες με τέτοια μεγάλοι αριθμοί, χρησιμοποιήστε ιδιότητες δυνάμεων και αρθρωτή αριθμητική για να διευκολύνετε τους υπολογισμούς. Παρακάτω είναι ένα παράδειγμα για 3 50 (\displaystyle 3^(50)) mod 50:

• Ξαναγράψτε την έκφραση σε μια πιο βολική μορφή: mod 50. Όταν κάνετε χειροκίνητους υπολογισμούς, ενδέχεται να απαιτούνται περαιτέρω απλοποιήσεις.
• (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Εδώ λάβαμε υπόψη την ιδιότητα του αρθρωτού πολλαπλασιασμού.
• 3 25 (\displaystyle 3^(25)) mod 50 = 43.
• (3 25 (\displaystyle (3^(25)) mod 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) mod 50.
• = 1849 (\displaystyle =1849) mod 50.
• = 49 (\displaystyle =49).