מספר ראשוני

המונח "ראשוני" מפנה לכאן. אם הכוונה למשמעות אחרת, ראו ראשוני (פירושונים).

בתורת המספרים, מספר ראשוני הוא מספר טבעי גדול מ-1, שלא ניתן להציגו כמכפלה של שני מספרים טבעיים קטנים ממנו, כלומר הוא מתחלק רק ב-1 ובעצמו. מספר טבעי גדול מ-1 שאינו ראשוני נקרא מספר פריק. המספר 1 אינו נחשב ראשוני, וגם לא פריק.

מקובל להתייחס אל המספרים הראשוניים כאבני הבניין של תורת המספרים, משום שאפשר להרכיב מהם, באמצעות פעולת הכפל, כל מספר טבעי. כבר אוקלידס ידע להוכיח שקיימים אינסוף מספרים ראשוניים. ענפים מרכזיים בתורת המספרים עוסקים בתכונות שונות של המספרים הראשוניים, בצפיפות שבה הם מופיעים, במידת הסדירות של הופעות אלה, ועוד.

הכללות של המספרים הראשוניים לשדות שמעבר למספרים הרציונליים נלמדות במסגרת תורת המספרים האלגברית ותורת החוגים.

פירוק יחיד לגורמים

לפי "המשפט היסודי של האריתמטיקה", כל מספר טבעי גדול מ-1 אפשר להציג באופן יחיד כמכפלה של מספרים ראשוניים (למשל: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 28 = 7\times 2\times 2} ). ההצגה הזו יחידה עד כדי שינוי סדר. ראשוניים אלה נקראים גורמים של המספר. בלשון מודרנית, חוג המספרים השלמים הוא תחום פריקות יחידה.

תהליך מציאת המספרים הראשוניים המרכיבים מספר שלם נתון נקרא פירוק לגורמים. זוהי בעיה קשה מבחינה אלגוריתמית, ולא ידוע עבורה אלגוריתם יעיל (כלומר, בעל סיבוכיות פולינומית). חוזקן של שיטות הצפנה מרכזיות נובע מן הקושי לפרק מספר גדול לגורמיו הראשוניים.

שכיחותם של הראשוניים

התפלגות הראשוניים

קיימים אינסוף מספרים ראשוניים. ההוכחה הראשונה לכך ניתנה בספרו של אוקלידס, "יסודות". זוהי הוכחה בדרך השלילה:

ברור שלכל מספר גדול מ-1 יש גורם ראשוני (זו טענה שאפשר להוכיח באינדוקציה מתמטית). נניח שיש רק מספר סופי של ראשוניים,

\ p_{1},\dots ,p_{n}

. המספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ N = p_1\dots p_n+1} (מכפלת n הראשוניים הללו פלוס 1) אינו מתחלק באף אחד מהם, ולכן אין לו גורמים ראשוניים – אבל זו סתירה לכך ש-

\ N>1

. מכאן שאין רשימה סופית הכוללת את כל הראשוניים.

כאשר סופרים את הראשוניים בקטעים ארוכים (כגון: עד 1,000, בין 1,000 ל-2,000, וכן הלאה), מגלים ששכיחותם הולכת ויורדת. גאוס עסק רבות בחישובים בקשר לסוגיה זו, ושיער ששכיחות הראשוניים בין 1 ל-x יורדת, בקירוב, ביחס הפוך ללוגריתם הטבעי של x. כחמישים שנים אחר-כך חקר רימן את פונקציית זטא הקרויה על שמו, במטרה להוכיח את ההשערה של גאוס. על היסודות שהניח רימן, הצליחו לבסוף המתמטיקאים של סוף המאה ה-19 להוכיח את משפט המספרים הראשוניים: מספר הראשוניים הקטנים ממספר נתון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} שווה בקירוב ל- :הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \frac{x}{\ln(x)}} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \ln(x)} הוא הלוגריתם הטבעי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} .

ממשפט המספרים הראשוניים אפשר להסיק היכן נמצא, בקירוב, הראשוני ה-n-י, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p_n} : הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p_n \sim n\,\mbox{ln}\,n} . ליתר דיוק, עבור כל שלם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n\ge 6} , מתקיים $\ n\ln n+n(\ln \ln n-1)<p_{n}<n\ln n+n\ln \ln n$ .

לפי השערת ברטראן (שהוכחה במאה ה-19), יש מספר ראשוני בכל קטע מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ [n,2n]} . עם זאת, לא ידוע האם לכל n טבעי קיימים ראשוניים בקטע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ [n^2,(n+1)^2]} .

ברווח שבין ראשוניים סמוכים עוסקת השערת המספרים הראשוניים התאומים.

הצגות של ראשוניים

לא קיים פולינום שאינו קבוע, אפילו בכמה משתנים, המקבל (כאשר מציבים בו מספרים שלמים) רק ערכים ראשוניים. לתוצאה זו יש הכללות רבות. למשל, היא נכונה גם עבור פונקציות אלגבריות (פונקציה F היא אלגברית אם קיים פולינום P כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P(F(z))=0} ; לדוגמה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ F(z) = \sqrt[3]{z^2+\sqrt{z}}} אלגברית). פונקציה מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \sum_{i=1}^{m} P_i(x_1,\dots,x_n) a_i^{Q(x_1,\dots,x_n)}} , שבה הפולינומים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P_i,Q_i} בעלי מקדמים שלמים, והמספרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_i} שלמים, שאינה קבועה, אינה יכולה לקבל רק ערכים ראשוניים כאשר מציבים במשתנים $\ x_{1},\dots ,x_{n}$ ערכים טבעיים^[1].

לעומת זאת, אפשר להציג מספרים ראשוניים באמצעות פונקציות שאינן אלגבריות. לדוגמה, אם מגדירים את הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d(x,y) = \max(x-y,0)} , ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r(y,x)} היא השארית של y בחלוקה ל־x (עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r(y,0)=y} ), אז הראשוני ה-n-י מתקבל מהנוסחה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p_n = \sum_{i=0}^{n^2} d(1,d(\sum_{j=0}^{i}r(d(j,1)!^2,j),n))} ^[2]. בעזרת טכניקות שפותחו במסגרת פתרון הבעיה העשירית של הילברט, נמצאו פולינומים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P(x_1,\dots,x_n)} בעלי מקדמים שלמים, כך שקבוצת הערכים הטבעיים שהפולינום מקבל, כאשר מציבים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_1,\dots,x_n} מספרים טבעיים, מתלכדת עם קבוצת המספרים הראשוניים^[3].

משפט מילס קובע כי קיים קבוע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} כך ש- $[A^{3^{n}}]$ ראשוני לכל n טבעי (כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [\cdot]} היא פונקציית הערך השלם).

הצגות ויזואליות של ראשוניים

צורה ויזואלית של התפלגות המספרים הראשוניים ניתנת להצגה על ידי ספירלת אולם. אופן הצגה זה מדגיש את הראשוניים המופיעים בסדרות ריבועיות, כמו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 4n^2+1} . את הספירלה גילה המתמטיקאי ומדען האטום סטניסלב אולם.

ראשוניים בסדרות חשבוניות

את משפט המספרים הראשוניים הכליל דיריכלה לסדרות חשבוניות: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a,n} הם מספרים זרים, אז ישנם אינסוף מספרים ראשוניים השקולים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} . דיריכלה הוכיח שבכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} , המספרים הראשוניים מפוזרים באופן אחיד בקירוב, בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \phi(n)} השאריות האפשריות מודולו $\ n$ . אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \pi(x,n,a)} מייצג את כל המספרים הראשוניים בטווח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ [2,x]} השקולים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mbox{gcd}(a,n)=1} , אזי

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \pi(x,n,a) \sim \frac{x}{\phi(n)\,\mbox{ln}\,x}} .

לעומת זאת, לא ידוע האם יש אינסוף ראשוניים מצורות שאינן ליניאריות, כגון $\ n^{2}+1$ .

טורים ומכפלות אינסופיות

ידוע שסכום הטור ההרמוני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \sum_{n\leq x} \frac{1}{n}} הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \ln(x)+\gamma+o(1)} (כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \gamma} הוא קבוע אוילר-מסקרוני). לעומת זאת, כאשר מסכמים על ראשוניים בלבד, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \sum_{p \leq x}\frac{1}{p} = \ln\ln(x)+B+o(1)} , כאשר B קבוע. ובפרט טור ההופכיים של המספרים הראשוניים מתבדר.

באופן דומה, המכפלה $\ \prod _{n=2}^{N}(1-1/n)={\frac {1}{N}}$ , בעוד ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \prod_{p\leq N}(1-1/p) \sim \frac{e^{-\gamma}}{\ln(N)}} .

ראשוניים קטנים וגדולים

המספרים הראשוניים הקטנים ביותר הם 2, 3, 5, 7, 11, 13 ו-17.

נכון ל-2019, המספר הראשוני הגדול ביותר שהתגלה הוא מספר מרסן הראשוני ה-51, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{82,589,933}-1} ^[4]. למספר זה 24,862,048 ספרות עשרוניות. המספר התגלה באמצעות חישוב מבוזר קהילתי של מיזם GIMPS על ידי פטריק לארוץ'. קדם לו המספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{77,232,917}-1} שהתגלה ב-26 בדצמבר 2017 שהוא מספר מרסן הראשוני ה-50, שהתגלה על ידי ג'ון פייס ממיזם GIMPS^[5].

ב-12 באוקטובר 2024 נמצא על ידי המתנדב לוק דוראנט מספר ראשוני חדש, מספר המרסן הראשוני ה-52, שהוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{136,279,841}-1} , המספר הוא בן 41,024,320 ספרות. גילוי המספר החדש הוא לאחר כ-6 שנים שלא התגלה מספר חדש, והוא נמצא על ידי תוכנת החיפוש Mersenne Prime Search (GIMPS) המספר פורסם רשמית ב-21 באוקטובר 2024 (לאחר שהסתיימה בדיקתו ב-19 באוקטובר)^[6] מוצא המספר זכה בפרס בסך 3000 דולר ארצות הברית^[7].

אלגוריתמים

מאז המצאת שיטת RSA ב-1977, הפכו המספרים הראשוניים למרכיב יסודי כמעט בכל מערכת הצפנה המשלבת מפתחות ציבוריים ופרטיים. במקרים רבים, חוזק ההצפנה מבוסס על הקלות היחסית שבה אפשר לבצע פעולות של כפל והעלאה בחזקה מודולריות, גם במספרים גדולים (בני מאות ספרות), ומאידך על הקושי העצום שבפירוק מספרים כאלה לגורמיהם הראשוניים.

מציאת כל המספרים הראשוניים הקטנים ממספר נתון

שגיאה ביצירת תמונה ממוזערת:

מציאת כל המספרים הראשוניים בין 2 ל-120 באמצעות הנפה של ארטוסתנס.

ארטוסתנס, מתמטיקאי ואסטרונום יווני בן המאה ה-3 לפנה"ס, פיתח אלגוריתם פשוט ויעיל למציאת כל המספרים הראשוניים הקטנים ממספר נתון, הקרוי על שמו: הנפה של ארטוסתנס. אלגוריתם זה מאתר מספרים ראשוניים בהדרגה ככאלה שאינם מספרים פריקים, אשר אותם הוא מפיק עבור כל מספר ראשוני, החל מ 2, על ידי ספירה בכפולות של אותו מספר. לדוגמה:

קובעים 2 כמספר ראשוני הראשון, סופרים ממנו בצעדים של 2 ומסמנים את כל המספרים האלה (שיהיו המספרים הזוגיים) כפריקים. קובעים ש 3 הוא הראשוני הבא ומסמנים את כפולותיו על ידי ספירה בשלשות (יהיו אלה כל הכפולות של 3). 5 הוא הראשוני הבא (את 4 סימנו כבר בשלב הראשון), ואת כפולותיו מסמנים על ידי ספירה בצעדים של 5, וכך הלאה.

הנפה של ארטוסתנס יעילה מבחינת סיבוכיות הזמן הנדרש לביצוע המשימה ליצירת רשימה של מספרים ראשוניים הקטנים מגבול מסוים, אך אינה יעילה לבדיקת ראשוניות של מספר נתון; לשם כך יש דרכים אחרות.

הוכחת ראשוניות

כדי להוכיח שמספר נתון אינו ראשוני, די להציג פירוק שלו לשני גורמים. מכאן שזיהוי מספרים לא ראשוניים הוא בעיה שהיא לפחות במחלקת הסיבוכיות NP. גם בדיקה האם מספר הוא ראשוני שייכת ל-NP, בהתבסס על כך שמספר p הוא ראשוני אם ורק אם קיים מספר מסדר p-1 בחבורת אוילר של p, ותנאי זה ניתן לבדיקה באופן יעיל בהינתן הפירוק של p-1 (כך שהוכחת NP לראשוניות p תכלול את הפירוק הזה ואת המספר מסדר p-1). בשנת 2002 הציגו מנינדרה אגרוול, נירג' קייל וניטין סקסנה אלגוריתם פולינומי להוכחת ראשוניות, הנקרא על שמם מבחן AKS לראשוניות. בכך הראו שהוכחת ראשוניות שייכת למחלקת הסיבוכיות P‏^[8] ולפיכך גם הבעיה הדואלית (האם מספר אינו ראשוני) שייכת ל-P.

מבחני ראשוניות

הדרך הנאיבית לבדיקת ראשוניות של מספר נתון נקראת "חלוקה ניסיונית" (Trial division): ניסיון לחלק את המספר הנתון בכל המספרים מ־2 ועד לשורש הריבועי של המספר הנתון. אם המספר לא התחלק באף אחד ממספרים אלו הוא גם לא יתחלק באף מספר גדול יותר ולכן הוא ראשוני. במספרים קטנים (ובסמוך להפעלת שיטת הנפה של ארטוסתנס), עדיף לבצע את החילוק הניסיוני רק במספרים ראשוניים. לשתי השיטות סיבוכיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(\sqrt{n})} או קרוב לזה, והן אינן יעילות עבור מספרים גדולים (בני עשרות ספרות עשרוניות).

אלגוריתמים מתקדמים יותר לבדיקת ראשוניות מתחלקים לשני סוגים עיקריים:

אלגוריתם בדיקת ראשוניות אקראי, אלו אלגוריתמים אקראיים, המקבלים מספר כלשהו ומחזירים תשובה "אמת" או "שקר" לגבי ראשוניותו של המועמד. אלגוריתם כזה עשוי לטעות בכיוון אחד: התשובה "שקר" פירושה שהמספר פריק, ואילו התשובה "אמת" פירושה שהמספר ראשוני בסיכוי גבוה מאד.
בדיקת ראשוניות דטרמיניסטית, נקראת גם בדיקת ראשוניות אמיתית. בניגוד לשיטה הקודמת, התשובה שמחזיר אלגוריתם כזה היא נכונה בוודאות. הוודאות נקנית במחיר של סיבוכיות גבוהה יותר.

מבחנים רבים, משתי המחלקות, מבוססים על המשפט הקטן של פרמה: עבור כל ראשוני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} ושלם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} זר ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} , מתקיים השוויון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a^{p-1} \equiv 1 (\mbox{mod }p)} . לפיכך, אם השוויון אינו מתקיים, זוהי ראיה לכך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} אינו ראשוני. קיימים אלגוריתמים יעילים לחישוב הערך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a^{n-1}} מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} , כגון אלגוריתם ריבוע וכפל (העלאה חוזרת בריבוע, וכפל ב-a על-פי ההצגה הבינארית של n), שסיבוכיותו פולינומית באורך של n. כל מספר ראשוני יעבור את המבחן, אולם לכל a ישנם מספרים פריקים שהמבחן לא יאתר – אלו קרויים פסאודו ראשוניים.

גרי מילר ניצל תכונות ידועות של המשפט הקטן של פרמה ליצירת אלגוריתם דטרמיניסטי פולינומי למבחן ראשוניות, המתבסס על השערת רימן המוכללת (ERH). מיכאל רבין הרחיב את האלגוריתם מיד לאחר מכן, למבחן ראשוניות פולינומי אקראי. האלגוריתם נקרא על שמם אלגוריתם מילר-רבין. רוברט סולוביי ופולקר שטראסן הציעו אלגוריתם למבחן ראשוניות אקראי המבוסס על סימן יעקובי. עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ראשוני כלשהו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left({a\over n}\right) = a^{{n-1 \over 2}} (\mbox{mod }n)} מתקיים עבור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} . גם אלגוריתם זה ניתן להרחבה למבחן ראשוניות דטרמיניסטי, בהנחה שהשערת רימן המורחבת נכונה.

שפי גולדווסר וג'ו קיליאן הציעו אלגוריתם אקראי למבחן ראשוניות המתבסס על עקום אליפטי, שזמן הריצה שלו פולינומי כמעט עבור כל קלט. בהתבסס על רעיון זה, פיתח ארתור אטקין אלגוריתם דטרמיניסטי יעיל מאוד מבחינה מעשית לבדיקת ראשוניות הנקרא Atkin's test. יתרונה של הגישה הוא שהיא מספקת הוכחות קצרות לראשוניות (primality certificate).

לאונרד אדלמן והואנג פרסמו אלגוריתם הסתברותי שלעולם אינו טועה, אולם רק ניתן לומר שתוחלת זמן הריצה שלו פולינומית, כלומר הם הראו שבדיקת ראשוניות היא במחלקת הסיבוכיות ZPP = RP ∩ Co-RP.

מבחינה תאורטית לפחות סוגיית הסיבוכיות של בדיקת ראשוניות יושבה ב-2002 כששלושה מדעני מחשב הודיים, אגרוול, קייל וסקסנה, הראו אלגוריתם פולינומי דטרמיניסטי לבדיקת ראשוניות הנקרא על שמם AKS. האלגוריתם מבוסס על הכללה של המשפט הקטן של פרמה לחוגי פולינומים מעל שדות סופיים. סיבוכיות האלגוריתם היא בסביבות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(\mbox{log}^6(n))} ^[9].

איברים ראשוניים בתחומי שלמות

חוג המספרים השלמים אינו אלא אחד מני תחומי שלמות רבים. בתחום שלמות כללי יש שני סוגי איברים שאפשר לראות בהם הכללה של המספרים הראשוניים: איבר אי-פריק של תחום שלמות הוא איבר a (לא הפיך ושונה מאפס) שאין לו מחלקים לא טריוויאליים, כלומר, אם a=bc אז כל אחד משני הגורמים b ו-c הוא הפיך או כפולה של a באיבר הפיך. איבר p הוא איבר ראשוני, אם כל אימת ש-p מחלק מכפלה bc, הוא מחלק את אחד הגורמים שלה. כל איבר ראשוני הוא אי-פריק, אבל ההפך אינו בהכרח נכון. בחוג השלמים שני המושגים מתלכדים (זוהי הלמה של אוקלידס), ומגדירים את המספרים הראשוניים המוכרים, והמספרים הנגדיים להם: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2, -2, 3, -3, ...} .

התכונה הבסיסית של המספרים הראשוניים (בחוג השלמים) מתבטאת במשפט היסודי של האריתמטיקה: כל מספר אפשר לפרק לגורמים ראשוניים, באופן יחיד. גם כאן, כשבוחנים תחום שלמות כללי במקום חוג השלמים, שתי התכונות האלה עשויות שלא להתקיים. ישנם תחומי שלמות שבהם הראשוניים נדירים יותר, וקיים פירוק לגורמים אי-פריקים, אבל לא לגורמים ראשוניים (לדוגמה: בחוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mathbb{Z}[\sqrt{-6}]} אפשר לפרק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 6 = 2 \cdot 3 = -\sqrt{-6} \cdot \sqrt{-6}} ; הגורמים אי-פריקים אבל אינם ראשוניים). ישנם גם תחומי שלמות שבהם אין פירוק אפילו לגורמים אי-פריקים (אלו חוגים שאינם נתריים). עם זאת, כאשר קיים פירוק לגורמים ראשוניים, הוא יחיד (אפילו בין כל הפירוקים לגורמים אי-פריקים). בתחומים ראשיים, כל איבר אי-פריק הוא ראשוני, ויש פירוק יחיד לגורמים.

שאלות פתוחות

תחום המספרים הראשוניים כולל שאלות פתוחות רבות, ובהן:

השערת גולדבך – האם כל מספר זוגי גדול מ-2 הוא סכום של שני ראשוניים?
השערת המספרים הראשוניים התאומים – האם יש אינסוף זוגות של מספרים ראשוניים שההפרש ביניהם הוא 2?
האם לכל d טבעי קיימים אינסוף זוגות של מספרים ראשוניים שההפרש ביניהם הוא 2d? (הכללה של שתי ההשערות הקודמות).
האם יש אינסוף מספרי פיבונאצ'י ראשוניים?
האם יש אינסוף מספרי פרמה ומספרי מרסן ראשוניים?
האם יש אינסוף מספרים ראשוניים מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n^2+1} ? (בתורת המספרים השאלה ידועה כבעיית אוילר); איוונייץ הוכיח (1972), בעזרת שיטת הנפה, שיש אינסוף מספרים מהצורה האמורה שיש להם לכל היותר שני גורמים ראשוניים.

בתרבות

בספר המדע הבדיוני "מגע" מאת קרל סייגן מזהה גיבורת הספר, העובדת במיזם SETI, שידור המגיע מהחלל של סדרת קולות שהיא סדרת המספרים הראשוניים מתחילתה ועד 907, ומשוכנעת שמקורו בחיים תבוניים מחוץ לכדור הארץ.

ספרו של אפוסטולוס דוקסיאדיס, "הדוד פטרוס והשערת גולדבך"^[10], הוא רומן המתרחש על רקע חיפוש הוכחה להשערת גולדבך, הקובעת שכל מספר זוגי גדול מ-2 ניתן להציג כסכום של שני מספרים ראשוניים. לקידום מכירתו של הספר הכריזו המו"לים של המהדורה האנגלית של הספר בארצות הברית ובבריטניה, על פרס בסך מיליון דולר למי שיוכיח את השערת גולדבך. עד תום המועד שנקבע למתן ההוכחה לא נמצאה ההוכחה המבוקשת.

כריסטופר, המספר בספרו של מארק האדון "המקרה המוזר של הכלב בשעת לילה", הוא ככל הנראה בעל תסמונת אספרגר או תסמונת סוואנט, הוא מחונן ואוהב מתמטיקה. הדבר בולט כבר במספור הפרקים במספרים ראשוניים ולא במספרים מונים כמו בספרים אחרים (פרק 2 הוא הפרק הראשון של הספר). הוא מציג את עצמו כמי מכיר את כל המדינות בעולם ובירותיהן ואת כל המספרים הראשוניים עד 7,507.

בספר "האיש שחשב שאשתו היא כובע" מתאר הנוירולוג אוליבר סאקס את חוויותיו הטיפוליות עם מספר מטופלים, בהם הפרק "התאומים", על אודות תסמונת סוואנט. סאקס נפגש עם זוג תאומים אוטיסטים, שלא היו מסוגלים לקרוא או לבצע פעולות כפל וחילוק, אך היו מסוגלים למצוא בצורה ספונטנית, וכשעשוע קליל, טווח נרחב של מספרים ראשוניים. בעוד שהתאומים "שולפים מן המותן" מספרים ראשוניים בעלי שש עד עשרים ספרות, סאקס נזקק לטבלה המכילה את רשימת המספרים הללו, על מנת לעקוב אחריהם.

המלחין הצרפתי אוליבייה מסייאן השתמש במספרים ראשוניים בהלחנת יצירותיו La Nativité du Seigneur (אנ') ו-Quatre Études de rythme (אנ').

ראו גם

לקריאה נוספת

מרכוס דו סוטוי, המוזיקה של המספרים הראשוניים, הוצאת ידיעות אחרונות, תרגם: אוריאל גבעון, 2006.

קישורים חיצוניים

מיזמי קרן ויקימדיה
ערך מילוני בוויקימילון: מספר ראשוני
ספר לימוד בוויקיספר: מספר ראשוני

יעל נוריק, מספרים ראשוניים – שאלות, תשובות והשערות, במדור "מאגר המדע" באתר של מכון דוידסון לחינוך מדעי, 13 בדצמבר 2014
אהוד דה שליט, מדוע המספרים הראשוניים מסקרנים כל כך?, באתר פרונטירז, 1 באפריל 2019
The Prime Pages מספרים ראשוניים באתר אוניברסיטת טנסי
בודק ראשוניות (באנגלית)
Big Primes - אתר עם רשימות של מספרים ראשוניים, מספרי מרסן, מספרי פיבונאצ'י, מספרי פרמה, מספרים מושלמים ועוד (באנגלית)
מספר ראשוני, באתר MathWorld (באנגלית)
2048 הראשוניים הראשונים.
מספר ראשוני, באתר אנציקלופדיה בריטניקה (באנגלית)
סדרת המספרים הראשוניים, באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
מספרים ראשוניים, דף שער בספרייה הלאומית

הערות שוליים

^ Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 4.4
^ James Jones, Formula for the n'th prime number, Canad. Math. Bull. 18(3) (1975)
^ Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 1
^ 51st Known Mersenne Prime Discovered, www.mersenne.org
^ 50th Known Mersenne Prime Discovered, www.mersenne.org
^ אתר החיפוש של מספרים חדשים
^ עם יותר מ-41 מיליון ספרות: זהו המספר הראשוני הכי גדול, באתר ynet, 21 באוקטובר 2024
^ ראו מאמרם של אגרוול ועמיתיו
^ ראו מאמרם של אגרוול ועמיתיו
^ מהדורה עברית: תרגום: אמיר צוקרמן, הוצאת ידיעות ספרים, 2000

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

39916470מספר ראשוני

[1] Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 4.4

[2] James Jones, Formula for the n'th prime number, Canad. Math. Bull. 18(3) (1975)

[3] Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 1

[4] 51st Known Mersenne Prime Discovered, www.mersenne.org

[5] 50th Known Mersenne Prime Discovered, www.mersenne.org

[6] אתר החיפוש של מספרים חדשים

[7] עם יותר מ-41 מיליון ספרות: זהו המספר הראשוני הכי גדול, באתר ynet, 21 באוקטובר 2024

[8] ראו מאמרם של אגרוול ועמיתיו

[9] ראו מאמרם של אגרוול ועמיתיו

[10] מהדורה עברית: תרגום: אמיר צוקרמן, הוצאת ידיעות ספרים, 2000

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]