בואו נוכיח שיש אינסוף ראשוניים!

אחת מהתוצאות המתמטיות הבסיסיות המפורסמות ביותר היא שקיימים אינסוף מספרים ראשוניים. זו תוצאה נפלאה, בגלל שכל כך קל לומר מה בדיוק היא אומרת, מאוד קל להוכיח אותה, והיא אומרת משהו לא מובן מאליו ובעל השלכות מעניינות. בפוסט הזה אני ארצה להציג במרוכז שלל הוכחות של התוצאה הזו ולומר עליהן כמה דברים נחמדים. אני אלך אחד-לאחד על פי האוסף שמופיע בתחילת The development of prime number theory של Narkiewicz פשוט כי הוא כולל כל הוכחה שאני מכיר ועוד כמה שלא הכרתי קודם. מה שכן, אני אנסה להציג אותן מהקל אל הכבד, כך שגם מי שבקושי מכיר מתמטיקה יוכל להינות מכל מה שאפשרי לפני שהוא יגיע לשלב שבו הוא נשבר.

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

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

בואו נתחיל!

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

את המספרים הטבעיים - 1,2,3 וכן הלאה - אני מניח שכולנו מכירים. עכשיו, אם ניקח מספר כמו 15 למשל, אנחנו רואים שאפשר לכתוב אותו בתור מכפלה של שני מספרים טבעיים קטנים יותר - \( 15=3\cdot5 \). לעומת זאת את 3 ו-5 אי אפשר לכתוב כמכפלה כזו - אפשר רק לכתוב משהו כמו \( 3=3\cdot1 \). מספר כמו 15 נקרא פריק ואילו מספר כמו 3, שהדרך היחידה לכתוב אותו כמכפלה של שני מספרים טבעיים היא בתור הוא עצמו כפול 1, נקרא ראשוני (למעט 1 שהוא לא זה ולא זה ואדבר על כך בהמשך). די ברור שאם ניקח מספר כלשהו שגדול מ-1, יקרה אחד משניים: או שהוא ראשוני, או שאפשר לכתוב אותו בתור מכפלה של שני מספרים קטנים ממנו. אם הם לא ראשוניים, אפשר לפרק גם אותם, וכן הלאה - מכיוון שהגודל של המספרים יורד כל הזמן התהליך הזה חייב להיתקע מתישהו - לא יהיה לנו יותר שום מספר לפרק, ומה שנקבל הוא תיאור של המספר שממנו התחלנו בתור מכפלה של ראשוניים. למשל, אם תעשו את זה על 360 תקבלו \( 360=2\cdot2\cdot2\cdot3\cdot3\cdot5 \). טוב, אולי תקבלו את הגורמים הראשוניים הללו בסדר קצת שונה, למשל \( 360=3\cdot2\cdot5\cdot2\cdot3\cdot2 \), ואתם גם יכולים לכפול את אגף ימין ב-1 כמה שאכפת לכם, אבל אלו יהיו ההבדלים היחידים. זו התכונה המעניינת ביותר של ראשוניים: כל מספר טבעי ניתן לתיאור באופן יחיד (עד כדי שינוי סדר וכפל ב-1 כמה שרוצים) בתור מכפלה של ראשוניים. זו לא תוצאה פשוטה בשום פנים ואופן ולא אוכיח אותה כרגע (ההוכחה קלה מרגע שיש לנו את הטענה הבאה: אם \( p \) ראשוני והוא מחלק את המכפלה \( ab \) אז הוא מחלק את \( a \) או שהוא מחלק את \( b \); אבל הטענה הזו כאמור לא טריוויאלית להוכחה).

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

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

ברגע שבו אינסוף נכנס לתמונה, ההוכחות שלנו נאלצות להיות מתוחכמות. איך אמר יאיר לפיד? קשה להוכיח את השערת גולדבך בגלל אינסופיות המספרים. אני צריך לתת איזה שהוא טיעון כללי שיראה שאני תמיד יכול לייצר עוד ועוד ראשוניים יש מאין. זה מה שאוקלידס עשה (למען האמת, כשקוראים מה הוא עשה - “יסודות”, ספר 9, טענה 20 - רואים שהוא הסתפק בלטפל במקרה של להוכיח שיש יותר מ-3 ראשוניים ולהשאיר לאחרים לטפל במקרה הכללי). הרעיון הוא להתחיל מקבוצה \( p_{1},\dots,p_{n} \) של ראשוניים ולהראות איך אפשר למצוא ראשוני חדש, שלא מופיע בקבוצה הזו (ולכן לא ייתכן שיש מספר סופי שלהם; כי אם היה מספר סופי היינו מסתכלים על קבוצת כל הראשוניים ואז משתמשים בשיטה של אוקלידס כדי לייצר אחד שלא מופיע בה).

התעלול עצמו פשוט: נכפיל את כל הראשוניים, ולתוצאה נוסיף 1: נגדיר \( D=p_{1}\cdots p_{n}+1 \). עכשיו, אם נחלק את \( D \) בראשוני כלשהו מהקבוצה, נקבל שארית 1, כלומר \( D \) לא מתחלק באף אחד מהם. אם \( D \) הוא ראשוני, “ניצחנו”; אבל ייתכן גם ש-\( D \) איננו ראשוני. במקרה הזה פשוט מפרקים אותו לגורמים ראשוניים וכל אחד מהם חייב להיות ראשוני חדש. זה בלבול נפוץ יחסית לחשוב ש-\( D \) חייב להיות ראשוני שנובע מתיאור של ההוכחה בתור “בואו נניח שיש מספר סופי של ראשוניים ונכפול את כולם”

בואו נראה דוגמה או שתיים. אם הקבוצה שלנו כוללת רק את \( 2,3 \) אז נקבל \( D=7 \) שהוא בוודאי ראשוני (שימו לב ש”קפצנו” מעל 5). אם ניקח את הקבוצה \( 3,5 \) (בלי 2) אז נקבל \( D=16 \) שהוא לא ראשוני, אבל ניתן לכתוב בתור \( 16=2\cdot2\cdot2\cdot2 \), כך שנקבל את 2. אם ניקח את הקבוצה \( 3,7 \) אז נקבל \( D=22=2\cdot11 \), כך שאנחנו מקבלים בצורה הזו את 2 או את 11, וכן הלאה.

האם זו שיטה טובה לייצר ראשוניים חדשים? חד משמעית לא. זו שיטה איומה ונוראה, אם אנחנו מתעניינים בהיבטים החישוביים שלה, כלומר בשאלה כמה זמן לוקח להפעיל אותה. לכפול מספרים נתונים זה קל, וגם להוסיף 1 לתוצאה זה קל, אבל ברגע שיש לנו כמות לא גדולה של מספרים (נאמר, 1000) אנחנו מקבלים \( D \) שהוא מספר עצום בגודלו, ולפרק כזה מספר לגורמים - זה יכול להיות עניין קשה ביותר. ובפועל אנחנו מכירים הרבה יותר מ-1,000 מספרים ראשוניים כך שאם ננסה להפעיל את השיטה הזו נקבל \( D \)-ים מגודל מפלצתי לחלוטין. אם כן, השיטה הזו לחלוטין לא יכולה לשמש בתור כלי מעשי לייצור ראשוניים, אבל זה לא באמת חשוב כי זו לא המטרה שלה. המטרה היא להוכיח שיש אינסוף ראשוניים.

עדיין, זה לא אומר שאי אפשר לשאול שאלות תיאורטיות מעניינות על “מה קורה אם מנסים לייצר ראשוניים בצורה הזו”. אז אפשר להגדיר סדרה \( a_{1},a_{2},a_{3},\dots \) באופן הבא: קובעים את \( a_{1}=2 \) ואם כבר קבענו את \( a_{1},\dots,a_{n} \) אז קובעים את \( a_{n+1} \) על ידי כך שמסתכלים על \( D=a_{1}\cdots a_{n}+1 \) ועכשיו לוקחים את \( a_{n+1} \) להיות אחד מהמחלקים הראשוניים של \( D \). כמובן, נשאלת השאלה איזה מחלק ראשוני של \( D \) לקחת. שני חוקים כלליים סבירים שעולים לראש הם “קחו את המחלק הקטן ביותר” ו”קחו את המחלק הגדול ביותר”. מקבלים בצורה הזו שתי סדרות שונות של ראשוניים:

\( 2,3,7,43,13,53,5,6221671,38709183810571,139,\dots \)

\( 2,3,7,43,139,50207,340999,2365347734339,\dots \)

השאלה המתבקשת בנוגע לשתי הסדרות הללו היא “האם כל הראשוניים מופיעים בתוך הסדרה?”. בנוגע לסדרה הראשונה השאלה פתוחה - הנה לכם בעיה פתוחה במתמטיקה עם ניסוח פשוט למדי שאין לנו מושג איך לתקוף בכלל. הסדרה השניה, לעומת זאת, היא בעייתית יותר. אם תסתכלו עליה, מתקבל הרושם שהיא מונוטונית עולה, כלומר אחרי איבר כלשהו בסדרה יבואו רק איברים גדולים ממנו. כמו כן, 5 לא מופיע בין האיברים הראשונים שכתבתי - אחרי 3 מגיע 7, בלי 5 באמצע. בסדרה הראשונה 5 גם כן מתפספס ככה, אבל חוזר אחרי 53 (ולכן רואים מייד שהסדרה הראשונה איננה מונוטונית עולה). אם כן, יש לנו שלוש שאלות הנוגעות לסדרה השניה:

1. האם כל מספר ראשוני מופיע בה?
2. אם לא, האם היא מונוטונית עולה?

את שתי השאלות הללו העלה המתמטיקאי מולין בשנת 1963; שתי הסדרות לעיל נקראות על שמו. התשובה לשתיהן היא שלילית. כדי לראות שהסדרה לא מונוטונית מספיק לחשב בה מספיק איברים (רצוי באמצעות מחשב…) - מגלים שהאיבר העשירי קטן מהתשיעי. גם התשובה לשאלה השניה שלילית - בואו נראה ש-5 אכן לא מופיע בכלל בסדרה הזו (זה יהיה קצת טכני; אם אתם ממש לא רוצים, פשוט תעברו לחלק הבא). לשם כך, בואו נניח בשלילה ש-5 כן הופיע בסדרה; זה אומר שהיה \( D=p_{1}\cdots p_{n}+1 \) עבור \( n \) כלשהו כך ש-5 הוא המחלק הראשוני הגדול ביותר של \( D \). מכיוון שראינו ש-2,3 (הראשוניים היחידים שקטנים מ-5) מופיעים בתחילת הסדרה, ואנחנו יודעים ש-\( D \) לא מתחלק באף אחד מהראשוניים \( p_{1},\dots,p_{n} \), המסקנה היא שהמחלק הראשוני היחיד של \( D \) הוא \( 5 \), כלומר \( D=5^{k} \). אבל זה אומר ש-\( p_{1}\cdots p_{n}=5^{k}-1 \), והבעיה היא שאגף ימין פה מתחלק ב-4 ולא משנה מהו \( k \). למה זו בעיה? כי אגף שמאל הוא מכפלה של ראשוניים שכולם שונים זה מזה; אם נחלק את אגף שמאל ב-2 נקבל מספר אי זוגי, בעוד שאגף ימין יישאר זוגי - סתירה.

בטיעון קצת יותר מחוכם שלא אכנס אליו כרגע אפשר להראות שה-2,3,7,43 של תחילת הסדרה הם הראשוניים היחידים עד וכולל 47 שמופיעים בה (כלומר, גם 11 חסר, וגם 13, וכן הלאה). לעת עתה בואו נעבור לעוד הוכחות לקיום אינסוף ראשוניים.

חלק שני, שבו אנחנו עושים אוקלידס קצת אחרת

אז מה בעצם אוקלידס עושה? לוקח את כל \( n \) הראשוניים שמצאנו עד עכשיו, כופל את כולם ומוסיף 1. למה לא פשוט לכפול את כל המספרים מ-1 ועד \( n \) ולהוסיף 1? כלומר, להסתכל על הסדרה שהאיבר הכללי שלה הוא \( n!+1 \) (למי שלא מכיר: מספר טבעי ואחריו סימן קריאה, \( n! \), הוא פשוט קיצור לכפל כל המספרים הטבעיים מ-1 ועד \( n \), למשל \( 4!=1\cdot2\cdot3\cdot4=24 \); זה נקרא עצרת). מובטח לנו שכל מספר \( n!+1 \) אינו יכול להתחלק על ידי ראשוני שקטן מ-\( n \), מאותם שיקולים כמו אצל אוקלידס, ולכן לכל מספר כזה יהיה לנו מחלק ראשוני גדול מ-\( n \). מכיוון שזה עובד לכל \( n \) גדול כרצוננו, בהכרח יש אינסוף ראשוניים (אם יש מספר סופי, קחו \( n \) שגדול מכולם ותראו מה קורה).

כמו קודם, אנחנו תוהים מה קורה אם מסתכלים על סדרת כל הראשוניים שאפשר להפיק בצורה הזו. בואו נסתכל על סדרת הראשוניים שמתקבלים אם לוקחים בכל פעם את הראשוני הקטן ביותר שמחלק את \( n!+1 \). הסדרה הזו מתחילה ב-\( 2,3,7,5,11,7,71,\dots \) כך שכבר אנחנו רואים שראשוני יכול להופיע בה יותר מפעם אחת (7 הוא הראשוני הקטן ביותר שמחלק את \( 3!+1=7 \) וגם את \( 6!+1=721=7\cdot103 \)). השאלה המעניינת יותר היא האם כל ראשוני יופיע בסדרה הזו, וכאן התשובה למרבה השמחה היא חיובית.

ההסבר מדוע זה קורה הוא לא טריוויאלי לחלוטין ואתם יכולים לדלג עליו אם הטרמינולוגיה לא תהיה ברורה לכם. זה נובע מתוצאה נחמדה בתורת המספרים האלמנטרית שנקראת משפט וילסון שאומר שלכל ראשוני \( p \) מתקיים ש-\( \left(p-1\right)!\equiv-1\left(\mbox{mod }p\right) \). דהיינו, ש-\( \left(p-1\right)!+1 \) תמיד יתחלק ב-\( p \). כמובן ש-\( \left(p-1\right)!+1 \) לא יכול להתחלק באף מספר - ראשוני או לא - שקטן מ-\( p \) (כי הוא התקבל ממכפלת כולם ועוד 1) ולכן הראשוני הקטן ביותר שמחלק את \( \left(p-1\right)!+1 \) יהיה \( p \). במילים אחרות, בסדרת הראשוניים שלנו, כל ראשוני \( p \) יופיע במקום \( p-1 \) ולכן כל ראשוני מופיע בה (מה קורה ל-7? המופע הראשון שלו הוא “בטעות”; המופע שהמשפט מבטיח הוא המופע השני).

ייתכן שמסקרן אתכם עכשיו איך מוכיחים את משפט וילסון. הנה הוכחה מיידית למי שמכירים קצת רקע: עבור \( p=2 \) המשפט טריוויאלי אז נניח ש-\( p \) אי זוגי. תבוננו מעל \( \mathbb{Z}_{p} \) על הפולינום \( f\left(x\right)=\left(x-1\right)\left(x-2\right)\cdots\left(x-\left(p-1\right)\right) \). בבירור \( f\left(0\right)=\left(p-1\right)! \) (יש מספר זוגי של מוכפלים ולכן המינוסים מתבטלים). כמו כן, בואו נביט בפולינום \( g\left(x\right)=x^{p-1}-1 \): כאן בבירור \( g\left(0\right)=-1 \). העניין הוא שהשורשים של \( g \) הם בדיוק המספרים \( 1,2,\dots,p-1 \) - זה נובע מהמשפט הקטן של פרמה. לכן \( f \) הוא אותו פולינום כמו \( g \), וסיימנו (שני פולינומים מתוקנים מאותה דרגה עם אותם שורשים הם זהים).

בואו נעבור עכשיו לעוד תעלול שעדיין דומה למה שאוקלידס עשה במובן של “בואו נכפול ראשוניים ונייצר ראשוני חדש”. שוב, בהינתן קבוצת ראשוניים בואו נכפול את כולם ונקבל מספר \( D \). הפעם, במקום להוסיף לו 1, בואו נפרק אותו למכפלה כלשהי, \( D=ab \). בואו ניקח עכשיו ראשוני \( p \) כלשהו מהקבוצה שלנו. הוא חייב לחלק את \( a \) או את \( b \) (אם הוא לא מחלק אף אחד מהם, איך הוא מחלק את \( D \)?) אבל רק אחד מהם (אם הוא היה מחלק את שניהם זה היה אומר שבמכפלה שהניבה את \( D \) אותו \( p \) השתתף איכשהו פעמיים). מכאן שהוא לא יכול לחלק את \( a+b \) (זו מין הכללה של הרעיון לפיו אם \( p \) מחלק את \( a \) הוא לא יכול לחלק את \( a+1 \)). קיבלנו אם כן של-\( a+b \) (שהוא בבירור גדול מ-1) יש גורם ראשוני שלא שייך למכפלה שלנו. דוגמה: אם נכפול את הראשוניים \( 2,3,5 \) נקבל את המספר \( D=30 \), שאפשר לפרק למשל בתור \( 10\cdot3 \), וסכום שני אלו נותן לנו 13, שהוא ראשוני חדש.

חלק שלישי, שבו אוילר פוגש את אוקלידס

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

פונקציית אוילר של מספר טבעי \( n \) שווה למספרם של המספרים שקטנים מ-\( n \) וזרים אליו. שני מספרים הם זרים אם אין להם מחלקים ראשוניים משותפים. למשל, עבור 15 , המספר 6 לא זר אליו (מחלק ראשוני משותף: 3) וגם \( 10 \) לא (מחלק משותף: 5) אבל 14 דווקא כן.

יש ל-\( \varphi \) שתי תכונות חשובות שהופכות אותה לנוחה למדי: ראשית, היא כפלית במובן זה שאם \( a,b \) הם מספרים זרים, אז \( \varphi\left(ab\right)=\varphi\left(a\right)\varphi\left(b\right) \). שנית, אנחנו יודעים בדיוק מה היא מחזירה על ראשוניים: \( \varphi\left(p\right)=p-1 \) (מן הסתם כי כל מספר שקטן מ-\( p \) זר אליו). למעשה, אנחנו יודעים קצת יותר מזה: \( \varphi\left(p^{n}\right)=p^{n}-p^{n-1}=p^{n-1}\left(p-1\right) \) (כי מבין כל \( p^{n} \) המספרים בתחום \( 1,\dots,p^{n} \) אנחנו מעיפים את כל אלו מהצורה \( pa \) כאשר \( 1\le a\le p^{n-1} \)).

פונקציית אוילר שימושית בשלל הקשרים (למשל, בזכות התכונה החשובה ש-\( a^{\varphi\left(n\right)}-1 \) מתחלק ב-\( n \); זו הכללה של המשפט הקטן של פרמה למספרים לא ראשוניים). בהקשר שלנו, אוילר אומר ככה: נניח ש-\( D \) הוא מכפלה של קבוצת ראשוניים, אז \( \varphi\left(D\right)=\prod_{p}\left(p-1\right) \) (ה-\( \Pi \) הזה הוא דרך לכתוב “מכפלת כל האיברים מהצורה \( p-1 \) עבור כל ראשוני \( p \) שמחלק את \( D \)). אם הקבוצה שלנו כוללת לפחות שני ראשוניים אז נקבל ש-\( \varphi\left(D\right) \) הוא גדול מ-2. לכן יש מספר זר ל-\( D \) שהוא גדול מ-1; למספר הזה צריך להיות מחלק ראשוני שאיננו מחלק את \( D \), והופס קיבלנו שוב ראשוני חדש.

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

ההוכחה של אוילר שהצגתי התבססה על ספירה של מספרים זרים שקטנים מ-\( D \). עכשיו אני רוצה לקחת את זה קדימה ולשכוח סוף סוף מהשיטה האוקלידית של לכפול קבוצה קיימת של ראשוניים. תחת זאת, כדי להראות שיש אינסוף ראשוניים, מספיק לי להראות סדרה אינסופית של מספרים זרים. דהיינו, סדרה \( a_{1},a_{2},a_{3},\dots \) שאין לאף זוג מספרים בה גורם ראשוני משותף. מן הסתם קיום סדרה שכזו מוכיח קיום של סדרה בת אינסוף ראשוניים, כי קחו מחלק ראשוני לכל איבר בסדרה. מצד שני, על פניו נראה שעברנו לבעיה קשה יותר - צריך יהיה הרי להוכיח שכל זוג איברים בסדרה הזו זרים. כמובן, עם בחירה נכונה של אברי הסדרה, זה יהיה קל יחסית. או לפחות מעניין. אני הולך להציג שתי סדרות כאלו: של מספרי פרמה ושל מספרי פיבונאצ'י (רגע! מספרי פיבונאצ’י לא זרים זה לזה! אל תדאגו, נגיע לכך).

נתחיל עם פרמה. מספרי פרמה הם מספרים מהצורה \( F_{n}=2^{2^{n}}+1 \). הסדרה של מספרי פרמה מתחילה עם \( F_{0}=3 \) וממשיכה כך: \( 3,5,17,257,65537,\dots \). מהשלוש נקודות ואילך המספרים הם מפלצתיים בגודלם וקשה להתעסק איתם. מה שמעניין הוא שחמשת המספרים שכתבתי הם ראשוניים. זה גרם לפרמה להעלות את ההשערה שכל מספרי פרמה הם ראשוניים, אבל אוילר הצליח להראות שכבר המספר הבא בסדרה אינו ראשוני. למעשה, כל המספרים הבאים בסדרה עד המספר במקום ה-32 הם לא ראשוניים, אם כי אנחנו אפילו לא יודעים פירוק מלא לגורמים של רובם. אלו פשוט מספרים כל כך גדולים שקשה להתעסק איתם. כמובן, השאלה אם יש עוד ראשוניים בהמשך הסדרה היא תעלומה, כמו גם השאלה הקשה יותר האם יש בהמשך הסדרה אינסוף ראשוניים.

לצרכנו התעלומות הללו לא חשובות; מספיק יהיה להראות שכל שני מספרי פרמה שונים הם זרים. התעלול פה הוא פשוט מאוד. בואו נסתכל על \( F_{n}-2=2^{2^{n}}-1 \). עכשיו, עוד מבית הספר כולנו לומדים להכיר ולאהוב את הזהות \( x^{2}-1=\left(x-1\right)\left(x+1\right) \) וכשאני רואה ביטוי כמו \( 2^{\left(2^{n}\right)}-1 \) אפילו לי זה קופץ לעיניים. במקרה שלנו, הפירוק הוא \( 2^{2^{n}}-1=\left(2^{2^{n-1}}-1\right)\left(2^{2^{n-1}}+1\right)=\left(2^{2^{n-1}}-1\right)F_{n-1} \), כלומר אנחנו רואים ש-\( F_{n-1} \) מחלק את \( F_{n}-2 \). לכן בוודאי ש-\( F_{n-1} \) זר ל-\( F_{n} \) (הגורם היחיד שהיה יכול להיות משותף לשניהם הוא 2, אבל מספר פרמה הוא תמיד אי זוגי).

את הרעיון הזה אפשר להכליל יחסית בקלות. שימו לב שראינו ש-\( 2^{2^{n}}-1 \) מתחלק ב-\( 2^{2^{n-1}}-1 \). באותו האופן מראים ש-\( 2^{2^{n-1}}-1 \) מתחלק ב-\( 2^{2^{n-2}}-1 \) וכן הלאה וכן הלאה - לכל \( k<n \) אפשר להראות ש-\( 2^{2^{n}}-1 \) מתחלק ב-\( 2^{2^{k}}-1 \). כעת, מכיוון ש-\( F_{k} \) מחלק את \( 2^{2^{k+1}}-1 \) נקבל מכך שלכל \( k<n \) מתקיים ש-\( F_{k} \) מחלק את \( F_{n}-2 \) ולכן זר לו.

בואו נעבור עכשיו אל פיבונאצ’י. מספרי פיבונאצ’י, שכדי לבלבל אתכם אסמן גם אותם ב-\( F_{n} \) (מה לעשות? זה הסימון הסטנדרטי!) הם סדרת מספרים שמתחילה ב-1,1 ומכאן ואילך כל מספר שווה לסכום שני קודמיו: \( F_{1}=F_{2}=1 \) ו-\( F_{n}=F_{n-1}+F_{n-2} \) לכל \( n>2 \). מקבלים את הסדרה \( 1,1,2,3,5,8,13,21,\dots \). זו אחת מהסדרות המפורסמות במתמטיקה, אם לא המפורסמת שבהם; כל כך מפורסמת עד שאם חלק ממנה צץ באיזה שהוא מקום, מייד עטים לא-מתמטיקאים עליו ומחפשים בכך משמעות מיסטית. הפעם אני רוצה להשתמש בה באופן מתמטי למהדרין, אבל יש לי בעיה קטנה - כפי שקל לראות, אברי הסדרה לא דווקא זרים אלו לאלו (2 לא זר ל-8; ו-3 לא זר ל-21, וכן הלאה).

אז מה עושים? מסתבר שאפשר להסתפק בפחות. לא חייבים שכל זוג מספרי פיבונאצ’י יהיו זרים; מספיק שרק מספרי פיבונאצ’י שהאינדקסים שלהם זרים יהיו זרים. כך למשל אצלנו \( F_{3}=2 \) ו-\( F_{6}=8 \), וכאן האינדקסים \( 3,6 \) לא זרים, אז אין בעיה עם כך שגם מספרי הפיבונאצ’י לא זרים; ובדומה עם \( F_{4}=3 \) ו-\( F_{8}=21 \).

אז יש לנו שתי שאלות כאן. ראשית, למה אפשר להסתפק בכך שרק מספרים עם אינדקס זר הם זרים. שנית, למה מספרי פיבונאצ’י מקיימים את התכונה הזו. נתחיל מהשאלה הראשונה, שהיא קלה. נניח שיש רק מספר סופי של ראשוניים, \( p_{1},\dots,p_{k} \). נסתכל על אברי הסדרה באינדקסים המתאימים, \( F_{p_{1}},\dots,F_{p_{k}} \). אנחנו יודעים שכל האיברים הללו זרים, כלומר מתחלקים על ידי ראשוניים שונים. ייתכן, אמנם, שאחד מהמספרים הללו הוא 1 שלא מתחלק בכלל על ידי ראשוניים; זה אומר שיש לנו לפחות \( k-1 \) ראשוניים שונים שמחלקים את יתר אברי הסדרה. זה אומר שאם נצליח להראות שני איברים בסדרה הזו שהם בעלי לפחות שני מחלקים ראשוניים שונים, בסך הכל יהיו לנו לפחות \( k+1 \) ראשוניים שונים וזו סתירה להנחה שיש רק \( k \). את התכונה הזו - מספרי פיבונאצ’י מאינדקס ראשוני עם לפחות שני מחלקים - קל להדגים במפורש: \( F_{19}=4181=113\cdot37 \) ו-\( F_{31}=1346269=557\cdot2417 \).

נשאר אם כן רק להראות שאם \( a \) זר ל-\( b \) אז \( F_{a} \) זר ל-\( F_{b} \). ההוכחה תהיה קצת טכנית ושוב - אתם מוזמנים לקפוץ מעליה אם זה יהיה יותר מדי. נתחיל מהמקרה הקל ביותר: זה של \( F_{n} \) ו-\( F_{n-1} \). מכיוון ש-\( F_{n}=F_{n-1}+F_{n-2} \) הרי ש-\( F_{n}-F_{n-1}=F_{n-2} \) ולכן אם היה מספר שמחלק בו זמנית את \( F_{n} \) ו-\( F_{n-1} \) הוא היה מחלק גם את \( F_{n-2} \) ואפשר היה להמשיך ככה עד שהיינו מקבלים מחלק של \( F_{2}=1 \) וזה כמובן אפשרי רק אם המחלק הזה הוא 1. לכן \( F_{n} \) זר ל-\( F_{n-1} \).

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

\( F_{n}=F_{n-1}+F_{n-2} \)

עכשיו בואו נחליף את \( F_{n-1} \) בהגדרה הרקורסיבית שלו:

\( F_{n}=\left(F_{n-2}+F_{n-3}\right)+F_{n-2} \)

כלומר, קיבלנו:

\( F_{n}=2F_{n-2}+F_{n-3} \)

עכשיו שוב: נחליף את \( F_{n-2} \) בהגדרה שלו, ונקבל

\( F_{n}=2\left(F_{n-3}+F_{n-4}\right)+F_{n-3} \)

כלומר

\( F_{n}=3F_{n-3}+2F_{n-4} \)

האם אתם מתחילים להרגיש תבנית? לא? אז עוד צעד:

\( F_{n}=3\left(F_{n-4}+F_{n-5}\right)+2F_{n-4} \)

כלומר

\( F_{n}=5F_{n-4}+3F_{n-5} \)

עכשיו תסתכלו על המקדמים שמופיעים בכל שלב: גם זו סדרת פיבונאצ’י, רק עולה!

באופן כללי, אפשר לכתוב את המשוואה

\( F_{n}=a_{k}F_{n-k}+b_{k}F_{n-k-1} \)

כאשר \( a_{k},b_{k} \) הם מקדמים. אחרי שפותחים עוד שלב במשוואה הזו, מקבלים

\( F_{n}=\left(a_{k}+b_{k}\right)F_{n-k-1}+a_{k}\left(F_{n-k-2}\right) \)

כלומר, \( b_{k+1} \) הוא \( a_{k} \) ואילו \( a_{k+1} \) הוא \( a_{k}+b_{k}=a_{k}+a_{k-1} \) - כלומר, יש לנו כאן את סדרת פיבונאצ’י שוב, רק בסדר הפוך. אנחנו מקבלים את הנוסחה הנפלאה הבאה:

\( F_{n}=F_{k+1}F_{n-k}+F_{k}F_{n-k-1} \)

שאני מקווה שהיא קצת יותר ברורה עכשיו מאשר אם סתם הייתי מצניח אותה עליכם. מה הנוסחה הזו מלמדת אותנו? שאם \( d \) הוא מחלק משותף של \( F_{n} \) ושל \( F_{k} \) אז הוא גם מחלק את \( F_{k+1}F_{n-k} \). עכשיו, מכיוון ש-\( d \) מחלק את \( F_{k} \) ואנחנו יודעים ש-\( F_{k} \) זר ל-\( F_{k+1} \) לא ייתכן ש-\( d \) מחלק את \( F_{k+1} \) ולכן הוא בהכרח מחלק את \( F_{n-k} \). אפשר להמשיך באותו האופן ולקבל ש-\( d \) מחלק גם את \( F_{n-2k} \) וכן הלאה וכן הלאה עד שבסוף מקבלים ש-\( d \) מחלק את \( F_{n\mbox{ mod }k} \), כלומר את מספר פיבונאצ’י שהאינדקס שלו מתאים לשארית החלוקה של \( n \) ב-\( k \).

נסכם: לכל \( n,k \) אפשר לחלק את \( n \) ב-\( k \) ולקבל את התוצאה \( n=qk+r \) כאשר השארית \( r \) מקיימת \( 0\le r<k \). כעת, ממה שראינו לעיל, אם \( d \) הוא מחלק משותף של \( F_{n} \) ושל \( F_{k} \) אז הוא גם מחלק משותף של \( F_{k} \) ושל \( F_{r} \). עכשיו אפשר להמשיך את זה: לחלק את \( k \) ב-\( r \), לקבל שארית חדשה, \( d \) יהיה מחלק גם של מספר פיבונאצ’י שמתאים לה, וכדומה. מתי המשחק הזה נעצר? ובכן, אם \( n \) זר ל-\( k \), המשחק הזה ייעצר רק כשנגיע ל-1, דהיינו נקבל ש-\( d \) הוא מחלק של \( F_{1}=1 \) ולכן \( d=1 \). כל זה קצת מסורבל אבל למי שמכיר את המושגים הרלוונטיים אין כאן שום דבר קשה.

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

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

הברחתי את כל מי שצריך? יפה, אז בואו נראה הוכחה עוד יותר טכנית, אבל עם רעיון ממש טריוויאלי בבסיסה. הרעיון הוא לספור כמה מספרים חופשיים מריבועים יש בין 1 ל-\( n \). מספר הוא חופשי מריבועים אם הוא לא מתחלק על ידי ריבוע של אף מספר טבעי גדול מ-1. בניסוח שקול, מספר הוא חופשי מריבועים אם כשמפרקים אותו לראשוניים מקבלים מכפלה שבה כל הראשוניים שונים זה מזה. מה שאנחנו הולכים להראות הוא שבין 1 ל-\( n \) יש לפחות \( \frac{n}{4} \) מספרים חופשיים מריבועים. בפרט, המסקנה מכך היא שמספרם של המספרים החופשיים מריבועים איננו חסום. זה מספיק. למה זה מספיק? כי נניח שהיו לנו רק \( k \) ראשוניים. כמה מספרים חופשיים מריבועים היינו יכולים לבנות בעזרתם? לכל ראשוני היו לנו רק שתי אפשרויות: או שהוא משתתף במכפלה שמגדירה את המספר, או שלא. זה נותן לנו בסך הכל \( 2^{k} \) מספרים אפשריים שהם חופשיים מריבועים. עבור \( n \) גדול מספיק, \( 2^{k}<\frac{n}{4} \) וזו סתירה.

כדי להוכיח שיש לפחות \( \frac{n}{4} \) מספרים חופשיים מריבועים, בואו נוכיח שיש לכל היותר \( \frac{3}{4}n \) מספרים בין 1 ל-\( n \) שמתחלקים על ידי ריבוע. כמה מספרים מתחלקים על ידי 4 בין 1 ל-\( n \)? זה קל, \( \frac{n}{4} \). ליתר דיוק, המספר הזה עשוי להיות שבר אז צריך לעגל אותו למטה: \( \left[\frac{n}{4}\right] \). וכמה מתחלקים על ידי 9? \( \left[\frac{n}{9}\right] \), וכן הלאה. עכשיו, המספר 36 למשל מתחלק גם על ידי 4 וגם על ידי 36, אז יש סכנה שנספור אותו פעמיים. לכן מה שאנחנו מוצאים יהיה חסם מלעיל על מספר המספרים שאינם חופשיים מריבועים ולא המספר המדויק. והנה החסם הזה: \( \sum_{k=2}^{n}\left[\frac{n}{k^{2}}\right] \).

עכשיו נעשה שרשרת קטנה של תעלולים כדי לקבל חסם טוב על זה:

\( \sum_{k=2}^{n}\left[\frac{n}{k^{2}}\right]<n\left(\frac{1}{4}+\sum_{k=3}^{\infty}\frac{1}{k^{2}}\right)\le n\left(\frac{1}{4}+\int_{2}^{\infty}\frac{dt}{t^{2}}\right)=\frac{3}{4}n \)

המעבר השני מתקבל מכך שאנחנו מסירים את הערך התחתון, כותבים בצד במפורש את האיבר הראשון בסכום, ומוסיפים עוד איברים חיוביים לסכום. המעבר שאחריו קצת יותר מחוכם, אם כי כנראה טבעי למי שרגילים לאנליזה: הרעיון הוא שאם ניקח סכום רימן לאינטגרל \( \int_{2}^{\infty}\frac{dt}{t^{2}} \) עם החלוקה \( \left[2,3\right],\left[3,4\right],\left[4,5\right],\dots \), הרי שהסכום באגף שמאל תמיד יהיה קטן או שווה מסכום הרימן הזה, כי הוא מתקבל מכך שבוחרים מכל קטע את הקצה הימני שלו - האיבר שמחזיר את הערך הנמוך ביותר האפשרי של הפונקציה באותו הקטע. המעבר האחרון הוא פשוט חישוב האינטגרל: \( \int_{2}^{\infty}\frac{dt}{t^{2}}=\lim_{n\to\infty}\left[-\frac{1}{t}\right]_{2}^{n}=\lim_{n\to\infty}\left(\frac{1}{2}-\frac{1}{n}\right)=\frac{1}{2} \) .

הנה עוד טיעון ספירה דומה, שמבחינות מסויימות הוא פשוט יותר ומבחינות מסויימות מסובך יותר. נניח שיש לנו רק \( k \) ראשוניים. אז לכל מספר טבעי \( n \) אפשר לכתוב \( n=\prod_{i=1}^{k}p_{i}^{\alpha_{i}} \). בואו ניקח לוגריתם על בסיס 2 (מה שמסומן \( \lg \)) על שני האגפים, ונקבל \( \lg n=\sum_{i=1}^{k}\alpha_{i}\lg p_{i}\ge\sum_{i=1}^{k}\alpha_{i} \) כשהמעבר האחרון נובע מכך שהראשוני הקטן ביותר הוא 2. במילים אחרות, קיבלנו חסם טריוויאלי על האקספוננטים בפירוק לגורמים של \( n \) - הם לא יכולים להיות גדולים מ-\( \lg n \).

עכשיו בואו נסתכל על הקטע \( \left[1,N\right] \). כל מספר בו קטן או שווה ל-\( N \) ולכן האקספוננטים בפירוק לגורמים של כל מספר בקטע הזה לא יכולים להיות גדולים מ-\( \lg N \). על כן, כל מספר בקטע הזה מתקבל מבחירה, עבור כל \( 1\le i\le k \), של אקספוננט שהוא מספר בין 0 ובין \( \lg N \). לכן יש לנו לכל היותר \( \left(\lg N+1\right)^{k} \) מספרים בקטע. המסקנה היא ש-\( N\le\left(\lg N+1\right)^{k} \) לכל \( N \). עכשיו נכנס לתמונה שיקול סטנדרטי על כך שפונקציה לינארית ב-\( N \) גדלה מהר יותר מכל פולינום ב-\( \lg N \) ולכן עבור \( N \) גדול דיו אי השוויון הזה הוא בלתי אפשרי.

חלק שישי שבו פתאום נכנסת טופולוגיה לתוך העסק

הנה הוכחה בלתי קשורה בעליל לכל מה שעשינו עד כה, ומסתמכת על תוצאות בסיסיות בטופולוגיה קבוצתית. זו הוכחה די מדהימה לטעמי, ולכן כבר הקדשתי לה פוסט. כאן אסתפק בלתת קרדיט להלל פורסטנברג שהמציא אותה, ולתאר אותה בקווים כלליים למי שכבר מכיר את המושגים: אנחנו מגדירים טופולוגיה על \( \mathbb{Z} \) עם בסיס שהוא אוסף כל הסדרות החשבוניות. קל להראות שכל קבוצות הבסיס הן סגורות. כעת נביט באיחוד כל הסדרות החשבוניות עם איבר ראשון 0 והפרש \( p \) ראשוני. כל מספר פרט ל-1 ומינוס 1 מתחלק על ידי ראשוני ולכן שייך לאחד מהסדרות הללו. המסקנה היא שהמשלים של איחוד כל הסדרות הללו הוא הקבוצה \( \left\{ 1,-1\right\} \). הקבוצה הזו סופית ולכן לא יכולה להיות פתוחה (כל אברי הבסיס הם קבוצות אינסופיות). ולכן המשלימה שלה לא יכולה להיות סגורה. מה המשלימה? איחוד של קבוצות סגורות. הדרך היחידה שבה האיחוד הזה לא יהיה סגור היא אם האיחוד הוא אינסופי, דהיינו יש אינסוף ראשוניים. וואו וואו וואו.

חלק שביעי שבו אנחנו מגיעים להוכחה העיקרית של אוילר והכיף מתחיל

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

אז בואו נראה קודם כל מה אוילר עשה, ואז נראה איך קרונקר תיקן את הרעיון.

המטרה של אוילר הייתה להוכיח שהמכפלה \( \prod_{p}\frac{p}{p-1} \) שנלקחת על כל הראשוניים היא אינסופית (במונחים מודרניים, “שואפת לאינסוף”, אבל תשכחו מזה - בואו נהיה אוילר לרגע ונזניח את הדיוק המתמטי לטובת הרעיון). מן הסתם ינבע מכך שיש אינסוף ראשוניים כי מכפלה סופית של מספרים ממשיים היא סופית. כבר כאן אנחנו רואים את הגאונות - זו גישה שונה לחלוטין מהגישה של אוקלידס.

האופן שבו אוילר מוכיח את זה הוא כך: נניח שאנחנו מכירים את הטור ההרמוני, \( 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots=\sum_{n=1}^{\infty}\frac{1}{n} \). בואו נסמן את סכום הטור הזה ב-\( x=\sum_{n=1}^{\infty}\frac{1}{n} \). האם \( x=137 \)? ובכן, לא. אפשר להוכיח (לא אעשה זאת כאן, אבל עשיתי זאת בעבר ושם גם הוסבר עניין ה-137) שה-\( x \) הזה הוא אינסוף. לכן, אומר אוילר, אם נוכיח ש-\( x\cdot\left(\prod_{p}\frac{p}{p-1}\right)^{-1}=1 \) בהכרח נובע מכך ש-\( \prod_{p}\frac{p}{p-1} \) אינסופי (כי אם היה סופי, גם ההופכי שלו היה סופי, ומספר סופי כפול אינסוף זה אינסוף).

כדי להגיע לשוויון הזה ל-1, אוילר מבצע מניפולציות משעשעות ביותר על הטור ההרמוני כדי למחוק ממנו איברים. אם \( x=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots \) אז כשנכפול את זה בחצי, נקבל \( \frac{1}{2}x=\frac{1}{2}+\frac{1}{6}+\frac{1}{8}+\dots \) ולכן ההפרש, \( \frac{1}{2}x=x-\frac{1}{2}x=1+\frac{1}{3}+\frac{1}{5}+\dots \) שווה לסכום כל ההופכיים של מספרים אי-זוגיים; נפטרנו מכל הזוגיים.

השלב הבא הוא מן הסתם לחלק את \( \frac{1}{2}x \) ב-3 ולחסר מ-\( \frac{1}{2}x \), כדי להעלים מהסכום את כל ההופכיים של מספרים שמתחלקים ב-3. מקבלים:

\( \frac{1}{2}\left(x-\frac{1}{3}x\right)=\frac{1\cdot2}{2\cdot3}x=1+\frac{1}{5}+\frac{1}{7}+\dots \)

הבא בתור יהיה 5, ואחר כך 7, ואחר כך 11… אתם רואים את הרעיון? זה למעשה שימוש יצירתי בכברה של ארטוסתנס, שהיא אלגוריתם שמייצר את כל הראשוניים באופן הבא: מתחילים עם כל הטבעיים שגדולים מ-1. בכל שלב, המספר הראשון שטרם טיפלנו בו הוא ראשוני; מוסיפים אותו לרשימת הראשוניים שלו, ואז מוחקים את כל הכפולות שלו מהרשימה. ואז שוב, המספר הבא שטרם נמחק יהיה ראשוני, ונמחק את הכפולות שלו, וכן הלאה וכן הלאה.

אצל אוילר בסופו של דבר יימחקו כל המספרים באגף ימין שאינם 1, ומה נקבל באגף שמאל? מכפלה של כל הגורמים מהצורה \( \frac{p-1}{p} \) עבור \( p \) ראשוני. כלומר, קיבלנו \( \left(\prod_{p}\frac{p-1}{p}\right)x=1 \), כמבוקש. זה מסיים את ההוכחה, למעט העובדה שביצענו פה המון מניפולציות על טורים מתבדרים שלא הכי ברור איך אפשר להצדיק אותן.

אז הנה מה שקרונקר עושה. קרונקר מסתמך על העובדה שהטור ההרמוני אמנם מתבדר, אבל אם “נזוז טיפה הצידה” נקבל משהו שמתכנס. התוצאה המתמטית הרלוונטית היא זו: הטור \( \sum_{n=1}^{\infty}\frac{1}{n^{s}} \) מתכנס לכל \( s>1 \) ומתבדר לכל \( s\le1 \). כלומר, \( s=1 \) (המקרה של הטור ההרמוני) הוא בדיוק “על הגבול”. לכן אפשר לדבר על פונקציה שמקבלת ערכים ממשיים לכל \( s>1 \) ולעבוד עם הפונקציה הזו. נסמן אותה \( \zeta\left(s\right)=\sum_{n=1}^{\infty}\frac{1}{n^{s}} \). הפונקציה הזו נקראת פונקציית הזיטא של רימן, אם כי צריך להיזהר כאן קצת; רימן בא הרבה אחרי אוילר, וכבר אוילר התעסק עם הפונקציה הזו; הגדולה של רימן הייתה בכך שהוא הרחיב את הפונקציה הזו למספרים המרוכבים ועשה בה שימושים מרהיבים שלא אציג כרגע אבל גם הם קשורים למספרים ראשוניים.

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

\( \zeta\left(s\right)=\prod_{p}\frac{1}{1-p^{-s}} \)

כאן אגף שמאל של המשוואה שואף לאינסוף כש-\( s \) שואף ל-1, ולכן גם אגף ימין, כך שמייד ברור שהנוסחה מוכיחה קיום של אינסוף ראשוניים. אם נציב \( s=1 \) בגורם \( \frac{1}{1-p^{-s}} \) נקבל \( \frac{1}{1-\frac{1}{p}}=\frac{p}{p-1} \), כך שבעצם יש לנו פה את ההוכחה המקורית של אוילר בתחפושת. גם ההוכחה של הנוסחה הזו היא בעצם ההוכחה המקורית של אוילר, רק שעכשיו בגלל ש”זזנו קצת” אנחנו עובדים עם סכומים מתכנסים וכל מה שנעשה יהיה חוקי. ניקח \( s>1 \). נסמן \( A=\zeta\left(s\right)=1+\frac{1}{2^{s}}+\frac{1}{3^{s}}+\dots \). ועכשיו במקום לחלק ב-2 נחלק ב-\( 2^{s} \) ונחסיר. נקבל

\( A-\frac{1}{2^{s}}A=\left(\frac{2^{s}-1}{2^{s}}\right)A=1+\frac{1}{3^{s}}+\frac{1}{5^{s}}+\dots \)

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

\( A\left(\frac{2^{s}-1}{2^{s}}\right)\left(\frac{3^{s}-1}{3^{s}}\right)\cdots=1 \)

כלומר, את הנוסחה \( A\cdot\prod_{p}\frac{p^{s}-1}{p^{s}}=A\cdot\prod_{p}\left(1-p^{-s}\right)=1 \) ומכאן ש-\( A=\prod_{p}\frac{1}{1-p^{s}} \), כנדרש.

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