מספר קרמייקל

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

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

רקע

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

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

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

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

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

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

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

הוכחה

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

2 גורר את 3: אם $ a $ זר ל-$ n $ , אז $ a^{n-1}\equiv 1{\pmod {n}} $ נובע מההנחה $ a^{n}\equiv a{\pmod {n}} $ משום ש-$ a $ הפיך מודולו $ 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, מצא קרמייקל את מספר קרמייקל הקטן ביותר, 560, ומשום כך נקראים המספרים על שמו. ניתן לראות כי $ 561 $ מקיים את תנאי משפט קורסלט: הפירוק לגורמים $ 561=3\cdot 11\cdot 17 $ לא מכיל ראשוני ממעלה שנייה, ומתקיים $ 2|560 $ וגם $ 10|560 $ וגם $ 16|560 $ .

מספרי קרמייקל הבאים הם (סדרה A002997 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים):

$ {\begin{aligned}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\end{aligned}} $

התפלגות

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

$ n $	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
$ C(10^{n}) $	1	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683	585355	1401644	3381806	8220777	20138200

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

$ C(X)<X\exp \left({-k_{1}{\sqrt {\log(X)\log {\bigl (}\log(X){\bigr )}}}}\right) $

עבור $ k_{1} $ קבוע כלשהו.

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

$ C(X)<X\exp \left({\frac {-k_{2}\log(X)\log {\Big (}\log {\bigl (}\log(X){\bigr )}{\Big )}}{\log(\log(X))}}\right) $

עבור $ k_{2} $ קבוע כלשהו. ההערכה של $ k_{2} $ עבור $ X=10^{N} $ כאשר $ N $ הולך וגדל היא באזור: $ k_{2}=1.86619 $ .

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

$ C(X)>{\sqrt[{7}]{X^{2}}} $

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

$ C(X)>X^{0.332} $

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

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

השערת להמר

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

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

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