מספר קרמייקל

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

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

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