מספר קרמייקל

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

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

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

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

משפט פרמה הקטן קובע שאם n ראשוני, אז לכל זר ל-. כאשר n אינו ראשוני השוויון בדרך כלל אינו מתקיים, ואפשר לבסס על כך מבחנים פשוטים לראשוניות של n. אם n אינו ראשוני ובכל-זאת , הוא נקרא פסאודו-ראשוני ביחס ל-b. מספרי קרמייקל הם פסאודו-ראשוניים ביחס לכל הבסיסים.

מספרי קרמייקל נדירים יחסית. למשל, יש 20,138,200 מספרי קרמייקל בין 1 ל-1021, כלומר בערך 1 מכל 50 מיליארד מספרים בטווח זה, והם נעשים נדירים יותר ככל שהמספרים גדלים.

קריטריון קורסלט[עריכת קוד מקור | עריכה]

קריטריון קורסלט (Korselt) קובע שמספר פריק הוא מספר קרמייקל אם ורק אם שני התנאים הבאים מתקיימים:

  1. חסר-ריבועים. כלומר הוא אינו מתחלק באף מספר ריבועי מלבד 1. במילים אחרות, מתפרק לגורמים כמכפלה של ראשוניים שונים זה מזה.
  2. עבור כל ראשוני שמחלק את , מתקיים גם (כלומר p-1 מחלק את n-1).

תכונה מספר 2 משמשת לזיהוי מספרי קרמייקל באלגוריתמים לבדיקת ראשוניות כמו אלגוריתם מילר-רבין.

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

מסקנה נוספת: למספר קרמייקל יש לפחות שלושה גורמים ראשוניים (אחרת המספר הוא מהצורה כאשר p,q ראשוניים, ו-p-1 מחלק את , כלומר p-1 מחלק את q-1; וגם להיפך; לכן p=q, בסתירה לתנאי הראשון.

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

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

כעת נראה את הכיוון השני. נניח ש- מספר קרמייקל ונוכיח שהוא מקיים את התנאים 1 ו-2. נתחיל עם תנאי 1. נניח שמתקיים . מספר קרמייקל ולכן . מכאן ש-. מכיוון ש-, נקבל ש-. לכן ו- חסר ריבועים.

נוכיח את תנאי 2. נניח , ונוכיח ש-. יהי שורש פרימיטיבי של (זהו איבר מסדר בחבורת אוילר ). זר ל- (כי זר ל-) ולכן ובפרט . הוכחנו ש-, ולכן מתחלק בסדר של בחבורת אוילר , כלומר כנדרש.

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

קורסלט היה הראשון שציין תכונות של מספרי קרמייקל, אך הוא לא מצא דוגמאות למספרים כאלו. ב-1910, מצא קרמייקל את מספר קרמייקל הקטן ביותר, , ומשום כך נקראים המספרים על שמו.[1] ניתן לראות ש- מקיים את תנאי משפט קורסלט: הפירוק לגורמים לא מכיל ראשוני ממעלה שנייה, ומתקיים וגם וגם .

מספרי קרמייקל הבאים הם (סדרה A002997 ב-OEIS):

התפלגות[עריכת קוד מקור | עריכה]

נסמן ב- את מספר מספרי קרמייקל שקטנים או שווים ל-. התפלגות מספרי קרמייקל לפי חזקות 10 היא:

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
1 7 16 43 105 255 646 1547 3605 8241 19279 44706 105212 246683 585355 1401644 3381806 8220777 20138200

בשנת 1953, הוכיח קנדל (Knödel) את החסם:

עבור קבוע כלשהו.

ב-1956, שיפר ארדש[2] את החסם:

עבור קבוע כלשהו. ההערכה של עבור X=10^N כאשר N הולך וגדל היא באזור: .


לכיוון השני, הוכיחו ב-1994 ויליאם אלפורד, אנדרו גרנוויל וקרל פומרנץ שקיימים אינסוף מספרי קרמייקל.[3] בפרט, הם הוכיחו שעבור גדול דיו:

ב-2005 שיפר הרמן[4] את החסם ל:

צ'רניק[5] הבחין ב-1939 שכל מספר מהצורה , כאשר שלושת הגורמים ראשוניים, הוא מספר קרמייקל. השאלה האם קיימים אינסוף מספרי קרמייקל מצורה זו היא בעיה פתוחה.

לו וניבור מצאו ב-1992 כמה מספרי קרמייקל גדולים במיוחד, כולל מספר קרמייקל עם 1,101,518 גורמים ומעל 16 מיליון ספרות.

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

המספר הטבעי n הוא מספר קרמייקל אם האקספוננט של חבורת אוילר של n מחלק את n-1. מכיוון שהאקספוננט תמיד מחלק את הסדר , הדרישה היא דרישה חזקה יותר. השערת להמר (אנ'), שעודנה פתוחה, קובעת שאין מספרים כאלה שאינם ראשוניים.

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

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

  1. ^ R. D. Carmichael (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society 16 (5): 232–238. 
  2. ^ Erdős, P. (1956). "On pseudoprimes and Carmichael numbers". Publ. Math. Debrecen 4: 201–206. MR 79031. 
  3. ^ W. R. Alford, A. Granville, C. Pomerance (1994). "There are Infinitely Many Carmichael Numbers". Annals of Mathematics 139: 703–722. doi:10.2307/2118576. 
  4. ^ Glyn Harman (2005). "On the number of Carmichael numbers up to x". Bull. Lond. Math. Soc. 37: 641–650. doi:10.1112/S0024609305004686. 
  5. ^ Chernick, J. (1939). "On Fermat's simple theorem". Bull. Amer. Math. Soc. 45: 269–274. doi:10.1090/S0002-9904-1939-06953-X.