מספר קרמייקל

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

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

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

1. $n$ חופשי מריבועים (כלומר מכפלת ראשוניים שונים) ולכל מחלק ראשוני $p$ מתקיים גם $p-1\mid n-1$.
2. לכל b מתקיים $b^{n}\equiv b{\pmod {n}}$ (כלומר $n$ הוא מספר קרמייקל).
3. לכל 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$.

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

$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 היא:

$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}\left(\log X\log \log X\right)^{\frac {1}{2}}}\right)$

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

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

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

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

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

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