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

שלב 1 מתוך 6

מה זה ראשוני

מספר ראשוני הוא מספר טבעי שיש לו בדיוק שני מחלקים: $1$⁠ והוא עצמו. $7$⁠ ראשוני; $6 = 2 \times 3$⁠ לא, והוא נקרא פריק. כל מספר פריק הוא מכפלה של ראשוניים, בדרך אחת בלבד: הראשוניים הם אבני הבניין של המספרים.

בסצנה המספרים מ־$1$⁠ עד $100$⁠ מסודרים בספירלה על מגש של אריחים. הראשוניים הם האריחים הזהובים הבולטים, הפריקים נמוכים וכהים, ו־$1$⁠ אפור.

שלב 2 מתוך 6

הגדול ביותר עד מאה

כדי לבדוק אם מספר ראשוני, לא צריך לנסות לחלק אותו בכל מספר קטן ממנו. מספיק לנסות את הראשוניים עד השורש שלו: אם $n = a \times b$⁠, אחד הגורמים לא גדול מ־$\sqrt{n}$⁠.

שלב 3 מתוך 6

הנפה

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

גבול הספירה קבוע עכשיו על $400$⁠. ניפוי הספירלה יריץ את הנפה: כל ראשוני מוחק את הכפולות שלו בצבע משלו, מהריבוע שלו והלאה, והלוח סופר כמה כל אחד מחק.

שלב 4 מתוך 6

מתדלדלים

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

שלב 5 מתוך 6

שמינית

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

שלב 6 מתוך 6

כיוון אחד קל

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