קיומם של אינסוף מספרים ראשוניים

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים

1 הוכחתו של אוקלידס
2 ראשוניים בסדרות חשבוניות
3 הוכחתם של אוילר וקרונקר
4 ההוכחה הטופולוגית של פורסטנברג
5 ראו גם
6 מקורות

[עריכה] הוכחתו של אוקלידס

משפט: בין המספרים הטבעיים, ישנם אינסוף ראשוניים.

הוכחה: באינדוקציה, אפשר לראות שכל מספר טבעי גדול מ-1 מתחלק במספר ראשוני. נניח בשלילה שיש רק מספר סופי של ראשוניים: $p_1, \cdots, p_n$ . נסתכל במספר $\ N = p_1 \cdot p_2 \cdot ... \cdot p_n + 1$ . ברור שמספר זה לא מתחלק באף p_i כי לכל חלוקה כזאת השארית היא 1. על-כן, N אינו מתחלק באף מספר ראשוני, בסתירה לכך ש- N>1.

הוכחה זו מציעה אלגוריתם לבניית סדרה של מספרים ראשוניים: בהינתן הראשוניים $\ p_1,\dots,p_n$ , הראשוני הבא, $\ p_{n+1}$ , מוגדר בתור הגורם הראשוני הקטן ביותר של $\ N= p_1\dots p_n+1$ . הסדרה המתקבלת, שאבריה הראשונים הם 2, 3, 7, 43, 13, 53, 5 ו- 6221671, נקראת סדרת אוקלידס-מולין.

מההוכחה אפשר להסיק שקיימים לפחות $\ \log_2\log_2(x)$ ראשוניים הקטנים מ- x. חסמים טובים יותר, כמו זה המתקבל ממשפט המספרים הראשוניים, דורשים מאמץ גדול בהרבה.

[עריכה] ראשוניים בסדרות חשבוניות

את ההוכחה של אוקלידס אפשר לשנות בקלות יחסית, כדי להראות שקיימים אינסוף ראשוניים בסדרות חשבוניות מסוימות. כך למשל, אם מתבוננים במספר $\ N=4p_1\cdot\dots\cdot p_n -1$ אפשר להוכיח שקיימים אינסוף ראשוניים המשאירים שארית 3 בחלוקה ל-4. הוכחות אלמנטריות מטיפוס זה מאפשרות לטפל בעיקר בסדרות מהצורה $\ an+1$ או $\ an+(a-1)$ (אדוארד לוקאס נעזר בסדרות לוקאס כדי להוכיח שיש אינסוף מספרים ראשוניים מהצורה $\ 5n+2$ ומהצורה $\ 8n+5$ ). שיטות אלה אינן די חזקות להוכיח שקיימים אינסוף ראשוניים בכל סדרה חשבונית בה האיבר הראשון והפרש הסדרה הם מספרים טבעיים זרים, תוצאה הנובעת ממשפט דיריכלה (1837).

[עריכה] הוכחתם של אוילר וקרונקר

ב-1748 ניסח אוילר את השוויון (הבעייתי, כפי שיוסבר מיד) $\ \sum_{n=1}^{\infty} \frac{1}{n} = \prod_{p}\left(1-\frac{1}{p}\right)^{-1}$ . באגף שמאל מופיע הטור ההרמוני, המתבדר לאינסוף; לכן המכפלה באגף ימין (העוברת על כל הראשוניים) מוכרחה להיות אינסופית - ומכאן שיש אינסוף ראשוניים.

בקורס שהעביר קרונקר בשנים 6-1875, הוא הצביע על הבעייתיות שבהשוואת שני ביטויים אינסופיים, והחליף את הנוסחה במכפלת אוילר של פונקציית זטא: $\ \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p}\left(1-\frac{1}{p^s}\right)^{-1}$ , המתארת שוויון בין שני ביטויים מוגדרים היטב כאשר $\ s>1$ הוא פרמטר ממשי. כעת הראה קרונקר שהגבול באגף שמאל, כאשר s שואף ל-1 מלמעלה, הוא אינסופי - אבל אילו היה מספר הראשוניים סופי, הגבול באגף ימין היה צריך להיות סופי. זוהי הדרך להפוך את טיעונו של אוילר להוכחה קבילה.

ב-1899 הציע המתמטיקאי J. Braun הוכחה אחרת המבוססת על מכפלת אוילר: אם מציבים בשוויון לעיל $\ s=2$ , מתקבל באגף שמאל $\ \frac{\pi^2}{6}$ , ומכיוון שפאי אינו רציונלי, המכפלה באגף ימין מוכרחה להיות אינסופית.

[עריכה] ההוכחה הטופולוגית של פורסטנברג

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

נהפוך את קבוצת המספרים השלמים $\ \mathbb{Z}$ למרחב טופולוגי, על ידי בחירת הבסיס הכולל את כל הסדרות החשבוניות, $\ a\mathbb{Z}+b$ (זהו בסיס, מכיוון שהחיתוך של שתי סדרות חשבוניות הוא סדרה חשבונית). המשלים של כל סדרה חשבונית הוא איחוד של מספר סופי של סדרות חשבוניות (בעלות אותו הפרש), ולכן כל קבוצה פתוחה מהווה גם קבוצה סגורה.

מכיוון שלכל מספר שלם, פרט ל- $\ \pm 1$ , יש גורם ראשוני, האיחוד $\ \cup p\mathbb{Z}$ העובר על כל הראשוניים, שווה לקבוצה $\ \mathbb{Z} - \{\pm 1\}$ . אם מספר הראשוניים היה סופי, זה היה איחוד של מספר סופי של קבוצות סגורות, ולכן הוא קבוצה סגורה; ואם כך, המשלים שלה, $\ \{\pm 1\}$ , הוא קבוצה פתוחה. אבל זו קבוצה סופית, שהיא קטנה מכדי להכיל סדרה חשבונית, ולכן אינה יכולה להיות פתוחה - בסתירה להנחה.