מספר קרמייקל

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

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

משפט פרמה הקטן קובע שאם 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.