מספר קרמייקל

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת המספרים, מספר קרמייקל או מספר פסאודו-ראשוני מוחלט הוא מספר טבעי פריק 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 ל-1021, כלומר בערך 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 הוא מספר זוגי. מסקנה נוספת: למספר קרמייקל יש לפחות שלושה גורמים ראשוניים (אחרת המספר הוא מהצורה \ pq כאשר p,q ראשוניים, ו-p-1 מחלק את pq-1= (p-1)q+(q-1), כלומר p-1 מחלק את q-1; וגם להיפך; לכן p=q, בסתירה לתנאי הראשון.

הוכחה[עריכת קוד מקור | עריכה]

נוכיח את קריטריון קורסלט. ראשית נניח ש-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, ומשום כך נקראים המספרים על שמו.[1] ניתן לראות ש-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, שיפר ארדש[2] את החסם:

C(X) < X \exp\left(\frac{-k_2 \log X \log \log \log X}{\log \log X}\right)

עבור k_2 קבוע כלשהו.

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

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

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

C(X) > X^{0.33}

צ'רניק[5] הבחין ב-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 היא דרישה חזקה יותר. השערת להמר (אנ'), שעודנה פתוחה, קובעת שאין מספרים כאלה שאינם ראשוניים.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ R. D. Carmichael (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society 16 (5): 232–238. 
  2. ^ Erdős, P. (1956). "On pseudoprimes and Carmichael numbers". Publ. Math. Debrecen 4: 201–206. 
  3. ^ W. R. Alford, A. Granville, C. Pomerance (1994). "There are Infinitely Many Carmichael Numbers". Annals of Mathematics 139: 703–722. doi:10.2307/2118576. 
  4. ^ Glyn Harman (2005). "On the number of Carmichael numbers up to x". Bull. Lond. Math. Soc. 37: 641–650. doi:10.1112/S0024609305004686. 
  5. ^ Chernick, J. (1939). "On Fermat's simple theorem". Bull. Amer. Math. Soc. 45: 269–274. doi:10.1090/S0002-9904-1939-06953-X.