Πρώτος αριθμός

φυσικός αριθμός με την ιδιότητα οι μόνοι φυσικοί διαιρέτες του να είναι η μονάδα και ο εαυτός του
(Ανακατεύθυνση από Πρώτοι αριθμοί)

Στα μαθηματικά πρώτος αριθμός (ή απλά πρώτος) είναι ένας φυσικός αριθμός με την ιδιότητα οι μόνοι φυσικοί διαιρέτες του να είναι η μονάδα και ο εαυτός του. Ένας φυσικός αριθμός, ο οποίος δεν είναι πρώτος αριθμός ονομάζεται σύνθετος αριθμός. Για παράδειγμα, ο αριθμός 5 είναι πρώτος, επειδή οι μόνοι τελειοι διαιρέτες του είναι το 1 και το 5, ενώ το 6 είναι σύνθετος επειδή έχει διαιρέτες του το 2 και 3 εκτός των 1 και 6. Το μηδέν και το ένα δεν θεωρούνται πρώτοι αριθμοί.

Η ακολουθία των 25 πρώτων αριθμών είναι η εξής

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, ...

Ο αριθμός 2 είναι ο μόνος άρτιος (ζυγός) πρώτος αριθμός. Όλοι οι άλλοι πρώτοι είναι περιττοί (μονοί).

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

Μια απλή αλλά αργή μέθοδος για να επαληθευτεί αν ένας δοθείς αριθμός n είναι πρώτος είναι η λεγόμενη δοκιμαστική διαίρεση. Η δοκιμαστική διαίρεση συνίσταται στον έλεγχο αν ο n είναι πολλαπλάσιο κάποιου ακέραιου αριθμού μεταξύ του 2 και του √n. Οι αλγόριθμοι που είναι πολύ πιο αποτελεσματικοί από τη δοκιμαστική διαίρεση έχουν επινοηθεί για να ελέγχουμε αν μεγαλύτεροι αριθμοί είναι πρώτοι. Ιδιαίτερα γρήγορες μέθοδοι είναι διαθέσιμες για αριθμούς ειδικών μορφών, όπως είναι αριθμοί Μερσέν. Ο γνωστός πρώτος αριθμός από τον Δεκέμβριο του 2018 είναι ο M82589933 με 24.862.048 ψηφία.

Υπάρχουν άπειροι σε πλήθος πρώτοι αριθμοί, όπως απέδειξε ο Ευκλείδης περίπου στο 300 π.Χ. Δεν υπάρχει κανένας γνωστός τύπος ο οποίος να διαχωρίζει όλους τους πρώτους αριθμούς από τους σύνθετους. Ωστόσο, η κατανομή των πρώτων αριθμών, όπως λέμε τη στατιστική συμπεριφορά των πρώτων γενικά, μπορεί να μοντελοποιηθεί. Το πρώτο αποτέλεσμα προς αυτή την κατεύθυνση είναι το θεώρημα πρώτων αριθμών, το οποίο αποδείχτηκε στα τέλη του 19ου αιώνα, το οποίο λέει ότι η πιθανότητα ενός τυχαία επιλεγμένου αριθμού n να είναι πρώτος είναι αντιστρόφως ανάλογη του πλήθους των ψηφίων ή του λογαρίθμου του n.

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

Ορισμός και παραδείγματα Επεξεργασία

Ένας φυσικός αριθμός (όπως 1, 2, 3, 4, 5, κ.ο.κ.) ονομάζεται πρώτος ή πρώτος αριθμός αν έχει ακριβώς δύο θετικούς διαιρέτες, το 1 και τον εαυτό του. Οι φυσικοί αριθμοί μεγαλύτεροι της μονάδας που δεν είναι πρώτοι ονομάζονται σύνθετοι. Ο ορισμός των πρώτων αριθμών γενικεύεται και στους ακέραιους: ένας ακέραιος αριθμός p, διάφορος του μηδενός και των ±1, που έχει ως διαιρέτες μόνο τους ±1 και ±p, καλείται πρώτος. Οι αριθμοί π.χ. 2, 3, 5 είναι πρώτοι, όπως και οι -2, -3, -5.

 
Ο αριθμός 12 δεν είναι πρώτος, καθώς 12 αντικείμενα μπορούν να τοποθετηθούν σε 3 ισομεγέθεις στήλες με 4 αντικείμενα η καθεμία (μεταξύ άλλων τρόπων). 11 αντικείμενα δεν μπορούν να τοποθετηθούν σε αρκετές ισομεγέθεις στήλες με παραπάνω από ένα αντικείμενο σε καθεμία χωρίς να περισσεύουν κάποια παραπάνω αντικείμενα (υπόλοιπο). Επομένως, ο αριθμός 11 είναι πρώτος.

Μεταξύ των αριθμών 1 και 6, οι αριθμοί 2, 3 και 5 είναι πρώτοι, ενώ οι αριθμοί 1, 4 και 6 δεν είναι πρώτοι. Ο 1 εξαιρείται από τους πρώτους αριθμούς για τους λόγους που εξηγούνται παρακάτω. Ο 2 είναι πρώτος αριθμός, διότι οι μόνοι φυσικοί αριθμοί που τον διαιρούν είναι οι 1 και 2. Στη συνέχεια, ο 3 είναι πρώτος επίσης επειδή οι 1 και 3 διαιρούν τον 3 χωρίς υπόλοιπο, αλλά ο 3 διαιρείται από το 2 με υπόλοιπο 1. Έτσι, ο 3 είναι πρώτος. Ωστόσο, ο 4 είναι σύνθετος, αφού ο 2 είναι ένας άλλος αριθμός (εκτός των 1 και 4) που διαιρεί τον 4 χωρίς υπόλοιπο:

 .

Ο 5 είναι επίσης πρώτος, επειδή κανένας από τους αριθμούς 2, 3, 4 δε διαιρεί τον 5. Στη συνέχεια, ο 6 διαιρείται από τους 2 και 3, αφού

 .

Άρα, ο 6 δεν είναι πρώτος. Η εικόνα στα δεξιά απεικονίζει ότι ο 12 δεν είναι πρώτος: 12 = 3 · 4. Κανένας άρτιος αριθμός μεγαλύτερος του 2 δεν είναι πρώτος, επειδή εξ ορισμού κάθε τέτοιος αριθμός n έχει τουλάχιστον τρεις διαφορετικούς διαιρέτες, τους 1, 2 και n. Αυτό συνεπάγεται ότι ο n δεν είναι πρώτος. Επομένως, ο όρος περιττός πρώτος αναφέρεται σε κάθε πρώτο αριθμό μεγαλύτερο του 2. Ανάλογα, όλοι οι πρώτοι μεγαλύτεροι του 5, γραμμένοι στο σύνηθες δεκαδικό σύστημα, τελειώνουν σε 1, 3, 7 ή 9, αφού οι άρτιοι αριθμοί είναι πολλαπλάσια του 2 και οι αριθμοί που τελειώνουν σε 0 ή 5 είναι πολλαπλάσια του 5.

Αν ο n είναι ένας φυσικός αριθμός, τότε οι αριθμοί 1 και n τον διαιρούν χωρίς υπόλοιπο. Συνεπώς, η προϋπόθεση ένας αριθμός να είναι πρώτος μπορεί να επαναδιατυπωθεί ως εξής: ένας αριθμός είναι πρώτος αν είναι του 1 και αν κανείς από τους

 

δε διαιρεί τον n (χωρίς υπόλοιπο). Επιπλέον, ένας άλλος τρόπος να πούμε το ίδιο είναι: ένας αριθμός n > 1 είναι πρώτος αν δε μπορεί να γραφεί ως γινόμενο δύο ακεραίων α και b, όπου α και b είναι μεγαλύτεροι του 1:

 .

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

Οι μικρότεροι 168 πρώτοι αριθμοί (όλοι οι πρώτοι αριθμοί μικρότεροι του 1000) είναι όπως παρακάτω με γαλανή επισήμανση κατά την διάταξη σπείρας Ούλαμ (με πράσινο χρώμα στο υπόβαθρο οι αριθμοί με μόνο 3 διαιρέτες, και με κόκκινο με μεγάλο αριθμό διαιρετών, περιλαμβάνονται και οι 13 πρώτοι αριθμοί από το 1000 έως το 1088):

1024 1023 1022 1021 1020 1019 1018 1017 1016 1015 1014 1013 1012 1011 1010 1009 1008 1007 1006 1005 1004 1003 1002 1001 1000 999 998 997 996 995 994 993 992
1025 900 899 898 897 896 895 894 893 892 891 890 889 888 887 886 885 884 883 882 881 880 879 878 877 876 875 874 873 872 871 870 991
1026 901 784 783 782 781 780 779 778 777 776 775 774 773 772 771 770 769 768 767 766 765 764 763 762 761 760 759 758 757 756 869 990
1027 902 785 676 675 674 673 672 671 670 669 668 667 666 665 664 663 662 661 660 659 658 657 656 655 654 653 652 651 650 755 868 989
1028 903 786 677 576 575 574 573 572 571 570 569 568 567 566 565 564 563 562 561 560 559 558 557 556 555 554 553 552 649 754 867 988
1029 904 787 678 577 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 551 648 753 866 987
1030 905 788 679 578 485 400 399 398 397 396 395 394 393 392 391 390 389 388 387 386 385 384 383 382 381 380 461 550 647 752 865 986
1031 906 789 680 579 486 401 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307 306 379 460 549 646 751 864 985
1032 907 790 681 580 487 402 325 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 305 378 459 548 645 750 863 984
1033 908 791 682 581 488 403 326 257 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 239 304 377 458 547 644 749 862 983
1034 909 792 683 582 489 404 327 258 197 144 143 142 141 140 139 138 137 136 135 134 133 132 181 238 303 376 457 546 643 748 861 982
1035 910 793 684 583 490 405 328 259 198 145 100 99 98 97 96 95 94 93 92 91 90 131 180 237 302 375 456 545 642 747 860 981
1036 911 794 685 584 491 406 329 260 199 146 101 64 63 62 61 60 59 58 57 56 89 130 179 236 301 374 455 544 641 746 859 980
1037 912 795 686 585 492 407 330 261 200 147 102 65 36 35 34 33 32 31 30 55 88 129 178 235 300 373 454 543 640 745 858 979
1038 913 796 687 586 493 408 331 262 201 148 103 66 37 16 15 14 13 12 29 54 87 128 177 234 299 372 453 542 639 744 857 978
1039 914 797 688 587 494 409 332 263 202 149 104 67 38 17 4 3 2 11 28 53 86 127 176 233 298 371 452 541 638 743 856 977
1040 915 798 689 588 495 410 333 264 203 150 105 68 39 18 5 0 1 10 27 52 85 126 175 232 297 370 451 540 637 742 855 976
1041 916 799 690 589 496 411 334 265 204 151 106 69 40 19 6 7 8 9 26 51 84 125 174 231 296 369 450 539 636 741 854 975
1042 917 800 691 590 497 412 335 266 205 152 107 70 41 20 21 22 23 24 25 50 83 124 173 230 295 368 449 538 635 740 853 974
1043 918 801 692 591 498 413 336 267 206 153 108 71 42 43 44 45 46 47 48 49 82 123 172 229 294 367 448 537 634 739 852 973
1044 919 802 693 592 499 414 337 268 207 154 109 72 73 74 75 76 77 78 79 80 81 122 171 228 293 366 447 536 633 738 851 972
1045 920 803 694 593 500 415 338 269 208 155 110 111 112 113 114 115 116 117 118 119 120 121 170 227 292 365 446 535 632 737 850 971
1046 921 804 695 594 501 416 339 270 209 156 157 158 159 160 161 162 163 164 165 166 167 168 169 226 291 364 445 534 631 736 849 970
1047 922 805 696 595 502 417 340 271 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 290 363 444 533 630 735 848 969
1048 923 806 697 596 503 418 341 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 362 443 532 629 734 847 968
1049 924 807 698 597 504 419 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 442 531 628 733 846 967
1050 925 808 699 598 505 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 530 627 732 845 966
1051 926 809 700 599 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 626 731 844 965
1052 927 810 701 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 730 843 964
1053 928 811 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 842 963
1054 929 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 962
1055 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961
1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088

Το σύνολο όλων των πρώτων αριθμών συνήθως συμβολίζεται με P.

Θεμελιώδες θεώρημα της αριθμητικής Επεξεργασία

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

23244 = 2 · 2 · 3 · 13 · 149 = 22 · 3 · 13 · 149. (22 συμβολίζει το τετράγωνο ή τη δεύτερη δύναμη του 2.)

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

n = p1 · p2 · ... · pt

ενός αριθμού n σε (πεπερασμένου πλήθους) πρώτους παράγοντες p1, p2, ..., pt ονομάζεται παραγοντοποίηση του n σε πρώτους παράγοντες. Το θεμελιώδες θεώρημα της αριθμητικής μπορεί να επαναδιατυπωθεί έτσι, ώστε να λέει ότι κάθε παραγοντοποίηση σε πρώτους αριθμούς θα είναι πανομοιότυπη εκτός από τη σειρά διάταξης των παραγόντων. Έτσι, μολονότι υπάρχουν πολλοί αλγόριθμοι παραγοντοποίησης με παράγοντες πρώτους αριθμούς για να το κάνουμε αυτό στην πράξη για μεγαλύτερους αριθμούς, στο τέλος όλοι οι αλγόριθμοι θα αποδίδουν το ίδιο αποτέλεσμα.

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

Ο αριθμός 1 δεν είναι πρώτος

Οι αρχαίοι Έλληνες δε θεωρούσαν τον 1 ούτε ως αριθμό κι έτσι δε τον θεωρούσαν ούτε ως πρώτο. Ωστόσο, στο 19ο αιώνα πολλοί μαθηματικοί θεωρούσαν τον 1 ως πρώτο αριθμό. Για παράδειγμα, η λίστα του Ντέρικ Νόρμαν Λέμερ που περιείχε πρώτους αριθμούς ως το 10,006,721 και εκδόθηκε μέχρι και το 1956, άρχιζε με τον 1 ως πρώτο αριθμό. Λέγεται ότι ο Ανρί Λεμπέσγκ είναι ο τελευταίος επαγγελματίας μαθηματικός που θεωρεί τον 1 ως πρώτο αριθμό. Παρόλο που ένα μεγάλο τμήμα των μαθηματικών είναι σωστό με τη θεωρία του 1 ως πρώτου αριθμού, το παραπάνω θεμελιώδες θεώρημα της αριθμητικής δε στέκει όπως είναι διατυπωμένο. Για παράδειγμα, ο αριθμός 15 μπορεί να παραγοντοποιηθεί ως 3 · 5 ή 1 · 3 · 5. Αν ο 1 ήταν πρώτος, τότε αυτές οι δύο εκφράσεις θα παρίσταναν διαφορετικές παραγοντοποιήσεις του 15 σε πρώτους αριθμούς κι έτσι το θεώρημα θα έπρεπε να τροποποιηθεί. Επιπρόσθετα, οι πρώτοι αριθμοί έχουν αρκετές ιδιότητες, τις οποίες ο αριθμός 1 δεν έχει, όπως τη σχέση του αριθμού με την αντίστοιχη τιμή του στη συνάρτηση του Όιλερ ή στη συνάρτηση του αθροίσματος των διαιρετών.

Ιστορία Επεξεργασία

Υπάρχουν ενδείξεις σε διασωθείσες επιγραφές των αρχαίων Αιγυπτίων ότι είχαν κάποια γνώση πρώτων αριθμών: οι επεκτάσεις του αιγυπτιακού κλάσματος στον πάπυρο του Ριντ, για παράδειγμα, έχουν αρκετά διαφορετικούς τύπους για πρώτους και για σύνθετους αριθμούς. Ωστόσο, οι πιο πρώιμες διασωθείσες επιγραφές σαφούς μελέτης των πρώτων αριθμών προέρχονται από τους αρχαίους Έλληνες. Τα στοιχεία του Ευκλείδη (περίπου στο 300 π.Χ.) περιέχουν σημαντικά θεωρήματα για τους πρώτους αριθμούς, συμπεριλαμβανομένων της απειρίας των πρώτων αριθμών και του θεμελιώδους θεωρήματος της αριθμητικής. Ο Ευκλείδης επίσης απέδειξε πώς μπορούμε να κατασκευάσουμε έναν τέλειο αριθμό από ένα πρώτο Μερσέν αριθμό. Το κόσκινο του Ερατοσθένη, το οποίο αποδίδεται στον Ερατοσθένη, είναι μια απλή μέθοδος να υπολογίσουμε τους πρώτους, παρόλο που οι μεγάλοι πρώτοι δεν υπολογίζονται σήμερα με τους υπολογιστές με αυτό τον τρόπο.

Μετά τους Έλληνες, λίγα πράγματα συνέβησαν με την έρευνα των πρώτων αριθμών μέχρι τον 17ο αιώνα. Το 1640 ο Πιέρ ντε Φερμά διατύπωσε (χωρίς απόδειξη) το μικρό θεώρημα του Φερμά (αργότερα αποδείχθηκε από τους Λάιμπνιτς και Όιλερ). Ο Φερμά υπέθεσε ότι όλοι οι αριθμοί της μορφής 22n + 1 είναι πρώτοι (αυτοί οι αριθμοί ονομάζονται αριθμοί Φερμά) και το επαλήθευσε αυτό μέχρι και για n = 4 (ή 216 + 1). Αλλά ο αμέσως επόμενος αριθμός Φερμά 232 + 1 είναι σύνθετος (ένας από τους παράγοντες του που είναι πρώτος αριθμός είναι ο 641), όπως ανακάλυψε αργότερα ο Όιλερ και μάλιστα δεν υπάρχουν παραπάνω γνωστοί αριθμοί Φερμά, οι οποίοι είναι πρώτοι. Ο Γάλλος καλόγερος Μερσέν μελέτησε τους πρώτους αριθμούς της μορφής 2p - 1, όπου p είναι πρώτος. Αυτοί οι αριθμοί ονομάζονται πρώτοι αριθμοί Μερσέν προς τιμή του.

Το έργο του Όιλερ στη θεωρία αριθμών περιλαμβάνει πολλά συμπεράσματα για τους πρώτους αριθμούς. Ο Όιλερ απέδειξε ότι η άπειρη σειρά 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... αποκλίνει. Το 1747 έδειξε ότι οι άρτιοι τέλειοι αριθμοί είναι ακριβώς οι ακέραιοι της μορφής 2p-1(2p − 1), όπου ο δεύτερος παράγοντας είναι ένας πρώτος Μερσέν αριθμός.

Στις αρχές του 19ου αιώνα, οι Λεζάντρ και Γκάους ανεξάρτητα υπέθεσαν ότι καθώς το x τείνει στο άπειρο, το πλήθος των πρώτων αριθμών μέχρι και το x είναι ασύμπτωτο στο κλάσμα x/ln(x), όπου ln(x) είναι ο φυσικός λογάριθμος του x. Στις ιδέες του ο Ρίμαν για τη συνάρτηση ζήτα, τις οποίες εξέδωσε το 1859, σχεδίαζε ένα πρόγραμμα που θα οδηγούσε σε μια απόδειξη του θεωρήματος των πρώτων αριθμών. Αυτό το περίγραμμα ολοκληρώθηκε από τους Χάνταμαρντ και ντε λα Βαλέ Ποσίν, οι οποίοι ανεξάρτητα απέδειξαν το θεώρημα των πρώτων αριθμών το 1896.

Δε γίνεται να αποδείξουμε ότι ένας μεγάλος αριθμός είναι πρώτος με τη δοκιμαστική διαίρεση. Πολλοί μαθηματικοί έχουν εργαστεί στην εύρεση τεχνικών για να αποδειχτεί αν ένας μεγάλος αριθμός είναι πρώτος, αλλά συχνά αυτές οι τεχνικές περιορίζονται σε συγκεκριμένες μορφές αριθμών. Παραδείγματα τέτοιων τεχνικών είναι το τεστ του Πέπιν για τους αριθμούς Φερμά (1877), το θεώρημα του Προθ (γύρω στο 1878), ο έλεγχος των Λούκας-Λέμερ (1856) και το γενικευμένο τεστ πρώτων αριθμών του Λούκας. Πιο πρόσφατοι αλγόριθμοι, όπως οι APRT-CL, ECPP και AKS δουλεύουν για όλους τους αριθμούς, αλλά παραμένουν πολύ πιο αργοί.

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

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

Πλήθος πρώτων αριθμών Επεξεργασία

Υπάρχουν άπειροι το πλήθος πρώτοι αριθμοί. Ένας άλλος τρόπος για να πούμε το ίδιο είναι ότι η ακολουθία

2, 3, 5, 7, 11, 13, ...

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

Η απόδειξη του Ευκλείδη Επεξεργασία

Έστω ένα πεπερασμένο σύνολο S πρώτων αριθμών. Η ιδέα - κλειδί είναι να θεωρήσουμε το γινόμενο όλων αυτών των αριθμών συν ένα:

 

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

Κανένας από τους πρώτους αριθμούς οι οποίοι διαιρούν τον Ν δεν μπορεί να είναι στοιχείο του πεπερασμένου συνόλου S των πρώτων αριθμών με το οποίο ξεκινήσαμε, επειδή διαιρώντας τον Ν με οποιοδήποτε από αυτούς τους πρώτους αριθμούς αφήνει υπόλοιπο 1. Επομένως, οι πρώτοι από τους οποίους ο Ν διαιρείται είναι επιπλέον πρώτοι εκτός από αυτόν με τον οποίο ξεκινήσαμε. Έτσι κάθε πεπερασμένο σύνολο πρώτων αριθμών μπορεί να επεκταθεί σε ένα μεγαλύτερο πεπερασμένο σύνολο πρώτων αριθμών.

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

Η αναλυτική απόδειξη του Όιλερ Επεξεργασία

Στην απόδειξη του Όιλερ χρησιμοποιείται το άθροισμα των αντίστροφων των πρώτων αριθμών,

 

Αυτό το άθροισμα γίνεται μεγαλύτερο από κάθε πραγματικό αριθμό με την προϋπόθεση ότι ο p είναι αρκετά μεγάλος. Αυτό δείχνει ότι υπάρχουν απείρως πολλοί πρώτοι αριθμοί, αφού ειδάλλως αυτό το άθροισμα θα μεγάλωνε μόνο μέχρι να φτάσουμε στο μεγαλύτερο πρώτο αριθμό p. Η αύξηση του S(p) υπολογίζεται από το δεύτερο θεώρημα του Μερσέν. Σε σύγκριση με το παραπάνω άθροισμα, παρατηρούμε ότι το άθροισμα

 

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

 

είναι πεπερασμένο.

Αναγνώριση πρώτου αριθμού και παραγοντοποίηση ακεραίου Επεξεργασία

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

Δοκιμαστική διαίρεση Επεξεργασία

Η πιο βασική μέθοδος ελέγχου αν ένας ακέραιος αριθμός είναι πρώτος ονομάζεται δοκιμαστική διαίρεση. Αυτή η μέθοδος συνίσταται στη διαίρεση του n από κάθε ακέραιο m, ο οποίος είναι του 1 και μικρότερος ή ίσος της τετραγωνικής ρίζας του n. Αν το αποτέλεσμα οποιασδήποτε από αυτές τις διαιρέσεις είναι ακέραιος, τότε ο n δεν είναι πρώτος, ειδάλλως είναι πρώτος αριθμός. Πράγματι, αν n = αb είναι σύνθετος (με α και b ≠ 1), τότε ένας από τους παράγοντες α ή b απαραίτητα το πολύ ίσος με  . Για παράδειγμα, για n = 37 οι δοκιμαστικές διαιρέσεις είναι από τους m = 2, 3, 4, 5 και 6. Κανένας από αυτούς τους αριθμούς δε διαιρεί το 37, οπότε ο 37 είναι πρώτος. Αυτός ο τρόπος μπορεί να εφαρμοστεί πιο αποτελεσματικά αν μια ολοκληρωμένη λίστα πρώτων αριθμών μέχρι και   είναι γνωστή - μετά οι δοκιμαστικές διαιρέσεις χρειάζεται να γίνουν μόνο για εκείνους τους m που είναι πρώτοι. Για παράδειγμα, για να ελέγξουμε αν ο 37 είναι πρώτος, μόνο τρεις διαιρέσεις είναι απαραίτητες (m = 2, 3 και 5), αφού οι αριθμοί 4 και 6 είναι σύνθετοι.

Η απλή μέθοδος της δοκιμαστικής διαίρεσης γρήγορα γίνεται μη πρακτική για τον έλεγχο μεγάλων ακεραίων επειδή το πλήθος των πιθανών παραγόντων μεγαλώνει ραγδαία καθώς ο n αυξάνεται. Σύμφωνα με το θεώρημα των πρώτων αριθμών, το οποίο αναλύεται παρακάτω, το πλήθος των πρώτων αριθμών μικρότερων του   είναι της τάξης  . Για τον μικρότερο πρώτο μεγαλύτερο του 1020, το πλήθος των πρώτων που πρέπει να δοκιμαστούν είναι περίπου 455 εκατομμύρια. Πάρα πολλοί από αυτούς δεν χωράνε σε 32bit (1010 > 4*109 ≈ 232), αλλά ακόμα και αν χωρούσαν θα χρειαζόταν περίπου 4*455 = 910 εκατομμύρια bytes για την αποθήκευσή τους. Εναλλακτικά, χωρίς αποθήκευση πρώτων αριθμών, χρειάζονται περίπου 10 δισεκατομμύρια διαιρέσεις.

Κόσκινα Επεξεργασία

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

Αιτιοκρατική και πιθανοτική αναγνώριση πρώτου Επεξεργασία

Οι σύγχρονοι έλεγχοι για τους πρώτους αριθμούς διαιρούνται σε δύο κατηγορίες, τους πιθανοτικούς (ή Μόντε Κάρλο) και τους αιτιοκρατικούς (ντετερμινιστικούς) αλγορίθμους. Ο έλεγχος του Φερμά για τους πρώτους αριθμούς βασίζεται στο μικρό θεώρημα του Φερμά. Το θεώρημα αυτό λέει ότι για κάθε πρώτο αριθμό p και για κάθε ακέραιο α, ο οποίος δε διαιρείται από τον p, ο αριθμός ap − 1 − 1 διαιρείται από τον p. Έτσι, αν ο αριθμός an − 1 − 1 δε διαιρείται από τον n, τότε ο n δεν μπορεί να είναι πρώτος. Ωστόσο, το αντίστροφο δεν ισχύει. Οι σύνθετοι αριθμοί που περνάνε τον έλεγχο του Φερμά για κάποιο α, ονομάζονται ψευδοπρώτοι στη βάση α. Μάλιστα, υπάρχουν άπειροι σύνθετοι αριθμοί n, οι οποίοι περνούν τον έλεγχου του Φερμά για κάθε α σχετικά πρώτο με τον n (αριθμοί Καρμάικλ). Ο δημοφιλής αλγόριθμος Miller-Rabin χρησιμοποιεί μια παραλλαγή του ελέγχου του Φερμά και ελέγχοντας ένα πλήθος από τυχαία α, εγγυάται ότι ένας αριθμός που περνάει τον έλεγχο για κάθε α είναι πρώτος με μεγάλη στατιστική βεβαιότητα. Η στατιστική βεβαιότητα είναι ανάλογη του πλήθους των τυχαίων α που χρησιμοποιεί ο αλγόριθμος.

Οι αιτιοκρατικοί (ντετερμινιστικοί) αλγόριθμοι αναγνωρίζουν έναν αριθμό ως πρώτο αν και μόνον αν είναι πρώτος. Για πρακτικά μεγέθη, ο ποιο γρήγορος αλγόριθμος αυτής της κατηγορίας χρησιμοποιεί την απόδειξη της ελλειπτικής καμπύλης (ECPP) για να αναγνωρίσει ένα αριθμό ως πρώτο. Η χρονική πολυπλοκότητα του αλγορίθμου αυτού είναι κατά μέσον όρο πολυωνυμική, αλλά δεν είναι γνωστό αν αυτό συμβαίνει και στη χειρότερη περίπτωση. Ο αλγόριθμος AKS είναι μεγάλης θεωρητικής σημασίας καθώς αποδεικνύει ότι το πρόβλημα της αναγνώρισης πρώτου αριθμού έχει πολυωνυμική χρονική πολυπλοκότητα στη χειρότερη περίπτωση. Είναι όμως κατά πολύ αργότερος από τον ECCP για πρακτικά μεγέθη. Οι αιτιοκρατικές μέθοδοι είναι τυπικά πιο αργές από τις πιθανοτικές κι έτσι οι τελευταίες εφαρμόζονται πρώτες πριν χρησιμοποιηθούν οι πιο χρονοβόρες αιτιοκρατικές μέθοδοι.

Ειδικοί αλγόριθμοι και ο γνωστός πρώτος αριθμός Επεξεργασία

 
Κατασκευή ενός κανονικού πενταγώνου. Ο 5 είναι ένας πρώτος αριθμός Φερμά.

Εκτός από τις παραπάνω δοκιμές για τους πρώτους αριθμούς για κάθε φυσικό αριθμό n, ένα πλήθος πολύ περισσότερο αποτελεσματικών μεθόδων για πρώτους αριθμούς είναι διαθέσιμο για συγκεκριμένους αριθμούς. Για παράδειγμα, για να εκτελεστεί η μέθοδος του Lucas για τους πρώτους απαιτείται η γνώση των παραγόντων που είναι πρώτοι αριθμοί του αριθμού n - 1, ενώ η μέθοδος των Λούκας-Λέμερ για τους πρώτους αριθμούς απαιτεί τους παράγοντες που είναι πρώτοι αριθμοί του αριθμού n + 1 ως δεδομένο. Για παράδειγμα, αυτές οι μέθοδοι μπορούν να εφαρμοστούν για να ελέγξουμε αν οι αριθμοί

n! ± 1 = 1 · 2 · 3 · ... · n ± 1

είναι πρώτοι. Οι πρώτοι αριθμοί αυτής της μορφής είναι γνωστοί ως παραγοντικοί πρώτοι αριθμοί. Άλλοι πρώτοι αριθμοί, όπου είτε ο p + 1 ή ο p - 1 είναι μιας συγκεκριμένης μορφής περιλαμβάνουν τους πρώτους αριθμούς Σόφι Ζερμέν (πρώτοι αριθμοί της μορφής 2p + 1, όπου p είναι πρώτος), τους αρχέγονους πρώτους αριθμούς, τους πρώτους αριθμούς του Φερμά και τους πρώτους αριθμούς του Μερσέν, οι οποίοι είναι πρώτοι αριθμοί της μορφής 2p - 1, όπου p είναι ένας τυχαίος πρώτος αριθμός. Η μέθοδος των Λούκας-Λέμερ είναι εξαιρετικά γρήγορη για τους πρώτους αριθμούς της μορφής αυτής. Για το λόγο αυτό ο γνωστός πρώτος αριθμός έχει γίνει σχεδόν ένας πρώτος Μερσέν από τότε που ανακαλύφθηκαν οι υπολογιστές.

Οι πρώτοι αριθμοί Φερμά είναι της μορφής

Fk = 22k + 1,

όπου k είναι ένας τυχαίος φυσικός αριθμός. Έτσι ονομάστηκαν οι αριθμοί αυτής της μορφής, αφού ο Πιέρ ντε Φερμά υπέθεσε ότι όλοι οι Fk είναι πρώτοι. Η πρόταση αυτή βασίστηκε στο γεγονός ότι οι οι πέντε πρώτοι τέτοιοι αριθμοί 3, 5, 17, 257 και 65,537 είναι πρώτοι. Ωστόσο, ο F5=4294967297=641×6700417 είναι σύνθετος και το ίδιο συμβαίνει για τους υπόλοιπους αριθμούς Φερμά, οι οποίοι έχουν ελεγχθεί από το 2011. Ένα κανονικό n-γώνιο είναι κατασκευάσιμο χρησιμοποιώντας χάρακα και διαβήτη αν και μόνο αν

n = 2i · m,

όπου m είναι ένας οποιοσδήποτε αριθμός από τους πρώτους Φερμά αριθμούς και i είναι ένας οποιοσδήποτε φυσικός αριθμός ή το μηδέν.

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

Τύπος Πρώτος αριθμός Πλήθος δεκαδικών ψηφίων Ημερομηνία Ανακαλύφθηκε από
πρώτος Μερσέν 282.589.933 − 1 24.862.048 Δεκέμβριος 2018 Great Internet Mersenne Prime Search
όχι πρώτος Μερσέν (αριθμός Προθ)   ψηφίων.[1] 9.383.761 6 Νοεμβρίου 2016 Seventeen or Bust
παραγοντικός πρώτος 150209! + 1 712,355 Οκτώβριος 2011 PrimeGrid[2]
αρχέγονος πρώτος 1098133# - 1 476,311 Μάρτιος 2012 PrimeGrid[3]
δίδυμοι πρώτοι αριθμοί 2.996.863.034.895 * 21290000 ± 1[4] .[5] 388.342 Σεπτέμβριος 2016 PrimeGrid[6]

Εύρεση πρώτων Επεξεργασία

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

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

 
Οπτικό κόσκινο Matiyasevich-Stechkin

Στις 14 Φεβρουαρίου 1999 οι Γιούρι Ματιγιάσεβιτς και Μπόρις Στέκιν δημοσίευσαν στο διαδίκτυο το οπτικό κόσκινο των πρώτων αριθμών. Τα σημεία της παραβολής   με ακέραιες συντεταγμένες ορίζουν χορδές που τέμνουν τον οριζόντιο άξονα x΄x σε σημεία της μορφής (αβ,0) όπου α,β ακέραιοι κι επομένως σαρώνουν όλους τους σύνθετους θετικούς ακέραιους.

Αλγόριθμοι εύρεσης πρώτων Επεξεργασία

Παρατίθενται μερικοί αλγόριθμοι (κατά σειρά ταχύτητας ή και απλότητας) για την εύρεση αν ο Ν>=2 είναι πρώτος. Η σειρά επίσης αυτών των αλγορίθμων είναι παιδευτική για την εισαγωγή σε μια σειρά από προγράμματα για ηλεκτρονικούς υπολογιστές.

Απλός 1 - από τον ορισμό του πρώτου αριθμού Επεξεργασία

  • Εξετάζουμε διαδοχικά όλους τους ακέραιους Μ < Ν
  • Μόλις βρεθεί διαιρέτης του Ν σταματάμε και ο Ν δεν είναι πρώτος
  • Αν εξαντληθούν οι Μ χωρίς να βρεθεί διαιρέτης, τότε ο Ν είναι πρώτος

Απλός 2 Επεξεργασία

Βασιζόμενοι στην παρατήρηση ότι κανένας αριθμός Ν δεν έχει διαιρέτη μεγαλύτερο του Ν/2, τροποποιούμε τον παραπάνω αλγόριθμο εξετάζοντας όλους τους αριθμούς Μ < Ν/2, διπλασιάζοντας έτσι την ταχύτητα σε σχέση με τον "Απλό 1".

Απλός 3 Επεξεργασία

Παρατηρούμε ότι αν ένας αριθμός Ν δεν είναι πρώτος τότε έχει (τουλάχιστον) δύο διαιρέτες μεγαλύτερους από 1. Σε αυτήν την περίπτωση τουλάχιστον ένας διαιρέτης είναι μικρότερος από την τετραγωνική ρίζα του αριθμού. Τροποποιούμε τον αλγόριθμο 2 εξετάζοντας όλους τους αριθμούς Μ που είναι μικρότεροι από την τετραγωνική ρίζα του N, αν η τελευταία δεν είναι ακέραιος. Αλλιώς ο αριθμός δεν είναι πρώτος, επειδή τον διαιρεί και η τετραγωνική του ρίζα.

Απλός 4 Επεξεργασία

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

 

αν δηλαδή το υπόλοιπο της διαίρεσης του Ν-1 παραγοντικό με το Ν, είναι ίσο με το υπόλοιπο της διαίρεσης του -1 με το N.

Η μέθοδος αυτή δεν εφαρμόζεται για μεγάλο Ν, αφού είναι δύσκολο να υπολογιστεί το παραγοντικό.

Ο μεγαλύτερος γνωστός πρώτος αριθμός Επεξεργασία

Τον Φεβρουάριο του 2024 ο μεγαλύτερος γνωστός πρώτος αριθμός ήταν ο 282589933 − 1, ο οποίος έχει 24.862.048 ψηφία. Βρέθηκε τον Δεκέμβριο του 2018 από το Great Internet Mersenne Prime Search (GIMPS).[7]

  (M82589933)

Δεύτερος είναι ο 277.232.917 − 1, ο οποίος έχει 23.249.425 ψηφία. Βρέθηκε τον Δεκέμβριο του 2017 από το Great Internet Mersenne Prime Search (GIMPS).[8]

  (M77232917)

Ο τρίτος πρώτος είναι ο:

  (M74207281), ο οποίος ανακαλύφθηκε μέσω του GIMPS τον Ιανουάριο του 2016 και έχει 22.338.618 ψηφία.

Ο τέταρτος πρώτος είναι ο :

 ) (M57885161)

και η ανακάλυψη του, έγινε στις 25 Ιανουαρίου 2013, μέσω του διαδικτυακού προγράμματος κατανεμημένης επεξεργασίας GIMPS (Great Internet Mersenne Prime Search).[9] Ο αριθμός αυτός έχει 17.425.179 ψηφία (ο δεύτερος με πάνω από 10 εκατομμύρια ψηφία) και έχει την πρόσθετη ιδιότητα να είναι ο 48ος Μερσέν πρώτος (Mersenne prime) που ανακαλύφθηκε. Ο 47ος Μερσέν πρώτος, ο 243,112,609 − 1, ανακαλύφθηκε στις 25 Αυγούστου του 2008.

Στο πρόσφατο παρελθόν, όλοι οι πρώτοι που ανακαλύφθηκαν ήταν Μερσέν πρώτοι.[10]

Επίσης, για τον πρώτο πρώτο αριθμό που ανακαλύφθηκε και είχε πάνω από 10.000.000 ψηφία, δόθηκαν 100.000 δολάρια.

Ιδιότητες πρώτων αριθμών Επεξεργασία

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

Κατανομή Επεξεργασία

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

Υπάρχουν αυθαίρετα μεγάλες ακολουθίες διαδοχικών μη πρώτων αριθμών, όπως για κάθε θετικό ακέραιο αριθμό n οι n διαδοχικοί ακέραιοι από (n + 1)! + 2 ως (n + 1)! + n + 1 (συμπεριλαμβανομένης και της τελικής τιμής) είναι όλοι σύνθετοι αριθμοί (αφού (n + 1)! + k διαιρείται από τον k για k από 2 ως n + 1).

Το θεώρημα του Ντίριχλετ για τις αριθμητικές προόδους, στη βασική του μορφή, ισχυρίζεται ότι τα γραμμικά πολυώνυμα

p(n) = α + bn

με τους σχετικά πρώτους α και b να παίρνουν άπειρα πολλές τιμές πρώτων αριθμών. Ισχυρότερες μορφές του θεωρήματος αναφέρουν ότι το άθροισμα των τιμών που επιστρέφει το πολυώνυμο αυτών των τιμών που είναι πρώτοι αριθμοί αποκλίνει και αυτές οι διαφορές που υπάρχουν στα πολυώνυμα με το ίδιο b έχουν περίπου τις ίδιες αναλογίες των πρώτων αριθμών.

Η αντίστοιχη ερώτηση για τα τετραγωνικά πολυώνυμα είναι λιγότερο κατανοητή.

Τύποι των πρώτων αριθμών Επεξεργασία

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

 

να είναι πρώτοι αριθμοί για κάθε φυσικό αριθμό n. Εδώ   αντιπροσωπεύει ακέραιο μέρος της έκφρασης, δηλαδή το μεγαλύτερο ακέραιο που δεν είναι από τον αριθμό που είναι στις αγκύλες. Ο τελευταίος τύπος μπορεί να αποδειχθεί χρησιμοποιώντας το αξίωμα του Μπέρτραντ (αποδεδειγμένο πρώτα από τον Παφνούτι Λβόβιτς Τσέμπισσιοφ), το οποίο αναφέρει ότι πάντα υπάρχει τουλάχιστον ένας πρώτος αριθμός p με n < p < 2n - 2, για κάθε φυσικό αριθμό n > 3. Ωστόσο, για να υπολογίσουμε τον Α ή τον μ απαιτείται η γνώση των απείρως πολλών πρώτων αριθμών με τους οποίους θα ξεκινήσουμε. Ένας άλλος τύπος βασίζεται στο θεώρημα του Ουίλσον και παράγει τον αριθμό 2 πολλές φορές και όλους τους άλλους πρώτους αριθμούς ακριβώς μία φορά.

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

Πλήθος των πρώτων αριθμών κάτω από ένα δοθέντα αριθμό Επεξεργασία

 
Ένα διάγραμμα που απεικονίζει την π(n) (μπλε), την n/ln(n) (πράσινη) και την Li(n) (κόκκινη)

Η συνάρτηση που καταμετράει τους πρώτους αριθμούς π(n) ορίζεται ως το πλήθος των πρώτων αριθμών μέχρι και τον n. Για παράδειγμα π(11) = 5, αφού υπάρχουν πέντε πρώτοι αριθμοί μικρότεροι ή ίσοι του 11. Υπάρχουν γνωστοί αλγόριθμοι για να υπολογίσουμε τις ακριβείς τιμές της συνάρτησης π(n) πιο γρήγορα από ότι να υπολογίζαμε αν κάθε αριθμός είναι πρώτος μέχρι και τον n. Το θεώρημα των πρώτων αριθμών αναφέρει ότι η π(n) δίνεται περίπου από τον τύπο

 ,

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

 

Το θεώρημα πρώτων αριθμών συνεπάγεται ότι υπολογίζει το μέγεθος του n-οστού πρώτου αριθμού pn (δηλαδή p1 = 2, p2 = 3, κ.ο.κ.) : μέχρι ένα οριοθετημένο παράγοντα, ο pn αυξάνεται όπως η nlog(n). Πιο συγκεκριμένα, τα κενά των πρώτων αριθμών,δηλαδή οι διαφορές pn - pn-1 των δύο διαδοχικών πρώτων αριθμών, γίνονται αυθαίρετα μεγάλες. Αυτή η τελευταία πρόταση μπορεί επίσης να διατυπωθεί με ένα πιο στοιχειώδη τρόπο σημειώνοντας ότι η ακολουθία n! + 2, n! + 3, …, n! + n αποτελείται από n - 1 σύνθετους αριθμούς, για κάθε φυσικό αριθμό n.

Αριθμητικές πρόοδοι Επεξεργασία

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

3, 12, 21, 30, 39, ...,

είναι μια αριθμητική πρόοδος μέτρου q = 9. Εκτός από το 3, κανείς από αυτούς τους αριθμούς δεν είναι πρώτος, αφού 3 + 9n = 3(1 + 3n), έτσι ώστε οι υπόλοιποι αριθμοί της προόδου αυτής είναι όλοι σύνθετοι. (Σε γενικές γραμμές, όλοι οι πρώτοι αριθμοί μεγαλύτεροι του q είναι της μορφής q# · n + m, όπου 0 < m < q# και ο m δεν έχει κανένα παράγοντα πρώτο αριθμό ≤ q.) Έτσι, η πρόοδος

α, α + q, α + 2q, α + 3q, ...

απείρως πολλούς πρώτους αριθμούς, μόνο όταν οι α και q είναι σχετικοί πρώτοι αριθμοί, δηλαδή ο μέγιστος κοινός τους διαιρέτης είναι το ένα. Αν ικανοποιείται αυτή η αναγκαία συνθήκη, τότε το θεώρημα του Ντίριχλετ για τις αριθμητικές προόδους ισχυρίζεται ότι η πρόοδος περιέχει απείρως πολλούς πρώτους αριθμούς. Η εικόνα παρακάτω απεικονίζει την πρόοδο με q = 9: οι αριθμοί είναι τυλιγμένοι γύρω μέχρι να περάσει ένα πολλαπλάσιο του 9. Οι πρώτοι αριθμοί είναι μαρκαρισμένοι με κόκκινο χρώμα. Οι σειρές(= πρόοδοι) που αρχίζουν με α = 3, 6 ή 9 περιέχουν το πολύ ένα πρώτο αριθμό. Σε όλες τις άλλες σειρές (α = 1, 2, 4, 5, 7 και 8) υπάρχουν απείρως πολλοί πρώτοι αριθμοί. Επιπλέον, οι πρώτοι αριθμοί κατανέμονται ισομερώς μεταξύ αυτών των σειρών σε όλη τη ροή - η πυκνότητα των πρώτων αριθμών με σύγκλιση α μέτρου 9 είναι 1/6.

 
Prime numbers (highlighted in red) in arithmetic progression modulo 9.

Το θεώρημα των Γκριν-Τάο δείχνει ότι υπάρχουν αυθαίρετα μεγάλες αριθμητικές πρόοδοι που περιέχουν πρώτους αριθμούς. Ένας περιττός πρώτος αριθμός p εκφράζεται ως το άθροισμα δύο τετραγώνων, p = x2 + y2, ακριβώς αν ο p συγκλίνει στο 1 με μέτρο 4.

Τιμές πρώτων αριθμών δευτεροβάθμιων πολυωνύμων Επεξεργασία

 
The Ulam spiral. Red pixels show prime numbers. Primes of the form 4n2 − 2n + 41 are highlighted in blue.

Ο Όιλερ σημείωσε ότι η συνάρτηση

n2 + n + 41

δίνει πρώτους αριθμούς για 0 ≤ n < 40, ένα γεγονός που οδηγεί βαθιά μέσα στην αλγεβρική θεωρία αριθμών και πιο συγκεκριμένα στους αριθμούς Χέεγκνερ. Για μεγαλύτερα n, η συνάρτηση δίνει σύνθετους αριθμούς. Η εικασία F των Χάρντι-Λίτλγουντ κάνει μια ασυμπτωτική πρόβλεψη για την πυκνότητα των πρώτων αριθμών μεταξύ των τιμών των δευτεροβάθμιων πολυωνύμων (με ακέραιους συντελεστές a, b και c)

 

Ωστόσο, η πρόοδος έχει αποδειχτεί δύσκολο να βρεθεί: κανένα δευτεροβάθμιο πολυώνυμο (με a ≠ 0) δεν είναι γνωστό να παίρνει απείρως πολλούς πρώτους αριθμούς ως τιμές. Η σπείρα του Ούλαμ απεικονίζει όλους τους φυσικούς αριθμούς με ένα σπειροειδές τρόπο. Οι πρώτοι αριθμοί μαζεύονται σε συγκεκριμένες διαγώνιες και όχι σε άλλες, γεγονός που υποδηλώνει ότι κάποια δευτεροβάθμια πολυώνυμα παίρνουν ως τιμές πρώτους αριθμούς πιο συχνά από άλλα.

Ανοικτά ερωτήματα Επεξεργασία

Η συνάρτηση ζήτα και η υπόθεση του Ρίμαν Επεξεργασία

 
Το σχέδιο της συνάρτησης ζήτα ζ(s). Στο s=1, η συνάρτηση έχει ένα πόλο, ο οποίος όπως λέμε τείνει στο άπειρο.

Η συνάρτηση ζήτα του Ρίμαν ζ(s) ορίζεται ως ένα άπειρο άθροισμα

 

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

 

Η συνάρτηση ζήτα είναι στενά συνδεδεμένη με τους πρώτους αριθμούς. Για παράδειγμα, το προαναφερθέν γεγονός ότι υπάρχουν άπειροι πρώτοι αριθμοί μπορεί επίσης να δειχθεί χρησιμοποιώντας τη συνάρτηση ζήτα: αν υπήρχαν πεπερασμένου του πλήθους πρώτοι αριθμοί, τότε η ζ(1) θα είχε μια πεπερασμένη τιμή. Ωστόσο, η αρμονική σειρά 1 + 1/2 + 1/3 + 1/4 + ... αποκλίνει (δηλαδή ξεπερνά κάθε δεδομένο αριθμό) κι έτσι πρέπει να υπάρχουν απείρως πολλοί πρώτοι αριθμοί. Ένα άλλο παράδειγμα της σημαντικότητας της συνάρτησης ζήτα και μια γεύση από τη σύγχρονη αλγεβρική θεωρία αριθμών είναι η παρακάτω ταυτότητα (πρόβλημα της Βασιλείας), σύμφωνα με τον Όιλερ,

 

Η τιμή της ζ(2), 6/π2, είναι η πιθανότητα δύο τυχαία επιλεγμένοι αριθμοί να είναι σχετικά πρώτοι.

Η χωρίς απόδειξη υπόθεση του Ρίμαν, από το 1859, αναφέρει ότι εκτός από τους s = -2, -4, ... όλα τα μηδενικά της ζήτα συνάρτησης έχουν πραγματικό μέρος ίσο με 1/2. Η σύνδεση στους πρώτους αριθμούς είναι αυτή που ουσιαστικά λέει ότι οι πρώτοι αριθμοί κατανέμονται όσο πιο τακτικά γίνεται. Από φυσική άποψη, η υπόθεση περίπου αναφέρει ότι η αταξία στην κατανομή των πρώτων αριθμών προέρχεται μόνο από τυχαίο θόρυβο. Από μαθηματική άποψη, η υπόθεση περίπου αναφέρει ότι η ασυμπτωτική κατανομή των πρώτων αριθμών (σχετικά με το ότι οι αριθμοί x/logx που είναι μικρότεροι από x είναι πρώτοι αριθμοί, θεώρημα πρώτων αριθμών) επίσης ισχύει για πολύ μικρότερα σε μήκος διαστήματα σχετικά με την τετραγωνική ρίζα του x (για διαστήματα κοντά στο x). Αυτή η υπόθεση θεωρείται γενικά ορθή. Πιο συγκεκριμένα, η απλούστερη υπόθεση είναι ότι οι πρώτοι αριθμοί δε θα έπρεπε να έχουν σημαντικές αταξίες χωρίς ένα καλό λόγο.

Άλλες εικασίες Επεξεργασία

Εκτός από την υπόθεση του Ρίμαν, πολλές ακόμη εικασίες σχετικά με τους πρώτους αριθμούς έχουν διατυπωθεί. Συχνά έχοντας μια στοιχειώδη σύνθεση, πολλές από αυτές τις εικασίες δεν έχουν απόδειξη για δεκαετίες: και τα τέσσερα προβλήματα του Λαντό παραμένουν άλυτα από το 1912. Ένα από αυτά είναι η εικασία του Γκόλντμπαχ, η οποία βεβαιώνει ότι κάθε άρτιος ακέραιος αριθμός n μεγαλύτερος του 2 μπορεί να γραφεί ως άθροισμα δύο πρώτων αριθμών. Από το Φεβρουάριο του 2011, αυτή η εικασία έχει επαληθευτεί για όλους τους αριθμούς μέχρι και n = 2 · 1017. Πιο απλές προτάσεις από αυτή έχουν αποδειχτεί, για παράδειγμα το θεώρημα του Βινογκραντόφ λέει ότι κάθε αρκετά μεγάλος περιττός ακέραιος αριθμός μπορεί να γραφεί ως άθροισμα τριών πρώτων αριθμών. Το θεώρημα του Κεν λέει ότι κάθε αρκετά μεγάλος άρτιος αριθμός μπορεί να γραφεί ως άθροισμα ενός πρώτου και ενός ημιπρώτου (= γινόμενο δύο πρώτων αριθμών) αριθμού. Επιπρόσθετα, κάθε άρτιος ακέραιος αριθμός μπορεί να γραφεί ως άθροισμα έξι πρώτων αριθμών. Το τμήμα της θεωρίας αριθμών που μελετά αυτές τις ερωτήσεις ονομάζεται πρόσθετη θεωρία αριθμών.

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

Ένας τρίτος τύπος εικασιών αφορά τις πτυχές της κατανομής των πρώτων αριθμών. Εικάζεται ότι υπάρχουν απείρως πολλοί δίδυμοι πρώτοι αριθμοί, ζευγάρια πρώτων αριθμών με διαφορά 2 (εικασία των διδύμων πρώτων αριθμών). Η εικασία του Πόλινακ ενισχύει την παραπάνω εικασία, καθώς αναφέρει ότι για κάθε θετικό ακέραιο αριθμό n, υπάρχουν απείρως πολλά ζευγάρια διαδοχικών πρώτων αριθμών με διαφορά 2n. Εικάζεται ότι υπάρχουν απείρως πολλοί πρώτοι αριθμοί της μορφής n2 + 1. Αυτές οι εικασίες είναι ειδικές περιπτώσεις της ευρείας υπόθεσης Η του Σίντσελ. Η εικασία του Μπρόκαρντ λέει ότι υπάρχουν πάντα τουλάχιστον τέσσερις πρώτοι αριθμοί μεταξύ των τετραγώνων δύο διαδοχικών πρώτων αριθμών μεγαλύτερων του 2. Η εικασία του Λεγκρέντ αναφέρει ότι υπάρχει ένας πρώτος αριθμός μεταξύ n2 και (n + 1)2 για κάθε θετικό ακέραιο αριθμό n. Υπονοείται από την ισχυρότερη εικασία του Κράμερ.

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

Οι εικασίες του Γκόλντμπαχ Επεξεργασία

Είναι πολύ γνωστή η πρώτη εικασία που διατύπωσε ο Κρίστιαν Γκόλντμπαχ 1690-1764, η οποία σχετίζεται με τους πρώτους αριθμούς. Ο Γκόλντμπαχ υποστήριξε ότι κάθε άρτιος αριθμός μεγαλύτερος του 2, μπορεί να γραφεί ως άθροισμα δύο πρώτων αριθμών. Η απόδειξη της παραπάνω εικασίας ταλανίζει ακόμα και σήμερα τους μαθηματικούς, καθώς παράλληλα οι υπολογιστές επιβεβαιώνουν την εικασία για όλο και μεγαλύτερους αριθμούς. Το 1998, η εικασία επιβεβαιώθηκε για αριθμούς μέχρις και της τάξης του  

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

Εφαρμογές Επεξεργασία

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

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

Ο Διεθνής Πρότυπος Αριθμός Βιβλίου δουλεύει με ένα ψηφίο ελέγχου, το οποίο εκμεταλλεύεται το γεγονός ότι ο αριθμός 11 είναι πρώτος αριθμός.

Αριθμητική modular ενός πρώτου αριθμού και πεπερασμένα σώματα

Η αριθμητική modular τροποποιεί τη συνήθη αριθμητική χρησιμοποιώντας μόνο τους αριθμούς

{0, 1, 2, ..., n - 1},

όπου ο n είναι ένας σταθερός φυσικός αριθμός που ονομάζεται modulus. ο υπολογισμός των αθροισμάτων, των διαφορών και των γινομένων γίνεται ως συνήθως, αλλά όποτε συναντούμε ένα αρνητικό αριθμό ή ένα αριθμό μεγαλύτερο του n - 1, αυτός αντικαθίσταται από το υπόλοιπο μετά τη διαίρεση από τον n. Για παράδειγμα, για n = 7, το άθροισμα 3 + 5 ισούται με 1 αντί για 8, αφού όταν το 8 διαιρείται με το 7 αφήνει υπόλοιπο 1. Για να αναφερθούμε σε αυτό, λέμε ότι το 3 + 5 είναι σύμφωνο με το 1 modulo 7 και γράφουμε

 

Ομοίως, 6 + 1 ≡ 0 (mod 7), 2 - 5 ≡ 4 (mod 7), αφού -3 + 7 = 4 και 3 · 4 ≡ 5 (mod 7), καθώς το 12 αφήνει υπόλοιπο το 5. Οι βασικές ιδιότητες της πρόσθεσης και του πολλαπλασιασμού γνωστές από τους ακεραίους ισχύουν και στην modular αριθμητική. Στον τομέα της αφηρημένης άλγεβρας, το παραπάνω σύνολο των ακεραίων, το οποίο συμβολίζεται με Z/nZ, είναι επομένως ένας αντιμεταθετικός δακτύλιος για κάθε n. Η διαίρεση όμως, δεν είναι γενικά δυνατή σε αυτή την κατάσταση. Για παράδειγμα, για n = 6, στην εξίσωση

 

μια λύση του x, η οποία θα ήταν ανάλογη με 2/3, δεν μπορεί να βρεθεί, καθώς το ένα μπορεί να βρεθεί υπολογίζοντας 3 · 0, ..., 3 · 5 modulo 6. Το ιδιαίτερο χαρακτηριστικό των πρώτων αριθμών είναι το εξής: η διαίρεση είναι δυνατή στη modular αριθμητική αν και μόνο αν ο n είναι πρώτος αριθμός. Ισοδύναμα, ο n είναι πρώτος αριθμός αν και μόνο αν όλοι οι ακέραιοι m που ικανοποιούν την ανισότητα 2 ≤ m ≤ n − 1 είναι σχετικοί πρώτοι με τον n, δηλαδή ο μόνος κοινός διαιρέτης τους είναι το 1. Πράγματι, για n = 7, η εξίσωση

 

έχει μοναδική λύση, τη x = 3. Εξαιτίας αυτού, για κάθε πρώτο αριθμό p, το Z/pZ (μερικές φορές σημειώνεται ως Fp) ονομάζεται σώμα ή πιο συγκεκριμένα πεπερασμένο σώμα, αφού περιέχει πεπερασμένου του πλήθους, δηλαδή p, στοιχεία. Ένα πλήθος θεωρημάτων μπορούν να προέρχονται από τη μελέτη του Fp με αυτό τον αφηρημένο τρόπο. Για παράδειγμα, το μικρό θεώρημα του Φερμά, το οποίο αναφέρει ότι

 

για κάθε ακέραιο αριθμό a που δε διαιρείται από τον p, μπορεί να αποδειχθεί χρησιμοποιώντας αυτές τις έννοιες. Αυτό συνεπάγεται ότι

 

Η εικασία του Τζιούγκα λέει ότι αυτή η εξίσωση είναι επίσης μια επαρκής συνθήκη για να πούμε ότι ο p είναι πρώτος αριθμός. Μια άλλη συνέπεια του μικρού θεωρήματος του Φερμά είναι η εξής: αν ο p είναι ένας πρώτος αριθμός διαφορετικός του 2 και του 5, ο 1/p είναι πάντα ένας περιοδικός αριθμός, με περίοδο p - 1 ή ένα διαιρέτη του p - 1. Το κλάσμα 1/p εκφρασμένο επίσης στη βάση q (αντί στη βάση 10) έχει παρόμοιο αποτέλεσμα, υπό τον όρο ο p δεν είναι παράγοντας του q ως πρώτος αριθμός. Το θεώρημα του Ουίλσον λέει ότι ένας ακέραιος αριθμός p > 1 είναι πρώτος αν και μόνο αν το παραγοντικό (p - 1)! + 1 διαιρείται από τον p. Επιπλέον, ένας ακέραιος αριθμός n > 4 είναι σύνθετος αν και μόνο αν (n - 1)! είναι διαιρέσιμο από τον n.

Άλλες μαθηματικές συμβολές των πρώτων αριθμών

Πολλά μαθηματικά πεδία χρησιμοποιούν πολύ τους πρώτους αριθμούς. Ένα παράδειγμα από τη θεωρία των πεπερασμένων σωμάτων είναι τα θεωρήματα του Sylow: αν G είναι ένα πεπερασμένο σώμα και pn είναι η μεγαλύτερη δύναμη του πρώτου αριθμού p που διαιρεί τη διάταξη G, τότε η G έχει μια υποομάδα τάξης pn. Επίσης, κάθε ομάδα με διάταξη πρώτων αριθμών είναι κυκλική (θεώρημα του Lagrange).

Κρυπτογράφηση δημόσιου κλειδιού

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

Οι πρώτοι αριθμοί στη φύση

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

Ένα παράδειγμα της χρήσης των πρώτων αριθμών στη φύση είναι ως εξελικτική στρατηγική που χρησιμοποιείται από τα τζιτζίκια του γένους Magicicada. Αυτά τα έντομα περνούν τον περισσότερο χρόνο της ζωής τους ως προνύμφες υπογείως. Τα έντομα αυτά μεγαλώνουν και στη συνέχεια βγαίνουν από τις φωλιές τους μετά από 13 ή 17 χρόνια, χρονικό σημείο από το οποίο θα αρχίσουν να πετάνε, να γεννάνε και μετά από λίγες εβδομάδες το πολύ πεθαίνουν. Θεωρείται ότι η λογική για αυτό είναι ότι τα διαστήματα πρώτων αριθμών μεταξύ καταστάσεων έκτακτης ανάγκης καθιστούν πολύ δύσκολο να εξελιχθούν τα αρπακτικά, οι οποίοι θα μπορούσαν να εξειδικευτούν ως θηρευτές των Magicicada. Αν τα έντομα αυτά δεν εμφανίζονταν σε διαστήματα πρώτων αριθμών, ας πούμε κάθε 12 χρόνια, τότε οι θηρευτές τους που θα εμφανίζονταν κάθε 2, 3, 4, 6 ή 12 χρόνια θα ήταν σίγουρο ότι θα τα συναντούσαν. Για πάνω από 200 χρόνια, ο μέσος όρος του πληθυσμού των αρπακτικών κατά τη διάρκεια της πιθανής γέννησης 14 και 15 ετών των τζιτζικιών θα ήταν έως και 2% υψηλότερα από ότι κατά τη διάρκεια γέννησής τους 13 και 17 ετών. Παρόλο που είναι μικρό, το πλεονέκτημα αυτό εμφανίζεται να είναι αρκετό για να οδηγηθούν στη φυσική επιλογή υπέρ της προνομιακής αρίθμησης του κύκλου ζωής για αυτά τα έντομα.

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

Γενικεύσεις Επεξεργασία

Η έννοια του πρώτου αριθμού είναι τόσο σημαντική που έχει γενικευτεί με διάφορους τρόπους σε ποικίλους τομείς των μαθηματικών. Γενικά, ο όρος πρώτος προσδιορίζει την ελαχιστοποίηση ή το διαχωρισμό ενός αντικειμένου στα βασικά του στοιχεία. Για παράδειγμα, το πεδίο των πρώτων αριθμών είναι το μικρότερο υποδιάστημα ενός διαστήματος F που περιέχει το 0 και το 1. Είναι είτε το σύνολο Q ή το πεπερασμένο σύνολο με p στοιχεία, εξ ου και η ονομασία. Συχνά ένας δεύτερος, πρόσθετος ορισμός προορίζεται από τη χρήση της λέξης πρώτος, δηλαδή ότι κάθε αντικείμενο μπορεί ουσιαστικά και μοναδικά να αναλυθεί στα βασικά χαρακτηριστικά του. Για παράδειγμα, στη θεωρία των κόμπων, ένας πρώτος (βασικός) κόμπος είναι ένας κόμπος, ο οποίος είναι αδιάσπαστος, με την έννοια ότι δεν μπορεί να γραφεί ως άθροισμα δύο τετριμμένων κόμπων. Κάθε κόμπος μπορεί να εκφραστεί μοναδικά ως ένα συνδεδεμένο άθροισμα βασικών (πρώτων) κόμπων. Άλλα παραδείγματα αυτού του τύπου είναι τα μοντέλα πρώτων αριθμών και οι πρώτοι αριθμοί τριπλής πολλαπλότητας.

Πρώτα στοιχεία στους δακτύλιους

Από τους πρώτους αριθμούς προκύπτουν δύο πιο γενικές έννοιες, οι οποίες εφαρμόζονται στα στοιχεία κάθε αντιμεταθετικού δακτυλίου R, μια αλγεβρική δομή, όπου ορίζονται η πρόσθεση, η αφαίρεση και ο πολλαπλασιασμός: πρώτα στοιχεία και στοιχεία που δεν ανάγονται. Ένα στοιχείο p του R ονομάζεται πρώτο στοιχείο αν δεν είναι ούτε μηδέν ούτε μονάδα (δηλαδή δεν έχει αντίστροφο στον πολλαπλασιασμό) και ικανοποιεί την παρακάτω προϋπόθεση: δοθέντων x και y στο R, τέτοια ώστε ο p να διαιρεί το γινόμενο xy, τότε ο p διαιρεί τον x ή τον y. Ένα στοιχείο δεν ανάγεται αν δεν μπορεί να γραφεί ως γινόμενο δύο στοιχείων του δακτυλίου, τα οποία δεν είναι μονάδες. Στο δακτύλιο Ζ των ακεραίων αριθμών, το σύνολο των πρώτων στοιχείων ισούται με το σύνολο των στοιχείων που δεν ανάγονται, το οποίο είναι το

 

Σε κάθε δακτύλιο R, κάθε πρώτο στοιχείο δεν ανάγεται. Το αντίστροφο γενικά δεν ισχύει, αλλά ισχύει για τη μοναδική παραγοντοποίηση διαστημάτων.

Το θεμελιώδες θεώρημα της αριθμητικής συνεχίζει να ισχύει στη μοναδική παραγοντοποίηση διαστημάτων. Ένα παράδειγμα τέτοιου διαστήματος είναι οι ακέραιοι του Γκάους Z[i], οι οποίοι αποτελούν το σύνολο των μιγαδικών αριθμών της μορφής a + bi, όπου το i δηλώνει τη μονάδα των φανταστικών αριθμών και οι a και b είναι τυχαίοι ακέραιοι αριθμοί. Τα πρώτα στοιχεία του συνόλου αυτού είναι γνωστά ως πρώτοι αριθμοί του Gauss. Κάθε πρώτος αριθμός (ακέραιος) δεν είναι πρώτος αριθμός του Γκάους: στο μεγαλύτερο δακτύλιο Z[i], 2 παράγοντες στο γινόμενο των δύο πρώτων αριθμών του Γκάους (1 + i) και (1 - i). Λογικοί πρώτοι αριθμοί (δηλαδή πρώτα στοιχεία του Ζ) της μορφής 4k + 3 είναι πρώτοι αριθμοί του Γκάους, ενώ όλοι οι πρώτοι αριθμοί της μορφής 4k + 1 δεν είναι.

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

Στη θεωρία των δακτυλίων, η έννοια του αριθμού αντικαθίσταται γενικά από την έννοια του ιδεώδους. Τα ιδεώδη των πρώτων αριθμών, τα οποία γενικεύουν τα πρώτα στοιχεία, υπό την έννοια ότι το βασικό ιδανικό που παράγεται από ένα πρώτο στοιχείο είναι ιδανικό πρώτου αριθμού, είναι ένα σημαντικό εργαλείο και αντικείμενο της μελέτης της αντιμεταθετικής άλγεβρας, της αλγεβρικής θεωρίας αριθμών και της αλγεβρικής γεωμετρίας. Τα ιδανικά των πρώτων αριθμών του δακτυλίου των ακεραίων αριθμών είναι τα ιδανικά (0), (2), (3), (5), (7), (11), ... Το θεμελιώδες θεώρημα της αριθμητικής γενικεύεται στο θεώρημα των Λάσκερ–Νόθερ, το οποίο εκφράζει κάθε ιδανικό σε ένα αντιμεταθετικό δακτύλιο του Noether ως την τομή βασικών ιδανικών, τα οποία αποτελούν τις κατάλληλες γενικεύσεις των δυνάμεων των πρώτων αριθμών.

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

 

όπου ο x είναι ένας ακέραιος και p και q είναι (συνήθεις) πρώτοι αριθμοί. Οι πρόσφατες προσπάθειες για την απόδειξη του τελευταίου θεωρήματος του Φερμά κορυφώθηκαν, όταν ο Kummer εισήγαγε τους τακτικούς πρώτους αριθμούς, δηλαδή πρώτους αριθμούς που ικανοποιούν μια συγκεκριμένη προϋπόθεση σχετικά με την αποτυχία της μοναδικής παραγοντοποίησης στο δακτύλιο που αποτελείται από τις εκφράσεις

 

όπου a0, ..., ap-1 είναι ακέραιοι και ο ζ είναι ένας μιγαδικός αριθμός, τέτοιος ώστε ζp = 1.

Αποτιμήσεις

Η θεωρία των αποτιμήσεων (valuation theory) μελετά συγκεκριμένες συναρτήσεις από ένα διάστημα Κ στους πραγματικούς αριθμούς R που ονομάζονται αποτιμήσεις. Κάθε τέτοια αποτίμηση αποδίδει μια τοπολογία στο Κ και δυο αποτιμήσεις ονομάζονται ισοδύναμες, αν αποδίδουν την ίδια τοπολογία. Ένας πρώτος αριθμός του Κ (μερικές φορές λέγεται μια τοποθεσία του Κ) είναι μια κλάση ισοδυναμίας των αποτιμήσεων. Για παράδειγμα, η p-αδική αποτίμηση ενός ρητού αριθμού q ορίζεται να είναι ο ακέραιος vp(q), τέτοιος ώστε

 

όπου οι r και s δεν είναι διαιρέσιμοι από τον p. Για παράδειγμα, v3(18/7) = 2. Ο p-αδικός τύπος ορίζεται ως[nb 1]

 

Πιο συγκεκριμένα, αυτός ο τύπος γίνεται μικρότερος, όταν ένας αριθμός πολλαπλασιάζεται από τον p, σε έντονη αντίθεση με τη συνήθη απόλυτη τιμή (επίσης αναφέρεται και ως άπειρος πρώτος). Ενώ συμπληρώνουμε τον Q (περίπου συμπληρώνοντας τα κενά) όσον αφορά την απόλυτη τιμή, αυτή αποδίδει το διάστημα των πραγματικών αριθμών, συμπληρώνοντας όσον αφορά τον p-αδικό τύπο |-|p αποδίδει το διάστημα των p-αδικών αριθμών. Αυτοί είναι ουσιαστικά όλοι οι πιθανοί τρόποι να συμπληρώσουμε τον Q, σύμφωνα με το θεώρημα του Οστρόφσκι.Ορισμένες αριθμητικές ερωτήσεις που σχετίζονται με τον Q ή με πιο γενικά καθολικά πεδία μπορούν να μεταφερθούν εμπρός και πίσω στα συμπληρωμένα (ή τοπικά) διαστήματα. Αυτή η τοπική-καθολική αρχή υπογραμμίζει ξανά τη σημασία των πρώτων αριθμών στη θεωρία αριθμών.

Στις τέχνες και τη λογοτεχνία Επεξεργασία

Οι πρώτοι αριθμοί έχουν επηρεάσει πολλούς καλλιτέχνες και συγγραφείς. Ο Γάλλος συνθέτης Ολιβιέρ Μεσσιάν χρησιμοποίησε τους πρώτους αριθμούς για να δημιουργήσει αμετρική μουσική μέσω φυσικών φαινομένων. Σε έργα, όπως Λα Νατιβίτ ντου Σενό (1935) και Κουάτρ ετούντ ντε ριμ (1949–50), ο συνθέτης χρησιμοποιεί ταυτόχρονα μοτίβα με μήκη που δίνονται από διαφορετικούς πρώτους αριθμούς για να δημιουργήσει απρόβλεπτους ρυθμούς: οι πρώτοι αριθμοί 41, 43, 47 και 53 εμφανίζονταi στο έργο "Neumes rythmiques". Σύμφωνα με τον Μεσσιάν, αυτός ο τρόπος σύνθεσης ήταν εμπνευσμένος από τις κινήσεις της φύσης, τις κινήσεις της ελεύθερης και άνισης διάρκειας.

Στο επιστημονικής φαντασίας μυθιστόρημά του Contact, ο επιστήμονας της NASA Καρλ Σάγκαν αναφέρει ότι οι πρώτοι αριθμοί μπορούν να χρησιμοποιηθούν ως ένα μέσο επικοινωνίας με τους εξωγήινους, μια ιδέα που πρώτα ανέπτυξε ανεπίσημα με τον Αμερικανό αστρονόμο Φρανκ Ντράκε το 1975. Στο μυθιστόρημά του The Curious Incident of the Dog in the Night-Time ο Μαρκ Χάντον, ο αφηγητής οργανώνει τα τμήματα της ιστορίας από διαδοχικούς πρώτους αριθμούς.

Πολλές ταινίες, όπως Cube, Sneakers, The Mirror Has Two Faces και A Beautiful Mind αντικατοπτρίζουν μια δημοφιλή γοητεία των πρώτων αριθμών και της κρυπτογραφίας. Οι πρώτοι αριθμοί χρησιμοποιούνται ως αλληγορία για τη μοναξιά και την απομόνωση στο μυθιστόρημα του The Solitude of Prime Numbers του Paolo Giordano, στο οποίο οι πρώτοι αριθμοί παρουσιάζονται ως ξένοι μεταξύ των ακεραίων αριθμών.

Δείτε ακόμη Επεξεργασία


Σημειώσεις Επεξεργασία

  1. κάποιοι δίνουν τον ορισμό  .

Παραπομπές Επεξεργασία

  1. Caldwell, Chris. «The Top Twenty: Proth». The Prime Pages. 
  2. Chris K. Caldwell. «The Top Twenty: Factorial». Primes.utm.edu. Ανακτήθηκε στις 5 Φεβρουαρίου 2013. 
  3. Chris K. Caldwell. «The Top Twenty: Primorial». Primes.utm.edu. Ανακτήθηκε στις 5 Φεβρουαρίου 2013. 
  4. Caldwell, Chris K. «The Prime Database: 2996863034895*2^1290000-1». 
  5. «World Record Twin Primes Found!». Αρχειοθετήθηκε από το πρωτότυπο στις 4 Ιανουαρίου 2018. Ανακτήθηκε στις 5 Ιανουαρίου 2018. 
  6. Chris K. Caldwell. «The Top Twenty: Twin Primes». Primes.utm.edu. Ανακτήθηκε στις 5 Φεβρουαρίου 2013. 
  7. «GIMPS Discovers - Largest Known Prime Number: 282,589,933-1». www.mersenne.org. 21 Δεκεμβρίου 2018. Ανακτήθηκε στις 12 Ιανουαρίου 2019. 
  8. «50th Known Mersenne Prime Discovered». www.mersenne.org. Ανακτήθηκε στις 4 Ιανουαρίου 2018. 
  9. Επίσημη σελίδα GIMPS
  10. Ο μεγαλύτερος γνωστός πρώτος αριθμός ήταν πάντα και Μερσέν πρώτος από το 1952, εκτός του 1989 και του 1992; δείτε Κάλντγουελ, "The Largest Known Prime by Year: A Brief History" από το Πανεπιστήμιο του Τενεσί.

Περαιτέρω ανάγνωση Επεξεργασία

Ελληνική βιβλιογραφία Επεξεργασία

  • Λάκκης, Κωνσταντίνος (1991). Θεωρία Αριθμών (7η έκδοση). Ζήτη. 
  • Αντωνιάδης, Ι.· Κοντογεώργης, Α. (2015). Θεωρία αριθμών και εφαρμογές. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. 
  • Πουλάκης, Δ. (2015). Υπολογιστική θεωρία αριθμών. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. doi:10.57713/kallipos-323. 
  • Κολουντζάκης, Μ.· Παπαχριστόδουλος, Χ. (2015). «Θεωρία Αριθμών». Διακριτά μαθηματικά. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. 

Ξένη βιβλιογραφία Επεξεργασία

Εξωτερικοί σύνδεσμοι Επεξεργασία