מספר קרמייקל

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

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

רקע

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

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

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

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

1. $n$ חופשי מריבועים (כלומר מכפלת ראשוניים שונים) ולכל מחלק ראשוני $p$ מתקיים גם $p-1\mid n-1$ .
2. לכל $a$ מתקיים $a^n\equiv a(\mathrm{mod}n)$ (כלומר $n$ הוא מספר קרמייקל).
3. לכל $a$ זר ל-$n$ מתקיים $a^{n-1}\equiv 1(\mathrm{mod}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(\mathrm{mod}p)$ לפי המשפט הקטן של פרמה, ולפי משפט השאריות הסיני נובע מכך שגם $a^{n-1}\equiv 1(\mathrm{mod}n)$ . שנית נניח כי $a$ ראשוני המחלק את $n$ . לכל גורם ראשוני $p\ne a$ מתקיים $a^{n-1}\equiv 1(\mathrm{mod}p)$ מאותה סיבה כמו במקרה הראשון, ולכן $a^{n-1}\equiv 1(\mathrm{mod}n/a)$ , ומכאן $a^n\equiv a(\mathrm{mod}n)$ . אבל כל מספר אפשר לכתוב כמכפלה של מספר זר ל-$n$ וגורמים ראשוניים המחלקים את $n$ , ולכן הטענה $a^n\equiv a(\mathrm{mod}n)$ נכונה לכל $a$ .

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

3 גורר את 1: יהי $p^r\mid n$ מחלק שהוא חזקת מספר ראשוני. אם $p=2$ נניח מלכתחילה $r\le 2$ . בעזרת משפט השאריות הסיני, נבחר מספר $a$ שהוא גם שורש פרימיטיבי $a$ של $p^r$ (זהו איבר מסדר $p^{r-1}(p-1)$ בחבורת אוילר $U_p$ ; נאלצנו להניח כי $p^r$ אינו מתחלק ב-8, משום של-8 אין שורש פרימיטיבי), וגם זר לכל גורם ראשוני אחר של $n$ . לכן $a$ זר ל-$n$ , ולפי ההנחה $a^{n-1}\equiv 1(\mathrm{mod}n)$ , ולכן גם $a^{n-1}\equiv 1(\mathrm{mod}{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{array}{r}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{array}$

התפלגות

נסמן $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 (\log (X))}\right)$

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

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

$C(X)<X\exp \left(\frac{-k_2\log (X)\log (\log (\log (X)\left)\right)}{\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$ . מכיוון שהאקספוננט תמיד מחלק את הסדר $\phi (n)$ , הדרישה $\phi (n)\mid n-1$ היא דרישה חזקה יותר. השערת להמר , שעודנה פתוחה, קובעת שאין מספרים כאלה שאינם ראשוניים.

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

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

הערות שוליים

מספר_קרמייקל20484372Q849530