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

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

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

לפי המשפט הקטן של פרמה, אם 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 הוא ראשוני.

הוכחה. אם נגלה ש- $\ \varphi(n)$ מחלק את n-1 (כאשר $\ \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, קל למצוא את העדים והמבחן נחשב למבחן הסתברותי יעיל.