מספרים מושלמים וראשוניי מרסן

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

הסיפור שלנו מתחיל עם האופן שבו אנחנו אוהבים לקחת מספרים טבעיים ולפרק להם את הצורה לגורמים. כלומר, למצוא מספרים שמחלקים אותם ולהציג את המכפלות הללו. למשל, את 36 אפשר לפרק ל-\( 36=3\times12 \) או ל-\( 36=36\times1 \) או ל-\( 36=6\times6 \) או ל-\( 36=2\times2\times3\times3 \). הפירוק האחרון מעניין במיוחד כי אי אפשר “להמשיך לפרק” את המספרים שמופיעים בו - המספרים הללו (2,3) נקראים ראשוניים. הפירוק \( 36\times1 \), לעומת זאת, הוא קצת מעצבן כי לא באמת למדנו ממנו משהו חדש - סתם תקענו 1 בלי מטרה. זו סיבה אחת למה אנחנו לא קוראים ל-1 ראשוני למרות שגם אותו אי אפשר “להמשיך לפרק” - בניגוד למספרים אחרים, הוא לא תורם כלום למכפלות שבהן הוא משתתף ואפשר פשוט למחוק אותו. עכשיו, מה שנחמד במספרים ראשוניים הוא שלכל מספר טבעי גדול מ-1 קיים פירוק יחיד למכפלה של ראשוניים - גם אם ננסה לפרק את 36 בשתי דרכים שונות, בסוף נגיע אל \( 2\times2\times3\times3 \) וכך גם לכל מספר אחר.

מספרים מושלמים נולדים מתוך המשחק הזה: ניקח מספר, נסתכל על כל המחלקים שלו שקטנים ממנו (כל אחד נספר רק פעם אחת), ואז נחבר את כולם. למשל, עבור 36 המחלקים שלו שקטנים ממנו הם \( 1,2,3,4,6,9,12,18 \). אם נחבר את כולם נקבל \( 55 \). זה לא נראה כרגע מעניין במיוחד, אבל אבל אנחנו משחקים פה משחק, אז בואו נקבל את זה שהתהליך הזה של “לקחת את כל המחלקים ולחבר אותם” הוא מעניין.

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

האם יש נקודות שבת אחרות? מספרים שסכום המחלקים שלהם שקטנים מהם שווה להם עצמם? למרבה השמחה יש ויש, ושתי הדוגמאות הראשונות הן 6 (עם המחלקים \( 1,2,3 \)) ו-\( 28 \) (עם המחלקים \( 1,2,4,7,14 \)). מכיוון שהמשחק הזה היה ממש מעניין ליוונים הקדמונים, אוקלידס קרא למספרים כאלו מושלמים בספרו “יסודות” (מה זה “יסודות”? תכף נגיע לזה). מאז עברו אי-אלו שנים וגילינו הרבה תכונות מעניינות אחרות של מספרים, אבל אין מה לעשות - אוקלידס קרא למספרים הללו דווקא מושלמים, אז מכאן ועד לנצח זו תהיה התכונה שתהפוך מספר ל”מושלם”.

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

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

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

הנה מה שהוא מציע, בניסוח קצת יותר מודרני: קחו את המספרים \( 1,2,4,8,\dots \), כלומר מתחילים מ-1 ואז כופלים שוב ושוב ב-2. את המספרים הללו בואו נחבר, כשאחרי כל חיבור אנחנו עוצרים כדי לבדוק אם קיבלנו מספר ראשוני. נניח שקיבלנו, אז בואו נכפול את המספר הראשוני שקיבלנו במחובר האחרון - הופס! התוצאה תהיה מספר מושלם!

זה נשמע כמו קסם, בואו נעשה את זה בפועל: \( 1 \) לבדו הוא לא ראשוני (גם לא אצל אוקלידס). לעומת זאת, \( 1+2=3 \) ו-3 הוא כן ראשוני; בואו נכפול אותו במחובר האחרון, כלומר ב-2, והופס! קיבלנו את 6, שהוא מספר מושלם. יפה! מה הלאה? \( 1+2+4=7 \), שהוא מספר ראשוני; נכפול ב-4 והופס! קיבלנו את \( 28 \), שהוא מספר מושלם. יפה! מה הלאה?

\( 1+2+4+8=15 \) וזה לא מספר ראשוני, אבל \( 1+2+4+8+16=31 \) שהוא כן ראשוני, ולכן \( 16\times31=496 \) הוא מספר מושלם. ובוא נמשיך עם זה עוד טיפה: \( 31+32=63 \) וזה לא מספר ראשוני (\( 63=7\times9 \)) אבל \( 63+64=127 \) שהוא כן מספר ראשוני, ולכן \( 127\times64=8128 \) הוא מספר מושלם. ומה הלאה? ובכן, בואו לא נתקדם הלאה. העניין הוא שהמספרים הבאים בסכום יוצאים לא ראשוניים עד לשלב מתקדם יחסית, ואז זה כבר כאב ראש לבדוק אם קיבלנו משהו ראשוני או לא. אוקלידס עצמו לא הכיר, ככל הנראה, מספרים מושלמים מעבר לארבעה שמצאנו.

אם תסתכלו על החישובים שביצענו קל לראות שתמיד קיבלנו בסכום שלנו מספר ששווה לחזקה הבאה של 2 שעמדנו לחבר, פחות 1. למשל, \( 1+2+4+8=15=16-1 \). בסימונים אלגבריים, \( 1+2+2^{2}+\dots+2^{n}=2^{n+1}-1 \). אין כאן משהו מפתיע - זה מקרה פרטי של נוסחת הסכום של סדרה הנדסית \( 1+q+q^{2}+\dots+q^{n}=\frac{q^{n+1}-1}{q-1} \) (איך מוכיחים אותה? כפלו את שני האגפים ב-\( q-1 \) ותראו מה קורה!). אז את השיטה של אוקלידס ניתן לתאר בנוסח המפושט הבא: אם \( 2^{n}-1 \) הוא מספר ראשוני, אז \( \left(2^{n}-1\right)\cdot2^{n-1} \) יהיה מספר מושלם. אוקלידס לא נתן שמות למספרים מהצורה \( 2^{n}-1 \); הם נקראים מספרי מרסן על שם מתמטיקאי בן המאה ה-17 שכמובן לא המציא אותם אבל בנה רשימה גדולה (לזמנו, ועם כמה טעויות) של מספרי מרסן הראשוניים (ולכן, כפי שכבר ראינו, גם גילה על הדרך מספרים מושלמים). מספר מרסן ראשוני נקרא פשוט ראשוני מרסן, וגם בימינו הראשוניים הללו פופולריים להחריד; בכל פעם שבה מדווח על גילוי “המספר הראשוני הגדול ביותר אי פעם!!!!!” המספר הזה הוא ראשוני מרסן חדש שהתגלה (כבר גילינו 49 ובטח עוד כמה שנים נגלה עוד אחד). הסיבה לכך היא שיש מבחן בדיקת ראשוניות שמיועד ספציפית למספרי מרסן והיעילות שלו (ביחס לגודל של המספר הנבדק) היא משמעותית טובה יותר מהיעילות של שיטות כלליות לבדיקת ראשוניות, כך שאפשר לבדוק ראשוניות של מספרים גדולים מאוד בעיקר אם הם מספרי מרסן.

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

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

נותרו לי עוד שתי שאלות, ואני לא יודע מה איתכם אבל בעיני הן המעניינות ביותר כאן: ראשית, מה עם ה-6 וה-28 הללו שנמצאים בסוף כל מספר מושלם? האם אנחנו כבר יכולים להבין למה הם שם? ושנית, איך מוכיחים את הטענות של אוקלידס ושל אוילר?

נתחיל מעניין ה-6 ו-28 הזה. איך אפשר להבין אותו, אם אנחנו רוצים לפתור את זה עצמאית? מה שאני הייתי עושה ראשית כל הוא לפתוח מחשב ולכתוב סקריפט שיחשב לי את כל הערכים של \( \left(2^{n}-1\right)2^{n-1} \) עבור 30 ה-\( n \)-ים הראשונים (בין אם \( 2^{n}-1 \) הוא ראשוני ובין אם לאו) כדי לקבל תחושה של מה הולך פה. בשפה כמו רובי או פייתון זה סקריפט של שורה בודדת ולא צריך לדאוג לשטויות כמו מספרים גדולים מדי, כך שזה עניין פשוט מאוד (ולמתמטיקאים בעבר זה היה כאב ראש נוראי). חיש קל אפשר לראות שמקבלים מספרים משלושה סוגים בלבד: כאלו שמסתיימים ב-6; כאלו שמסתיימים ב-28; וכאלו שמסתיימים ב-0, למשל \( 120=15\cdot8=\left(2^{4}-1\right)\cdot2^{3} \). מבין אלו, הכי קל להבין את אלו שמסתיימים ב-0 דווקא: מספר מסתיים ב-0 אם הוא מתחלק ב-10. מכיוון ש-\( 10=2\times5 \), מספר שמתחלק ב-10 צריך להתחלק הן ב-2 והן ב-5. עכשיו, המספר \( \left(2^{n}-1\right)2^{n-1} \) כבר מוצג לנו בתור פירוק לחלק זוגי (ה-\( 2^{n-1} \)) וחלק אי-זוגי, ה-\( 2^{n}-1 \). מכיוון שהחלק הזוגי הוא חזקה של 2 בלבד, המספרים היחידים שיכולים לחלק אותו הם זוגיים, ולכן מכיוון ש-5 הוא אי-זוגי, הוא מחלק רק את החלק האי-זוגי, לא את החלק הזוגי. במילים אחרות, קיבלנו שאם המספר שלנו מתחלק ב-10, אז \( 2^{n}-1 \) מתחלק ב-5 ובפרט הוא איננו מספר ראשוני. זה מסביר למה אין ברשימה שלנו מספרים מושלמים שמסתיימים ב-0. עם זאת, עדיין נשאר להבין למה האפשרויות היחידות למה שהמספרים יסתיימו בהם הם או 0 או 6 או 28 - וכפי שאנחנו רואים, זו שאלה שבכלל לא קשורה לראשוניות של \( 2^{n}-1 \).

כעת, הספרה האחרונה של מכפלת שני מספרים נקבעת על פי המכפלה של הספרה האחרונה בכל אחד מהם; בניסוח מתמטי, \( ab \) מודולו 10 שווה למכפלה של \( a \) מודולו 10 ב-\( b \) מודולו 10, כל זה מודולו 10. במקרה שלנו \( a=2^{n-1} \) ואילו \( b=2^{n}-1 \). בדיקה מפורשת מראה לנו שהספרה האחרונה של חזקות של 2 מתנהגת באופן המחזורי הבא: \( 2,4,8,6,2,4,8,6,\dots \). כדי לגלות איך מתנהגת הספרה האחרונה של מספר מרסן המתאים צריך לקחת כל מספר בסדרה הזו, להכפיל ב-2 ולהחסיר 1. מקבלים \( 3,7,5,1,3,7,5,1\dots \). המכפלה (מודולו 10) של האיברים במקומות המתאימים בשתי הסדרות תיתן לנו את הסדרה \( 6,8,0,6,6,8,0,6,\dots \). אז קיבלנו שהספרה האחרונה היא אכן תמיד 6 או 0 או 8. הדבר היחיד שחסר לנו הוא לראות שבמקרים שבהם הספרה האחרונה היא 8, שתי הספרות האחרונות ביחד הן 28. זה קצת יותר מסובך, כי עכשיו צריך להתחשב בשתי הספרות האחרונות בכל המספרים שכופלים.

הנה נימוק פשוט יחסית שמטפל בסיטואציה הזו: ראשית, נשים לב לכך ש-\( 2^{n} \) מתחלק ב-4 תמיד פרט למקרה \( n=1 \) שלא רלוונטי לנו כי בו הספרה האחרונה אינה 4. לכן אם הספרה האחרונה ב-\( 2^{n} \) היא 4, שתי הספרות האחרונות יכולות להיות רק \( 04,24,44,64,84 \) (כי אם מספר מתחלק ב-4 שתי הספרות האחרונות שלו צריכות מרכיבות מספר שמתחלק ב-4). כדי לקבל את שתי הספרות האחרונות של מספר מרסן המתאים שוב פעם צריך לכפול ב-2 ולהחסיר 1, ולכן נקבל \( 07,47,87,27,67 \). בואו נחדד את זה: אני מקבל שמכפלת שתי הספרות האחרונות של שני המספרים היא מכפלה מהצורה \( \left(4+20k\right)\left(7+40k\right) \), והמכפלה הזו יוצאת \( 28+140k+160k+800k^2=28+300k+800k^2 \). כלומר, 28 ועוד מספר ששתי הספרות האחרונות שלו הן 0, ולכן שתי הספרות האחרונות יצאו 28. זה עניין ממוזל; אין כאן קסם עמוק במיוחד. בסופו של דבר, זו תוצאה שתלויה בבסיס הספירה שלנו.

עכשיו סוף סוף אנחנו מגיעים אל החלק המתמטי הרציני שלנו - הוכחות לטענות של אוקלידס ושל אוילר. ההוכחות הללו מתבססות על להבין קצת יותר טוב איך מתנהגת הפעולה הזו שלוקחת מספר ומחזירה את סכום מחלקיו. לפני שאצטט תוצאה כללית, אתן דוגמה: אמרנו שסכום המחלקים של 36 הוא הסכום \( 1+2+3+4+6+9+12+18 \). האם יכלנו לכתוב את הסכום הזה בצורה יותר קומפקטית? כאן בדיוק נכנס הפירוק לגורמים של \( 36 \) לעזרתנו. \( 36=2^{2}\cdot3^{2} \). כל מחלק של 36 מתקבל מכך שאנחנו לוקחים חזקה של 2 בין 0 ל-2, וחזקה של 3 בין 0 ל-2, וכופלים את שתי החזקות הללו. למתמטיקאים יש טריק פשוט לייצר את כל סכומי המכפלות האפשריים - כפל של חיבור:

\( \left(1+2+4\right)\left(1+3+9\right) \)

כאן אנחנו כותבים חיבור של כל החזקות הרלוונטיות של 2 וכל החזקות הרלוונטיות של 4, וכופלים. כשנפתח את הסוגריים, מה שנקבל יהיה סכום של איברים, שכל אחד מהם מתקבל על ידי כך שאנחנו בוחרים מישהו מהסוגריים השמאליים ומישהו מהסוגריים הימניים וכופלים אותם. כל מחלק של 36 יתקבל בצורה הזו, כי הפירוק לגורמים של כל מחלק כזה כולל בדיוק את אותם גורמים ראשוניים כמו 36, רק אולי עם חזקות קטנות יותר (בפרט החזקה עשויה להיות 0 ואז הגורם “נעלם”). לרוע המזל, גם 36 בעצמו יתקבל בצורה הזו (הרי גם הוא מחלק של 36) אבל אנחנו התעניינו בפעולה של “סכום כל המחלקים שקטנים מהמספר”. לא נורא, בואו נתאים את עצמנו לגישה החדשה הזו, כי עליה יהיה קל לנו להוכיח דברים. אני אגדיר פונקציה \( \sigma\left(n\right)=\sum_{d|n}d \) שעוברת על כל הטבעיים שמחלקים את \( n \) כולל \( n \) עצמו, ומחברת אותם (זו משמעות הסימון \( \Sigma \) פה). אם \( n \) הוא מספר מושלם, הוא מקיים \( \sigma\left(n\right)=2n \) (כי סכום כל מחלקיו של \( n \) מושלם שכזה שווה ל-\( n \) עצמו ועוד סכום כל יתר מחלקיו, שסכומם הוא \( n \) גם כן). את מה שראינו קודם במקרה הפרטי של 36 אפשר כעת להכליל לנוסחה נחמדה: אם הפירוק לגורמים של \( n \) הוא \( n=p_{1}^{k_{1}}\dots p_{t}^{k_{t}} \) אז

\( \sigma\left(n\right)=\left(1+p_{1}+p_{1}^{2}+\dots+p_{1}^{k_{1}}\right)\dots\left(1+p_{t}+p_{t}^{2}+\dots+p_{t}^{k_{t}}\right) \)

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

\( \sigma\left(n\right)=\prod_{i=1}^{t}\left(\sum_{j=0}^{k_{i}}p_{i}^{j}\right) \)

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

\( \sigma\left(n\right)=\left(\frac{p_{1}^{k_{1}+1}-1}{p_{1}-1}\right)\cdots\left(\frac{p_{t}^{k_{t}+1}-1}{p_{t}-1}\right) \)

זו נוסחה נטולת סכומים ארוכים והיא מאפשרת לנו חישוב מהיר מאוד של \( \sigma\left(n\right) \) אם אנחנו יודעים מה הפירוק לגורמים של \( n \), ממש בלי שנצטרך לעבור על כל המחלקים שלו. זו המחשה נחמדה מאוד לאופן שבו היכרות עם הפירוק לגורמים של מספר נותנת לנו עליו אינפורמציה לא טריוויאלית (לרוע המזל, למצוא את הפירוק לגורמים של מספר יכולה להיות בעיה קשה מאוד בפני עצמה).

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

\( \sigma\left(n\right)=\left(1+\left(2^{k}-1\right)\right)\left(\frac{2^{k}-1}{2-1}\right)=2^{k}\left(2^{k}-1\right)=2\left(\left(2^{k}-1\right)2^{k-1}\right)=2n \)

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

נעבור עכשיו לכיוון השני, של אוילר: אני אקח מספר \( n \) זוגי כלשהו שמקיים \( \sigma\left(n\right)=2n \) וארצה להוכיח שהוא מהצורה \( n=\left(2^{k}-1\right)2^{k-1} \). איך נעשה את זה?

ראשית כל, אמרנו ש-\( n \) הוא זוגי. אז אפשר לכתוב אותו בתור חזקה גדולה מ-0 של 2 כפול מספר אי זוגי. הבה ונעשה זאת: \( n=2^{k-1}m \), כאשר \( k\ge2 \). בעצם כל מה שנשאר לנו להראות הוא ש-\( m=2^{k}-1 \) ושהוא ראשוני.

הצעד הראשון הוא להשתמש בתכונה מועילה מאין כמותה של \( \sigma \) - היא כפלית. אם נסתכל על הנוסחה עבור \( \sigma \), הצגנו אותה בתור מכפלה של סכומים, כאשר כל מכפלה מיועדת לטיפול בגורם ראשוני אחר של המספר שעליו מחשבים את \( \sigma \). זה אומר שאם יש לנו שני מספרים \( a,b \), שהם זרים - אין להם מחלקים משותפים - אז יתקיים \( \sigma\left(ab\right)=\sigma\left(a\right)\sigma\left(b\right) \) (זה לא נכון למספרים לא זרים; די נפוץ לקרוא לפונקציה בהקשר כמו שלנו “כפלית” גם אם זה רק על מספרים זרים; למשל פונקצית אוילר). במקרה שלנו, מכיוון ש-\( m \) אי זוגי, זה אומר ש-

\( \sigma\left(n\right)=\sigma\left(2^{k-1}m\right)=\sigma\left(2^{k-1}\right)\sigma\left(m\right)=\left(2^{k}-1\right)\sigma\left(m\right) \)

המעבר האחרון נובע מכך ש-\( \sigma\left(2^{k-1}\right)=1+2+\dots+2^{k-1}=2^{k}-1 \) (שוב, סכום טור הנדסי). כעת, מכיוון ש-\( n \) מושלם אז \( \sigma\left(n\right)=2n=2^{k}m \), ולכן קיבלנו:

\( 2^{k}m=\left(2^{k}-1\right)\sigma\left(m\right) \)

כעת, \( 2^{k}-1 \) מחלק את אגף ימין ולכן מחלק את אגף שמאל. מכיוון שהוא אי זוגי הוא אינו מחלק את \( 2^{k} \) ולכן הוא מחלק את \( m \). כלומר, אפשר לכתוב \( m=\left(2^{k}-1\right)M \). בואו נציב את זה חזרה במשוואה \( 2^{k}m=\left(2^{k}-1\right)\sigma\left(m\right) \) ונחלק ב-\( 2^{k}-1 \). נקבל:

\( 2^{k}M=\sigma\left(m\right) \)

מה עכשיו? אנחנו יודעים ש-\( m,M \) שניהם מחלקים של \( m \) ולכן שניהם משתתפים בסכום שמרכיב את \( \sigma\left(m\right) \), כלומר

\( \sigma\left(m\right)\ge m+M=\left(2^{k}-1\right)M+M=2^{k}M \)

אם היה מתקיים \( \sigma\left(m\right)>m+M \) היינו מקבלים מיידית סתירה: \( 2^{k}M=\sigma\left(m\right)>2^{k}M \). לכן \( \sigma\left(m\right)=m+M \). אבל זה אומר לנו את כל מה שאנחנו צריכים: ש-\( m,M \) הם שני המחלקים היחידים של \( m \), ולכן חייב להתקיים \( M=1 \), כלומר \( m=2^{k}-1 \), ו-\( m \) ראשוני כי אין לו מחלקים פרט לשני אלו. סיימנו!

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

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