מספר קרמייקל

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

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

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

רקע

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

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

קריטריון קורסלט

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

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

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

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

הוכחה

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

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

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

דוגמאות למספרי קרמייקל

קורסלט היה הראשון שציין תכונות של מספרי קרמייקל, אך הוא לא מצא דוגמאות למספרים כאלו. ב-1910, מצא קרמייקל את מספר קרמייקל הקטן ביותר, 560, ומשום כך נקראים המספרים על שמו.[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] את החסם:

עבור קבוע כלשהו. ההערכה של עבור כאשר הולך וגדל היא באזור: .

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

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

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

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

השערת להמר

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

קישורים חיצוניים

הערות שוליים

  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.