מבחן לוקאס-להמר

בתורת המספרים, מבחן לוקאס-להמר הוא מבחן ראשוניות – העשוי לספק הוכחה מהירה לכך שמספר נתון <math>n</math> הוא ראשוני. המבחן הוצע על ידי המתמטיקאי הצרפתי אדוארד לוקאס בשנת מותו, 1891, ושופר בשנות ה-30 של המאה ה-20 על ידי האמריקאי ד.ה. להמר. מבחן אחר בעל שם דומה הוא מבחן לוקאס-להמר למספרי מרסן, המותאם במיוחד לבדיקת מספרי מרסן.

לפי המשפט הקטן של פרמה, אם <math>n</math> מספר ראשוני שאינו מחלק את a, אז <math>a^{n-1}\equiv1\!\!\!\pmod{n}</math>. בניסוח אחר אפשר לומר שהסדר של <math>a</math> בחבורת אוילר של <math>n</math> מחלק את <math>n-1</math>. אם השוויון אינו מתקיים, זוהי ראיה מיידית לכך ש-<math>n</math> אינו ראשוני; אבל שוויון אינו מוכיח כי <math>n</math> ראשוני – הוא עלול להיות מספר פסאודו-ראשוני.

מבחן לוקאס-להמר מהווה מעין כיוון הפוך למשפט פרמה. אם הסדר של <math>a</math> בחבורת אוילר של <math>n</math> שווה ל-<math>n-1</math>, אז <math>n</math> מוכרח להיות ראשוני. כל מבחני הראשוניות שפותחו מאוחר יותר הם וריאציות על רעיון זה.

חסרונו הגדול של המבחן הוא שנדרשת ידיעת הפירוק לגורמים של <math>n-1</math>. בנוסף, הבדיקה דורשת עֵד, מספר שיקרא כאן <math>a</math>. כל עד עשוי להוכיח כי <math>n</math> ראשוני, אבל אם עד מסוים נכשל, לא ניתן להסיק מכך כי <math>n</math> אינו ראשוני. ב-2004 התברר שאין צורך לבדוק עדים הגדולים מ-<math>\log(n)^6</math>; אם כל העדים עד מספר זה נכשלו, המספר אינו ראשוני. מתוצאה זו נובע שהוכחת ראשוניות של <math>n</math> היא בעיה בעלת סיבוכיות פולי-לוגריתמית.

==תיאור המבחן==
משפט: אם לכל גורם ראשוני <math>q</math> של <math>n-1</math> קיים מספר <math>a</math> המקיים <math>a^{n-1}\equiv1\!\!\!\pmod{n},\,a^{(n-1)/q}\not\equiv1\!\!\!\pmod{n}</math>, אזי <math>n</math> הוא ראשוני.

הוכחה: אם נגלה כי <math>n-1</math> מחלק את <math>\phi(n)</math> (כאשר <math>\phi</math> פונקציית אוילר), אז נוכל להסיק כי <math>\phi(n)=n-1</math> (מכיוון שתמיד <math>\phi(n)\le n-1</math>), כלומר אין אף מספר קטן מ-<math>n</math> המחלק אותו, ולכן <math>n</math> ראשוני. נניח, אם כן, כי <math>q</math> הוא ראשוני שחזקתו <math>q^r</math> מחלקת את <math>n-1</math>. לפי ההנחה קיים <math>a</math> שהסדר שלו בחבורת אוילר, <math>\text{ord}(a)</math>, מחלק את <math>n-1</math> אבל לא את <math>(n-1)/q</math>. אם כך, <math>q^r</math> מוכרח לחלק את <math>\text{ord}(a)</math> (אחרת <math>\text{ord}(a)</math> היה מחלק את <math>(n-1)/q</math>), ולכן גם את <math>\phi(n)</math>, המתחלק תמיד ב-<math>\text{ord}(a)</math> (לפי משפט לגראנז'). הוכחנו שכל חזקת ראשוני המחלקת את <math>n-1</math> מחלקת גם את <math>\phi(n)</math>, כפי שרצינו.

בדרך כלל מספיקה גם הגרסה החלשה הבאה של המבחן: אם קיים מספר <math>a</math> המקיים <math>a^{n-1}\equiv1\!\!\!\pmod{n},\,a^{(n-1)/q}\not\equiv1\!\!\!\pmod{n}</math> לכל גורם ראשוני <math>q</math> של <math>n-1</math>, אזי <math>n</math> הוא ראשוני. כאן מחפשים <math>a</math> שיתאים בבת-אחת לכל הגורמים הראשוניים (אף כי על-פי המשפט הראשון תנאי זה אינו הכרחי). ההוכחה של הגרסה החלשה מיידית: אם <math>a</math> מספר המקיים את התנאים, אז הסדר שלו בחבורת אוילר שווה ל-<math>n-1</math>, ולכן (לפי משפט לגראנז') סדר החבורה מתחלק ב-<math>n-1</math>, כפי שרצינו להוכיח.

כדי להוכיח כי <math>n</math> נתון הוא ראשוני, יש למצוא <math>a</math> שיקיים את הדרישות. אם <math>n</math> אכן ראשוני, אז יש <math>\phi(n-1)</math> עדים פוטנציאליים אפילו למבחן החלש (כל היוצרים של חבורת אוילר, שהיא ציקלית במקרה זה). מכיוון שהיחס <math>\frac{\phi(n-1)}{n-1}</math> קרוב בדרך-כלל ל-1, קל למצוא את העדים והמבחן נחשב למבחן הסתברותי יעיל.

== ראו גם==
*מבחן ראשוניות
*סדר (תורת החבורות)

קטגוריה:מבחני ראשוניות
קטגוריה:משפטים בתורת המספרים
קטגוריה:הוכחות