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

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

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

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

חסרונו הגדול של המבחן הוא שנדרשת ידיעת הפירוק לגורמים של . בנוסף, הבדיקה דורשת עֵד, מספר שיקרא כאן . כל עד עשוי להוכיח כי  ראשוני, אבל אם עד מסוים נכשל, לא ניתן להסיק מכך כי  אינו ראשוני. ב-2004 התברר שאין צורך לבדוק עדים הגדולים מ-; אם כל העדים עד מספר זה נכשלו, המספר אינו ראשוני. מתוצאה זו נובע שהוכחת ראשוניות של  היא בעיה בעלת סיבוכיות פולי-לוגריתמית.

תיאור המבחן
משפט: אם לכל גורם ראשוני  של  קיים מספר  המקיים , אזי  הוא ראשוני.

הוכחה: אם נגלה כי  מחלק את  (כאשר  פונקציית אוילר), אז נוכל להסיק כי  (מכיוון שתמיד ), כלומר אין אף מספר קטן מ- המחלק אותו, ולכן  ראשוני. נניח, אם כן, כי  הוא ראשוני שחזקתו  מחלקת את . לפי ההנחה קיים  שהסדר שלו בחבורת אוילר, , מחלק את  אבל לא את . אם כך,  מוכרח לחלק את  (אחרת  היה מחלק את ), ולכן גם את , המתחלק תמיד ב- (לפי משפט לגראנז'). הוכחנו שכל חזקת ראשוני המחלקת את  מחלקת גם את , כפי שרצינו.

בדרך כלל מספיקה גם הגרסה החלשה הבאה של המבחן: אם קיים מספר  המקיים  לכל גורם ראשוני  של , אזי  הוא ראשוני. כאן מחפשים  שיתאים בבת-אחת לכל הגורמים הראשוניים (אף כי על-פי המשפט הראשון תנאי זה אינו הכרחי). ההוכחה של הגרסה החלשה מיידית: אם  מספר המקיים את התנאים, אז הסדר שלו בחבורת אוילר שווה ל-, ולכן (לפי משפט לגראנז') סדר החבורה מתחלק ב-, כפי שרצינו להוכיח.

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

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

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