מספר קרמייקל

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

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

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

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

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

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

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

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

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

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

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

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

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

2 גורר את 3: אם b זר ל-n, אז נובע מההנחה משום ש-b הפיך מודולו n.

3 גורר את 1: יהי מחלק שהוא חזקת מספר ראשוני. אם p=2 נניח מלכתחילה ש-. בעזרת משפט השאריות הסיני, נבחר מספר a שהוא גם שורש פרימיטיבי של (זהו איבר מסדר בחבורת אוילר ; נאלצנו להניח ש- אינו מתחלק ב-8, משום של-8 אין שורש פרימיטיבי), וגם זר לכל גורם ראשוני אחר של n. לכן a זר ל-n, ולפי ההנחה , ולכן גם . מכאן ש- מתחלק בסדר של בחבורת אוילר , כלומר . בפרט, , כנדרש. לצד זה, אם r>1 מתקבל גם , וזו סתירה לכך ש-, ומכאן ש- גם חופשי מריבועים.

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

קורסלט היה הראשון שציין תכונות של מספרי קרמייקל, אך הוא לא מצא דוגמאות למספרים כאלו. ב-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" (PDF). Publ. Math. Debrecen. 4: 201–206. MR 0079031.
  3. ^ W. R. Alford, A. Granville, C. Pomerance (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics. 139: 703–722. doi:10.2307/2118576.{{cite journal}}: תחזוקה - ציטוט: multiple names: authors list (link)
  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" (PDF). Bull. Amer. Math. Soc. 45: 269–274. doi:10.1090/S0002-9904-1939-06953-X.