מספר קרמייקל

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<center>
{| class="wikitable"
|-
! <math>n</math>
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 12
| 13
| 14
| 15
| 16
| 17
| 18
| 19
| 20
| 21
|-
! <math>C(10^n)</math>
| 1
| 7
| 16
| 43
| 105
| 255
| 646
| 1547
| 3605
| 8241
| 19279
| 44706
| 105212
| 246683
| 585355
| 1401644
| 3381806
| 8220777
| 20138200
|}
</center>
בשנת 1953, הוכיח קנדל (Knödel) את החסם:
:<math>C(X) < X \exp\left({-k_1 \left( \log X \log \log X\right)^\frac{1}{2}}\right)</math>

עבור <math>k_1</math> קבוע כלשהו. 

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

:<math>C(X) < X \exp\left(\frac{-k_2 \log X \log \log \log X}{\log \log X}\right)</math>

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

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

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

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

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

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

==קישורים חיצוניים==
* [https://web.archive.org/web/20120430081231/http://kaye7.school.org.il/number_types.htm#%D7%9E%D7%A1%D7%A4%D7%A8%D7%99_%D7%A7%D7%A8%D7%9E%D7%99%D7%99%D7%A7%D7%9C מספרי קרמייקל/ טיפוסי מספרים בתורת המספרים], אתר המרכז לתכנון לימודים במכללת קיי בבאר-שבע
* 
* 

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

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