הצגת המקור של הדף "מבחן לוקאס-להמר"

ב[[תורת המספרים]], '''מבחן לוקאס-להמר''' הוא [[מספר ראשוני#מבחני ראשוניות|מבחן ראשוניות]] – העשוי לספק הוכחה מהירה לכך שמספר נתון <math>n</math> הוא [[מספר ראשוני|ראשוני]]. המבחן הוצע על ידי המתמטיקאי הצרפתי [[אדוארד לוקאס]] בשנת מותו, [[1891]], ושופר ב[[שנות ה-30 של המאה ה-20]] על ידי האמריקאי [[דריק הנרי להמר|ד.ה. להמר]]. מבחן אחר בעל שם דומה הוא [[מבחן לוקאס-להמר למספרי מרסן]], המותאם במיוחד לבדיקת [[מספר מרסן|מספרי מרסן]].

לפי [[המשפט הקטן של פרמה]], אם <math>n</math> מספר ראשוני שאינו מחלק את a, אז <math>a^{n-1}\equiv1\!\!\!\pmod{n}</math>. בניסוח אחר אפשר לומר שה[[סדר (תורת החבורות)#סדר של איבר בחבורה|סדר]] של <math>a</math> ב[[חבורת אוילר]] של <math>n</math> מחלק את <math>n-1</math>. אם השוויון אינו מתקיים, זוהי ראיה מיידית לכך ש-<math>n</math> אינו ראשוני; אבל שוויון אינו מוכיח כי <math>n</math> ראשוני – הוא עלול להיות [[מספר פסאודו-ראשוני]].

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

חסרונו הגדול של המבחן הוא שנדרשת ידיעת ה[[פירוק לגורמים של מספר שלם|פירוק לגורמים]] של <math>n-1</math>. בנוסף, הבדיקה דורשת '''עֵד''', מספר שיקרא כאן <math>a</math>. כל עד עשוי להוכיח כי <math>n</math> ראשוני, אבל אם עד מסוים נכשל, לא ניתן להסיק מכך כי <math>n</math> אינו ראשוני. ב-[[2004]] התברר שאין צורך לבדוק עדים הגדולים מ-<math>\log(n)^6</math>; אם כל העדים עד מספר זה נכשלו, המספר אינו ראשוני. מתוצאה זו נובע שהוכחת ראשוניות של <math>n</math> היא בעיה בעלת [[סיבוכיות]] פולי-לוגריתמית.

==תיאור המבחן==
'''משפט''': אם לכל גורם ראשוני <math>q</math> של <math>n-1</math> קיים מספר <math>a</math> המקיים <math>a^{n-1}\equiv1\!\!\!\pmod{n},\,a^{(n-1)/q}\not\equiv1\!\!\!\pmod{n}</math>, אזי <math>n</math> הוא ראשוני.

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

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

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

== ראו גם==
*[[מספר ראשוני#מבחני ראשוניות|מבחן ראשוניות]]
*[[סדר (תורת החבורות)]]

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