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

בתורת המספרים, מבחן לוקאס-להמר הוא מבחן ראשוניות – העשוי לספק הוכחה מהירה לכך שמספר נתון 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 מחלק את $\ \varphi (n)$ (כאשר $\ \varphi$ פונקציית אוילר), אז נוכל להסיק $\ \varphi (n)=n-1$ (מכיוון שתמיד $\ \varphi (n)\leq n-1$), כלומר, אין אף מספר קטן מ- n המחלק אותו, ולכן n ראשוני. נניח, אם כן, ש- q הוא ראשוני שחזקתו $\ q^{r}$ מחלקת את $\ n-1$. לפי ההנחה קיים a שהסדר שלו בחבורת אוילר, $\ ord(a)$, מחלק את n-1 אבל לא את $\ (n-1)/q$. אם כך, $\ q^{r}$ מוכרח לחלק את $\ ord(a)$ (אחרת $\ ord(a)$ היה מחלק את $\ (n-1)/q$), ולכן גם את $\ \varphi (n)$, המתחלק תמיד ב- $\ ord(a)$ (לפי משפט לגראנז'). הוכחנו שכל חזקת ראשוני המחלקת את n-1 מחלקת גם את $\ \varphi (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 אכן ראשוני, אז יש $\ \varphi (n-1)$ עדים פוטנציאליים אפילו למבחן החלש (כל היוצרים של חבורת אוילר, שהיא ציקלית במקרה זה). מכיוון שהיחס $\ {\frac {\varphi (n-1)}{n-1}}$ קרוב בדרך-כלל ל-1, קל למצוא את העדים והמבחן נחשב למבחן הסתברותי יעיל.

ראו גם

• מבחני ראשוניות
• סדר של איבר בחבורה