מספר ראשוני

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

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

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

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

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

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

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

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

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

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

המספרים הראשוניים הקטנים ביותר הם 2, 3, 5, 7, 11, 13 ו-17.
נכון ל-2019, המספר הראשוני הגדול ביותר שהתגלה הוא מספר מרסן הראשוני ה-51, . למספר זה 24,862,048 ספרות עשרוניות. המספר התגלה באמצעות חישוב מבוזר קהילתי של מיזם GIMPS על ידי פטריק לארוץ'. קדם לו המספר  שהתגלה ב-26 בדצמבר 2017 שהוא מספר מרסן הראשוני ה-50, שהתגלה על ידי ג'ון פייס ממיזם GIMPS.

אלגוריתמים

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

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

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

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

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

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

חוג המספרים השלמים אינו אלא אחד מני תחומי שלמות רבים. בתחום שלמות כללי יש שני סוגי איברים שאפשר לראות בהם הכללה של המספרים הראשוניים: איבר אי-פריק של תחום שלמות הוא איבר a (לא הפיך ושונה מאפס) שאין לו מחלקים לא טריוויאליים, כלומר, אם a=bc אז כל אחד משני הגורמים b ו-c הוא הפיך או כפולה של a באיבר הפיך. איבר p הוא איבר ראשוני, אם כל אימת ש-p מחלק מכפלה bc, הוא מחלק את אחד הגורמים שלה. כל איבר ראשוני הוא אי-פריק, אבל ההפך אינו בהכרח נכון. בחוג השלמים שני המושגים מתלכדים (זוהי הלמה של אוקלידס), ומגדירים את המספרים הראשוניים המוכרים, והמספרים הנגדיים להם: .
התכונה הבסיסית של המספרים הראשוניים (בחוג השלמים) מתבטאת במשפט היסודי של האריתמטיקה: כל מספר אפשר לפרק לגורמים ראשוניים, באופן יחיד. גם כאן, כשבוחנים תחום שלמות כללי במקום חוג השלמים, שתי התכונות האלה עשויות שלא להתקיים. ישנם תחומי שלמות שבהם הראשוניים נדירים יותר, וקיים פירוק לגורמים אי-פריקים, אבל לא לגורמים ראשוניים (לדוגמה: בחוג  אפשר לפרק ; הגורמים אי-פריקים אבל אינם ראשוניים). ישנם גם תחומי שלמות שבהם אין פירוק אפילו לגורמים אי-פריקים (אלו חוגים שאינם נתריים). עם זאת, כאשר קיים פירוק לגורמים ראשוניים, הוא יחיד (אפילו בין כל הפירוקים לגורמים אי-פריקים). בתחומים ראשיים, כל איבר אי-פריק הוא ראשוני, ויש פירוק יחיד לגורמים.