מספר משוכלל

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

מספר משוכלל (או: מספר מושלם) הוא מספר טבעי השווה לסכום כל המחלקים הטבעיים שלו מלבד המספר עצמו. המספר המשוכלל הראשון הוא 6=1+2+3, ואחריו באים 28=1+2+4+7+14, 496 ו־8128. עיקר העניין במספרים משוכללים היה בימי הביניים, מסיבות נומרולוגיות. היום הם משמשים אבן בוחן ליכולת החישוב בבדיקה של ראשוניים גדולים.

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

כדי ש־\left(2^n-1\right) יהיה ראשוני, נדרש שגם n עצמו יהיה ראשוני. מספרים ראשוניים מן הצורה הזו נקראים מספרי מרסן ראשוניים, על-שמו של המתמטיקאי הצרפתי מרן מרסן (Marin Mersenne), שהודיע - בטעות - על מציאת מספרים משוכללים חדשים בשנת 1644.

לאונרד אוילר הראה שכל מספר משוכלל זוגי מתאים לתבנית שמצא אוקלידס. השאלה האם קיימים אינסוף מספרים משוכללים זוגיים, או לחלופין האם קיימים אינסוף מספרי מרסן ראשוניים, עודנה פתוחה. באשר למספרים משוכללים אי-זוגיים, לא ידוע האם קיים ולו אחד כזה. שאלת קיומם היא כנראה הבעיה המתמטית הפתוחה העתיקה ביותר. כן ידוע שלמספר משוכלל אי-זוגי יש לפחות 300 ספרות עשרוניות, גורם ראשוני גדול מ-100129, גורם שהוא חזקת ראשוני הגדול מ- \ 10^{12} (ב.י. מושקאט, 1966), גורם ראשוני שני הגדול מ-1000 (P. Hagis Jr., 1980) ושמספר מחלקיו אי זוגי .

בשנת 1952 החלו להיעזר במחשבים לשם מציאת מספרים משוכללים ובאותה שנה כבר נודעו 17 מספרים שכאלה. מאז ממשיך החיפוש ביתר שאת בעזרת מחשבי-על ובעזרת חישוב מבוזר קהילתי, וכיום (פברואר 2013) ידועים כבר 48 מספרים משוכללים.‏[1][2] החיפוש הוא אחר ראשוניי-מרסן, שמהם נוצרים מספרים משוכללים זוגיים בלבד, ולכן אין בו כדי לסייע בתשובה לשאלת הקיום של מספרים משוכללים אי-זוגיים.

מספר משוכלל הוא מספר המקיים את המשוואה \ \sigma(n) = 2n כאשר \ \sigma היא פונקציית סכום המחלקים. מספרים שעבורם \ \sigma(n) < 2n נקראים מספרים חסרים, ואלו שעבורם \ \sigma(n) > 2n נקראים מספרים שופעים.

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

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

נתון שהמספר \left(2^n-1\right) ראשוני, שנסמן מעתה באות \,p. עלינו להוכיח שהמספר (2^{n-1})\cdot p הוא מספר משוכלל.

ראשית נמצא את כל מחלקיו של המספר (מלבד המספר עצמו):

\{1,2,4,8,\ldots,2^{n-1}\}\cup \{p,2p,4p,8p,\ldots,2^{n-2}\cdot p\}

כעת נראה כי סכום איברים אלה שווה למספר עצמו. נחשב את המספר כך:

1+2+4+8+\ldots+2^{n-1}+(1+2+4+8+\ldots+2^{n-2})\cdot p

ומאחר שסכום כל חזקות ה-2 עד \,m כלשהו שווה ל:\!\, 2^{m+1}-1 (זהו סכום של סדרה הנדסית), ניתן לכתוב סכום זה כך:

2^n-1+(2^{n-1}-1)\cdot p=p+(2^{n-1}-1)\cdot p=(2^{n-1})\cdot p

וזהו בדיוק המספר המקורי, ובכך הושלמה ההוכחה.

הוכחת אוילר[עריכת קוד מקור | עריכה]

2000 שנה בערך אחרי אוקלידס עשה המתמטיקאי לאונרד אוילר צעד משמעותי, כאשר הוכיח שכל מספר משוכלל זוגי הוא בהכרח מן הצורה המתוארת לעיל. הוכחה: נניח ש-\,n הוא מספר משוכלל זוגי. ניתן לרשום את \,n כך: \,n = 2^{k-1}m כאשר \ k>1 ו-\,m הוא מספר אי זוגי; בפרט, הוא זר ל- \ 2^{k-1}.

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

בין המחלקים של m אפשר למנות לפחות את \ M ואת \ m עצמו (השונים זה מזה), ולכן \ 2^kM=\sigma(m)\geq m+M=2^kM. מכאן שאי-השוויון החלש הוא למעשה שוויון, ולכן \ m ו-\ M הם המחלקים היחידים של \ m; אבל 1 מחלק את \ m, ולכן \ M=1. הוכחנו כי \ m=2^k-1, והוא ראשוני.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ המספרים המשוכללים הראשונים הם:
    6
    28
    496
    8,128
    33,550,336
    8,589,869,056
    137,438,691,328
    2,305,843,008,139,952,128
    2,658,455,991,569,831,744,654,692,615,953,842,176
    191,561,942,608,236,107,294,793,378,084,303,638,130,997,321,548,169,216
  2. ^ אתר החיפוש אתר מספרי מרסן דרכו נמצאו מספרי מרסן הגדולים ביותר הידועים היום


קישורים חיצוניים[עריכת קוד מקור | עריכה]

ראו גם[עריכת קוד מקור | עריכה]