מספר קרמייקל

בתורת המספרים, **מספר קרמייקל** או **מספר פסאודו-ראשוני מוחלט** הוא מספר טבעי פריק n המקיים את מסקנת המשפט הקטן של פרמה: b^n\equiv b\pmod{n} לכל b שלם.

המספרים נקראים כך על שם המתמטיקאי רוברט דניאל קרמייקל, שמצא את מספר קרמייקל הקטן ביותר: \,561=3\cdot 11 \cdot 17, והעלה את ההשערה שישנם אינסוף מספרים כאלו.

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

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

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

התנאים הבאים שקולים עבור מספר פריק n:
# n חופשי מריבועים (כלומר מכפלת ראשוניים שונים) ולכל מחלק ראשוני p מתקיים גם p - 1 \mid n - 1.
# לכל b מתקיים b^n \equiv b \pmod{n} (כלומר n הוא מספר קרמייקל).
# לכל b זר ל-n מתקיים b^{n-1} \equiv 1 \pmod{n}.

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

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

### הוכחה
1 גורר את 2: נניח ש-n חופשי מריבועים ולכל מחלק ראשוני p שלו מתקיים גם p - 1 \mid n - 1. ראשית נניח ש-b זר ל-n. לכל גורם ראשוני p של n מתקיים b^{n-1} = (b^{p-1})^{(n-1)/(p-1)} \equiv 1 \pmod{p} לפי משפט פרמה הקטן, ולפי משפט השאריות הסיני נובע מכך שגם \ b^{n-1} \equiv 1 \pmod{n}. שנית נניח ש-b ראשוני המחלק את n. לכל גורם ראשוני p \neq b מתקיים b^{n-1} \equiv 1 \pmod{p} מאותה סיבה כמו במקרה הראשון, ולכן \ b^{n-1} \equiv 1 \pmod{n/b}, ומכאן ש-\ b^{n} \equiv b \pmod{n}. אבל כל מספר אפשר לכתוב כמכפלה של מספר זר ל-n וגורמים ראשוניים המחלקים את n, ולכן הטענה \ b^{n} \equiv b \pmod{n} נכונה לכל \ b.

2 גורר את 3: אם b זר ל-n, אז b^{n-1} \equiv 1 \pmod{n} נובע מההנחה b^n \equiv b \pmod{n} משום ש-b הפיך מודולו n.

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

## דוגמאות למספרי קרמייקל
קורסלט היה הראשון שציין תכונות של מספרי קרמייקל, אך הוא לא מצא דוגמאות למספרים כאלו. ב-1910, מצא קרמייקל את מספר קרמייקל הקטן ביותר, 561, ומשום כך נקראים המספרים על שמו. ניתן לראות ש-561 מקיים את תנאי משפט קורסלט: הפירוק לגורמים 561 = 3 \cdot 11 \cdot 17 לא מכיל ראשוני ממעלה שנייה, ומתקיים 2 | 560 וגם 10 | 560 וגם 16 | 560.

מספרי קרמייקל הבאים הם ():
:1105 = 5 \cdot 13 \cdot 17
:1729 = 7 \cdot 13 \cdot 19
:2465 = 5 \cdot 17 \cdot 29
:2821 = 7 \cdot 13 \cdot 31
:6601 = 7 \cdot 23 \cdot 41
:8911 = 7 \cdot 19 \cdot 67

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




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

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

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

:C(X) 

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

לכיוון השני, הוכיחו ב-1994 ויליאם אלפורד, אנדרו גרנוויל וקרל פומרנץ שקיימים אינסוף מספרי קרמייקל. בפרט, הם הוכיחו שעבור X גדול דיו:
:C(X) > X^{2/7}.

ב-2005 שיפר הרמן את החסם ל:
:C(X) > X^{0.332}

צ'רניק הבחין ב-1939 שכל מספר מהצורה (6k + 1)(12k + 1)(18k + 1), כאשר שלושת הגורמים ראשוניים, הוא מספר קרמייקל. השאלה האם קיימים אינסוף מספרי קרמייקל מצורה זו היא בעיה פתוחה.

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

## השערת להמר

המספר הטבעי n הוא מספר קרמייקל אם האקספוננט \operatorname{exp}U_n של חבורת אוילר של n מחלק את n-1. מכיוון שהאקספוננט תמיד מחלק את הסדר \ \varphi(n), הדרישה \ \varphi(n) \,|\, n-1 היא דרישה חזקה יותר. **השערת להמר** , שעודנה פתוחה, קובעת שאין מספרים כאלה שאינם ראשוניים.

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

## הערות שוליים

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