מבחן לוקאס-להמר
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת המספרים, מבחן לוקאס-להמר הוא מבחן ראשוניות - המבחן עשוי לספק הוכחה מהירה לכך שמספר נתון n הוא ראשוני. המבחן הוצע על ידי המתמטיקאי הצרפתי אדוארד לוקאס בשנת מותו, 1891, ושופר בשנות השלושים של המאה העשרים על-ידי האמריקאי ד.ה. להמר. מבחן אחר בעל שם דומה הוא מבחן לוקאס-להמר למספרי מרסן, המותאם במיוחד לבדיקת מספרי מרסן.
לפי המשפט הקטן של פרמה, אם n הוא ראשוני שאינו מחלק את a, אז
. בניסוח אחר אפשר לומר שהסדר של a בחבורת אוילר של n מחלק את n-1. אם השוויון אינו מתקיים, זוהי ראיה מיידית לכך ש- n אינו ראשוני; אבל שוויון אינו מוכיח ש- n ראשוני - הוא עלול להיות פסאודו-ראשוני.
מבחן לוקאס-להמר מהווה מעין כיוון הפוך למשפט פרמה. אם הסדר של a בחבורת אוילר של n שווה ל- n-1, אז n מוכרח להיות ראשוני. כל מבחני הראשוניות שפותחו מאוחר יותר הם ווריאציות על רעיון זה.
חסרונו הגדול של המבחן הוא שנדרשת ידיעת הפירוק לגורמים של n-1. בנוסף, הבדיקה דורשת עֵד, מספר שיקרא כאן a. כל עד עשוי להוכיח ש- n ראשוני, אבל אם עד מסוים נכשל, לא ניתן להסיק מכך ש- n אינו ראשוני. לאחרונה (2004) התברר שאין צורך לבדוק עדים הגדולים מ-
; אם כל העדים עד מספר זה נכשלו, המספר אינו ראשוני. מתוצאה זו נובע שהוכחת ראשוניות של n היא בעיה בעלת סיבוכיות פולי-לוגריתמית.
[עריכה] תאור המבחן
משפט. אם לכל גורם ראשוני q של n-1 קיים מספר a המקיים
ו-
, אז n הוא ראשוני.
הוכחה. אם נגלה ש-
מחלק את n-1 (כאשר
היא פונקציית אוילר), אז נוכל להסיק ש-
(מכיוון שתמיד
), כלומר, אין אף מספר קטן מ- n המחלק אותו, ולכן n ראשוני. נניח, אם כן, ש- q הוא ראשוני שחזקתו
מחלקת את
. לפי ההנחה קיים a שהסדר שלו בחבורת אוילר,
, מחלק את n-1 אבל לא את
. אם כך,
מוכרח לחלק את
(אחרת
היה מחלק את
), ולכן גם את
, המתחלק תמיד ב-
(לפי משפט לגראנז'). הוכחנו שכל חזקת ראשוני המחלקת את n-1 מחלקת גם את
, כפי שרצינו.
בדרך כלל מספיקה גם הגרסה החלשה הבאה של המבחן: אם קיים מספר a המקיים
, ו-
לכל גורם ראשוני q של n-1, אז n הוא ראשוני. כאן מחפשים a שיתאים בבת-אחת לכל הגורמים הראשוניים (למרות שעל-פי המשפט הראשון, תנאי זה אינו הכרחי). ההוכחה של הגרסה החלשה מיידית: אם a מספר המקיים את התנאים, אז הסדר שלו בחבורת אוילר שווה ל- n-1, ולכן (לפי משפט לגרנז') סדר החבורה מתחלק ב- n-1, כפי שרצינו להוכיח.
כדי להוכיח ש- n נתון הוא ראשוני, צריך למצוא a שיקיים את הדרישות. אם n אכן ראשוני, אז יש
עדים פוטנציאליים אפילו למבחן החלש (כל היוצרים של חבורת אוילר, שהיא ציקלית במקרה זה). מכיוון שהיחס
קרוב בדרך-כלל ל-1, קל למצוא את העדים והמבחן נחשב למבחן הסתברותי יעיל.
[עריכה] ראה גם
- מבחני ראשוניות
- מבחן לוקאס-להמר למספרי מרסן

