מספר קרמייקל

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

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

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

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

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

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

מספרי קרמייקל הבאים הם ():

התפלגות
נסמן ב- את מספר מספרי קרמייקל שקטנים או שווים ל-. התפלגות מספרי קרמייקל לפי חזקות 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, שיפר ארדש את החסם:

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

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

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

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

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

 השערת להמר 

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

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



הערות שוליים

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