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

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

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

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

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

תיאור המבחן

משפט: אם לכל גורם ראשוני $q$ של $n-1$ קיים מספר $a$ המקיים $a^{n-1}\equiv 1\!\!\!{\pmod {n}},\,a^{(n-1)/q}\not \equiv 1\!\!\!{\pmod {n}}$, אזי $n$ הוא ראשוני.

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

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

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

ראו גם

• מבחן ראשוניות
• סדר (תורת החבורות)