Πρώτοι αριθμοί

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

Επομένως το 0 και το 1 δεν είναι πρώτοι αριθμοί.

Ο αριθμός 2 είναι ο μόνος άρτιος πρώτος αριθμός ενώ όλοι οι άλλοι άρτιοι είναι σύνθετοι. Οι περιττοί άλλοτε είναι πρώτοι και άλλοτε σύνθετοι.

Οι πρώτοι αριθμοί είναι ένα από τα αντικείμενα της θεωρίας αριθμών. Διάσημες και άλυτες εικασίες, όπως η Υπόθεση του Ρίμαν και η Εικασία του Γκόλντμπαχ αφορούν πρώτους αριθμούς.

Το κόσκινο του Ερατοσθένη
Η πρόβλημα της εύρεσης πρώτων αριθμών απασχόλησε από τους αρχαίους χρόνους τους μαθηματικούς. Ένας απλός τρόπους για την εύρεση πρώτων αριθμών είναι το κόσκινο του Ερατοσθένη.

Στο σύνολο των φυσικών αριθμών διαγράφουμε πρώτα τα πολλαπλάσια του 2, μετά διαγράφουμε τα πολλαπλάσια του επόμενου μη διαγραμμένου αριθμού κ.λ.π. Οι αριθμοί που θα απομείνουν είναι όλοι πρώτοι.

Είναι προφανές ότι η παραπάνω διαδικασία δεν μπορεί να εφαρμοστεί σε όλο το σύνολο των φυσικών αριθμών, αλλά σε ένα υποσύνολο της μορφής {2,3,4,5, … ,ν} όπου ν οποιοσδήποτε φυσικός αριθμός.


Στην εικόνα μπορείτε να δείτε πως μπορούμε να βρούμε τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι από το 120 χρησιμοποιώντας το κόσκινο του Ερατοσθένη.

Ιδιότητες πρώτων αριθμών

  • Οι πρώτοι αριθμοί έχουν άπειρο πλήθος.
  • Αν ένας αριθμός ν δεν έχει διαιρέτες μικρότερους ή ίσους από την τετραγωνική του ρίζα, τότε είναι πρώτος.
  • Όλοι οι πρώτοι αριθμοί στο δεκαδικό σύστημα, εκτός του 2 και του 5, έχουν ως τελευταίο ψηφίο κάποιο από τα 1, 3, 7 ή 9 (διότι οι αριθμοί που τελειώνουν σε 0, 2, 4, 6 και 8 είναι πολλαπλάσια του 2 ενώ οι αριθμοί που τελειώνουν σε 0 ή 5 είναι πολλαπλάσια του 5).
  • Αν ο p είναι πρώτος και διαιρεί το γινόμενο αβ για κάποιους ακέραιους α και β, τότε ο p διαιρεί το α ή το β. (Ευκλείδης)
  • Αν p πρώτος και α ακέραιος, τότε το αp−α διαιρείται από το p. (Μικρό Θεώρημα του Φερμά)
  • Ένας ακέραιος p>1 είναι πρώτος αν και μόνο αν (p−1)!+1 διαιρείται από το p. (Θεώρημα του Ουίλσον)

Εφαρμογή

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

Αρκετοί αλγόριθμοι κρυπτογράφησης δημόσιου κλειδιού, όπως ο RSA και το πρωτόκολλο ανταλλαγής κλειδιών των Ντίφι-Χέλμαν, βασίζονται στους μεγάλους πρώτους αριθμούς (για παράδειγμα πρώτοι αριθμοί μεγέθους 512 bit χρησιμοποιούνται συχνά για τον RSA και πρώτοι αριθμοί μεγέθους 1024 bit είναι συνήθεις για τον αλγόριθμο Ντίφι–Χέλμαν.). Ο RSA βασίζεται στην υπόθεση ότι είναι πολύ πιο εύκολο (δηλαδή πιο αποτελεσματικό) να εκτελέσουμε πολλαπλασιασμό δύο (μεγάλων) αριθμών x και y από το να υπολογίσουμε τους x και y (υποτίθεται ότι είναι σχετικά πρώτοι) αν μόνο το γινόμενο xy είναι γνωστό.

Ένα σχόλιο σχετικά με το “Πρώτοι αριθμοί”

  1. Θα αφήσω εδω μερικούς αύθονους ή υπερτέλειου αριθμούς

    Στη θεωρία των αριθμών, υπερτέλειος αριθμός (abundant number‎) είναι ένας αριθμός που είναι μικρότερος από το άθροισμα των κατάλληλων διαιρετών του. Ο ακέραιος αριθμός 12 είναι ο πρώτος άφθονος αριθμός. Οι κατάλληλοι διαιρέτες του είναι 1, 2, 3, 4 και 6 για σύνολο 16

    81081
    153153
    171171
    189189
    207207
    223839
    243243
    261261
    279279
    297297
    351351
    459459
    513513
    567567
    621621
    671517
    729729
    742203
    783783
    793611
    812889
    837837
    891891
    908523
    960687
    999999
    1024947
    1054053
    1072071
    1073709
    1095633
    1108107
    1145529
    1162161
    1198197
    1224531
    1270269
    1307691
    1324323
    1378377
    1432431
    1449063
    1450449
    1519749
    1540539
    1566873
    1594593
    1648647
    1684683
    1702701
    1810809
    1828827
    1851759
    1864863
    1882881
    1896741
    1918917
    1954953
    1972971
    1990989
    2014551
    2081079
    2119887
    2135133
    2189187
    2225223
    2226609
    2243241
    2279277
    2333331
    2351349
    2380833
    2391543
    2405403
    2438667
    2459457
    2462229
    2488563
    2513511
    2556477
    2585583
    2603601
    2621619
    2675673
    2693691
    2711709
    2721411
    2725569
    2729727
    2783781
    2873871
    2882061
    2891889
    2909907
    2945943
    2963961
    2980593
    2999997
    3054051
    3072069
    3074841
    3162159
    3216213
    3221127
    3252249
    3270267
    3286899
    3324321
    3342339
    3396393
    3432429
    3436587
    3486483
    3522519
    3540537
    3594591
    3630627
    3633903
    3666663
    3673593
    3702699
    3720717
    3756753
    3805263
    3810807
    3846843
    3864861
    3884517
    3923073
    3936933
    3972969
    4027023
    4061421
    4063059
    4081077
    4135131
    4160079
    4225221
    4243239
    4252941
    4297293
    4333329
    4347189
    4351347
    4384611
    4405401
    4441437
    4446981
    4477473
    4513509
    4559247
    4567563
    4603599
    4621617
    4675671
    4700619
    4747743
    4765761
    4783779
    4837833
    4858623
    4891887
    4945941
    4963959
    4983363
    5054049
    5095629
    5108103
    5148297
    5195421
    5306301
    5432427
    5486481
    5555277
    5569641
    5594589
    5619537
    5648643
    5666661
    5690223
    5756751
    5806647
    5864859
    5918913
    5972967
    6009003
    6043653
    6084351
    6243237
    6255711
    6279273
    6333327
    6359661
    6405399
    6423417
    6467769
    6491331
    6567561
    6585579
    6675669
    6679827
    6724809
    6729723
    6789783
    6837831
    6939009
    6999993
    7018011
    7054047
    7103943
    7142499
    7174629
    7198191
    7216209
    7316001
    7360353
    7378371
    7386687
    7465689
    7504497
    7515963
    7540533
    7576569
    7666659
    7669431
    7671573
    7756749
    7810803
    7857927
    7864857
    8018703
    8027019
    8045037
    8081073
    8099091
    8117109
    8135127
    8164233
    8176707
    8189181
    8200647
    8219211
    8282043
    8351343
    8387379
    8399853
    8479107
    8495487
    8571717
    8621613
    8646183
    8657649
    8675667
    8729721
    8782389
    8837829
    8891883
    8909901
    8941779
    8999991
    9036027
    9063873
    9072063
    9124731
    9153837
    9162153
    9177399
    9186177
    9216207
    9224523
    9270261
    9286641
    9342333
    9388071
    9476649
    9486477
    9625077
    9648639
    9663381
    9666657
    9706851
    9738729
    9756747
    9787869
    9810801
    9828567
    9860697
    9927099
    9972963
    9993753

Γράψτε απάντηση στο fivos Ακύρωση απάντησης

Η ηλ. διεύθυνση σας δεν δημοσιεύεται.