מספרים ראשוניים.

מספרים שלא מתחלקים

את שתים־עשרה סוכריות אפשר לחלק בצורה הוגנת בין 2, 3, 4 או 6 ילדים. את שלוש־עשרה אי אפשר: איך שלא תחלקו אותן, תמיד תישאר סוכרייה עודפת, אלא אם תתנו את כולן לילד אחד, או סוכרייה אחת לכל אחד משלושה־עשר ילדים. מספר שלם גדול מ־1 שאפשר לחלק רק בשתי הדרכים המשעממות האלה הוא מספר ראשוני. המחלקים היחידים שלו הם 1 והוא עצמו. מספר שיש לו מחלקים נוספים, כמו 12, הוא מספר פריק.

הראשוניים מתחילים ב־2, 3, 5, 7, 11, 13, 17, 19, 23, 29. רק אחד מהם זוגי, כי כל מספר זוגי אחר אפשר לחלק לשניים. ו־1 נשאר בחוץ בכוונה, מסיבה שתתברר בהמשך.

הראשוניים חשובים כי מהם בנוי כל מספר שלם אחר. ממשיכים לפרק מספר לגורמים, ותמיד מגיעים בסוף לראשוניים: $360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5$$360 =$$2 \times 2 \times 2 \times 3 \times 3 \times 5$⁠. בכל דרך שתבחרו, תגיעו לאותם ראשוניים, וכל אחד מהם יופיע אותו מספר פעמים. זה נקרא המשפט היסודי של האריתמטיקה, ובגללו 1 לא נחשב לראשוני: אילו היה ראשוני, אפשר היה להוסיף לפירוק כמה אחדות שרוצים, והפירוק לגורמים כבר לא היה יחיד.

ספירלה של מספרים

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

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

נסו: הורידו את גבול הספירה ל־100, ריבוע של 10 × 10, ומצאו את 2, 3, 5 ו־7 ליד האמצע. אחר כך העלו אותו ל־2,500 ואז ל־10,000: המספרים נעשים קטנים מכדי לקרוא אותם, והקווים האלכסוניים מתגלים.

חזרה לניסוי ↑

חלק מהדפוס פשוט. ליד כל מספר בספירלה נמצא המספר שגדול ממנו באחד או קטן ממנו באחד, ולכן מספרים זוגיים ואי־זוגיים מתחלפים כמו המשבצות של לוח שחמט, וכל אלכסון הוא כולו אי־זוגי או כולו זוגי. כל הראשוניים חוץ מ־2 הם אי־זוגיים, ולכן הם יכולים ליפול רק על מחצית מהאלכסונים. והמספרים לאורך אלכסון אחד מצייתים לנוסחה: הקו שעולה למעלה וימינה מ־1 עובר דרך 1, 3, 13, 31, 57, שהם הערכים של $4n^2 - 2n + 1$⁠. יש נוסחאות כאלה שפוגעות בראשוניים הרבה יותר מאחרות. למתמטיקאים יש השערה שנבדקה היטב לגבי התדירות שבה כל אחת מהן אמורה לפגוע בהם, אבל איש לא הוכיח אותה.

הנפה של ארטוסתנס

איך מוצאים את כל הראשוניים עד מספר מסוים? לפני כ־2,200 שנה השתמש ארטוסתנס, מלומד יווני באלכסנדריה, בשיטה שעדיין נקראת על שמו. כתבו את כל המספרים. הקיפו בעיגול את 2, הראשוני הראשון, ומחקו כל כפולה של 2. המספר הבא שלא נמחק, 3, חייב להיות ראשוני, כי אף מספר קטן ממנו לא מחלק אותו. הקיפו אותו ומחקו את הכפולות שלו. אחר כך 5, אחר כך 7, וכן הלאה.

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

חזרה לניסוי ↑

שני קיצורי דרך הופכים את השיטה למהירה. כשמגיעים לראשוני $p$⁠, אפשר להתחיל למחוק מ־$p \times p$⁠, כי לכל כפולה קטנה יותר, כמו $p \times 2$⁠ או $p \times 3$⁠, יש גורם קטן יותר, והיא כבר נמחקה. לכן בסצנה 3 מתחיל ב־9 ו־5 ב־25. ואפשר לעצור כש־$p \times p$⁠ גדול מגבול הספירה: למספר פריק עד גבול הספירה חייב להיות גורם שאינו גדול מהשורש הריבועי שלו, ולכן הוא כבר נמחק. כדי למצוא את הראשוניים עד 400 מספיק לנפות עם הראשוניים עד 20. מה שלא נמחק בסוף הוא ראשוני, ובסצנה אלה בדיוק האריחים הזהובים.

למה הראשוניים לא נגמרים לעולם

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

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

רווחים שגדלים, תאומים שממשיכים להופיע

הראשוניים הולכים ומתדלדלים ככל שסופרים. רבע מהמספרים עד 100 הם ראשוניים, אבל רק אחד משמונה מהמספרים עד 10,000. ליד מספר גדול $N$⁠, בערך מספר אחד מכל $\ln N$⁠ הוא ראשוני, כאשר $\ln$⁠ הוא הלוגריתם הטבעי. זה משפט המספרים הראשוניים, שהוכח ב־1896, ופירושו שהרווח הממוצע בין ראשוניים שכנים גדל לאט, כמו $\ln N$⁠.

נסו: הזיזו את ניפוי הספירלה עד הסוף, אל נפה ורווחים, ואז גררו את גבול הספירה עד הקצה. כל עמודה היא הרווח מראשוני אחד לראשוני הבא. העקומה המקווקוות היא $\ln p$⁠, והרווח הגדול ביותר מסומן בצבע ענבר, על הלוח ועל האריחים.

חזרה לניסוי ↑

רווחים יכולים להיות ארוכים כרצונכם. המספרים $101! + 2$⁠, $101! + 3$⁠, וכן הלאה עד $101! + 101$⁠, כאשר $101!$⁠ פירושו $1 \times 2 \times 3 \times \dots \times 101$⁠, הם מאה מספרים פריקים ברצף: הראשון מתחלק ב־2, הבא ב־3, וכן הלאה. ובכל זאת נראה שגם הרווחים הקצרים לא נגמרים. זוגות של ראשוניים שההפרש ביניהם 2 בלבד, כמו 11 ו־13 או 9,857 ו־9,859, נקראים ראשוניים תאומים, והם ממשיכים להופיע עד כמה שבדקו. השאלה אם הם נמשכים לעד היא אחת השאלות הפתוחות הוותיקות ביותר במתמטיקה. ב־2013 הוכיח יטאנג צ’אנג שרווח כלשהו מתחת ל־70 מיליון מופיע אינסוף פעמים, ומתמטיקאים אחרים הורידו מאז את החסם הזה ל־246.

איפה משתמשים בראשוניים

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

מה המודל הזה משאיר בחוץ

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

הסצנה מנפה עם כל ראשוני בתורו ומוחקת כל מספר פריק פעם אחת, בצבע של הגורם הראשוני הקטן ביותר שלו. על הנייר הייתם מוחקים את 12 פעמיים, פעם בשביל 2 ופעם בשביל 3; התוצאה זהה. הספירה נעצרת ב־10,000, ועד שם יש 1,229 ראשוניים. תרשים הרווחים מראה רק רווחים בין ראשוניים ששניהם נמצאים בתחום הספירה, ולכן הרווח שאחרי הראשוני האחרון חסר, ועקומת $\ln p$⁠ מתארת את הממוצע, לא רווח בודד כלשהו.