מספר קרמייקל

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

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

רקע

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

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

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

קריטריון קורסלט (Korselt) קובע שמספר פריק $n$ הוא מספר קרמייקל אם ורק אם שני התנאים הבאים מתקיימים:

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

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

הוכחה

נוכיח את קריטריון קורסלט. ראשית נניח ש-$n$ מקיים את התנאים 1 ו-2. יהי $b$ מספר טבעי זר ל-$n$. נראה ש-$n \mid b^{n-1}-1$ ולכן $n$ מספר קרמייקל. לפי 1 נרשום את $n$ כמכפלה של ראשוניים שונים: $n = p_1p_2\cdots p_k$. $b$ זר לכל אחד מן הראשוניים ולכן לפי משפט פרמה הקטן, לכל $p_i$ מתקיים $b^{p_i-1} \equiv 1 \pmod{p_i}$. מכיוון שלפי 2 מתקיים: $p_i-1 \mid n-1$, אז $b^{n-1} \equiv 1 \pmod{p_i}$. כלומר לכל $p_i$ מתקיים $p_i \mid b^{n-1}-1$. מכיוון שהראשוניים $p_i$ זרים זה לזה, גם מכפלתם $n$ מקיימת: $n \mid b^{n-1}-1$ כנדרש.

כעת נראה את הכיוון השני. נניח ש-$n$ מספר קרמייקל ונוכיח שהוא מקיים את התנאים 1 ו-2. נתחיל עם תנאי 1. נניח שמתקיים $p^r \mid n$. $n$ מספר קרמייקל ולכן $n \mid p^n-p$. מכאן ש-$p^r \mid p^n-p$. מכיוון ש-$p^r \mid p^n$, נקבל ש-$p^r \mid p$. לכן $r=1$ ו-$n$ חסר ריבועים.

נוכיח את תנאי 2. נניח $p \mid n$, ונוכיח ש-$p-1 \mid n-1$. יהי $a$ שורש פרימיטיבי של $p$ (זהו איבר מסדר $p-1$ בחבורת אוילר $U_p$). $a$ זר ל-$n$ (כי $a$ זר ל-$p$) ולכן $n \mid a^{n-1}-1$ ובפרט $p \mid a^{n-1}-1$. הוכחנו ש-$a^{n-1} \equiv 1 \pmod{p}$, ולכן $n-1$ מתחלק בסדר של $a$ בחבורת אוילר $U_p$, כלומר $p-1 \mid n-1$ כנדרש.

דוגמאות למספרי קרמייקל

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

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

$1105 = 5 \cdot 13 \cdot 17 \qquad (4 \mid 1104; 12 \mid 1104; 16 \mid 1104)$

$1729 = 7 \cdot 13 \cdot 19 \qquad (6 \mid 1728; 12 \mid 1728; 18 \mid 1728)$

$2465 = 5 \cdot 17 \cdot 29 \qquad (4 \mid 2464; 16 \mid 2464; 28 \mid 2464)$

$2821 = 7 \cdot 13 \cdot 31 \qquad (6 \mid 2820; 12 \mid 2820; 30 \mid 2820)$

$6601 = 7 \cdot 23 \cdot 41 \qquad (6 \mid 6600; 22 \mid 6600; 40 \mid 6600)$

$8911 = 7 \cdot 19 \cdot 67 \qquad (6 \mid 8910; 18 \mid 8910; 66 \mid 8910)$

התפלגות

נסמן ב-$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$ קבוע כלשהו.

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

$C(X) > X^{2/7}.$

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

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

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

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

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

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