הצגת המקור של הדף "קיומם של אינסוף מספרים ראשוניים"

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

== הוכחתו של אוקלידס ==

'''משפט''': בין ה[[מספר טבעי|מספרים הטבעיים]] ישנם אינסוף ראשוניים.

'''הוכחה'''{{הערה|את ההוכחה המופיעה ב[[יסודות (ספר)|יסודות]], טענה IX.20, אפשר למצוא [http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.html כאן].}}: ב[[אינדוקציה מתמטית|אינדוקציה]], אפשר לראות שכל [[מספר טבעי]] גדול מ-1 מתחלק במספר ראשוני.
[[הוכחה בדרך השלילה|נניח בשלילה]] שיש רק מספר סופי של ראשוניים: <math>p_1, \ldots, p_n</math>. נסתכל במספר <math>\ N = p_1 \cdot p_2 \cdots p_n + 1</math>. ברור שמספר זה לא מתחלק באף p<sub>i</sub> כי לכל [[חילוק|חלוקה]] כזאת ה[[שארית (חילוק)|שארית]] היא 1. על-כן, N אינו מתחלק באף מספר ראשוני, בסתירה לכך ש- N>1.

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

מההוכחה אפשר להסיק שקיימים לפחות <math>\ \log_2\log_2(x)</math> ראשוניים הקטנים מ-<math>x</math>. [[חסם (מתמטיקה)|חסמים]] טובים יותר, כמו זה המתקבל מ[[משפט המספרים הראשוניים]], דורשים מאמץ גדול בהרבה.

== הוכחתם של אוילר וקרונקר ==
ב-[[1737]] ניסח [[לאונרד אוילר|אוילר]] את השוויון (הבעייתי, כפי שיוסבר מיד)
<math>\ \sum_{n=1}^{\infty} \frac{1}{n} = \prod_{p}\left(1-\frac{1}{p}\right)^{-1}</math>. באגף שמאל מופיע [[הטור ההרמוני]], ה[[טור מתבדר|מתבדר]] לאינסוף; לכן המכפלה באגף ימין (העוברת על כל הראשוניים) מוכרחה להיות אינסופית – ומכאן שיש אינסוף ראשוניים.

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

ב-[[1899]] הציע המתמטיקאי J. Braun הוכחה אחרת המבוססת על מכפלת אוילר: אם מציבים בשוויון לעיל <math>\ s=2</math>, מתקבל באגף שמאל <math>\ \frac{\pi^2}{6}</math> (ראו [[בעיית בזל]]), ומכיוון ש[[פאי]] בריבוע אינו [[מספר רציונלי|רציונלי]], המכפלה באגף ימין מוכרחה להיות אינסופית.

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

נתבונן ב[[חוג המספרים השלמים|קבוצת המספרים השלמים]] <math>\ \mathbb{Z}</math> עם ה[[טופולוגיה פרו-סופית|טופולוגיה הפרו-סופית]]: הקבוצה הופכת ל[[מרחב טופולוגי]] על ידי בחירת ה[[בסיס לטופולוגיה|בסיס]] הכולל את כל הסדרות החשבוניות, <math>\ a\mathbb{Z}+b</math> (זהו בסיס, מכיוון שהחיתוך של שתי סדרות חשבוניות הוא סדרה חשבונית). ה[[משלים (תורת הקבוצות)|משלים]] של כל סדרה חשבונית הוא [[איחוד (מתמטיקה)|איחוד]] של מספר סופי של סדרות חשבוניות (בעלות אותו הפרש), ולכן כל סדרה חשבונית מהווה גם [[קבוצה סגורה]].

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

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

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

ב-[[1896]] הוכיחו [[ז'אק אדמר|אדמר]] ו[[שארל דה לה ואלה פוסן|ואלה פוסן]] (באופן בלתי תלוי) את [[משפט המספרים הראשוניים]] הקובע כי מספר הראשוניים הקטנים מ-n [[אסימפטוטי]] ל-<math>\ \frac{n}{\ln(n)}</math>. המשפט קובע את קצב בו עולה מספר הראשוניים לאינסוף.

[[השערת ברטראן]] קובעת שלכל n טבעי ישנו מספר ראשוני בין n ל-2n. את ההשערה הוכיח [[פפנוטי צ'בישב]] בשנת [[1850]].

== מקורות ==
<div style="direction: ltr;">
* L.E.Dickson, '''History of the Theory of Numbers,''' Vol. 1, Chapter XVIII: theory of prime numbers.
</div>

== קישורים חיצוניים ==
* {{דוידסון|ארז גרטי|מספרים ראשוניים – אבני היסוד של המתימטיקה|maagarmada/math_and_comp/מספרים-ראשוניים-–-אבני-היסוד-של-המתימטיקה|11 ביולי 2011}}
* {{לא מדויק|187|ההוכחה הטופולוגית לקיום אינסוף ראשוניים}}
* {{לא מדויק|194|הוכחת אוילר לקיום אינסוף ראשוניים}}
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים|יישור=ימין}}

[[קטגוריה:מספרים ראשוניים]]
[[קטגוריה:משפטים בתורת המספרים]]
[[קטגוריה:הוכחות]]
[[קטגוריה:לאונרד אוילר]]
[[קטגוריה:אוקלידס]]