מבחן לוקאס-להמר למספרי מרסן
מתוך ויקיפדיה, האנציקלופדיה החופשית
במתמטיקה, מבחן לוקאס להמר הוא מבחן ראשוניות למספרי מרסן. המבחן פותח במקור בידי אדוארד לוקאס ב-1878 ולאחר מכן שופר בידי דריק הנרי להמר בשנות השלושים. על-שם אותם שני מתמטיקאים קרוי גם מבחן ראשוניות כללי, מבחן לוקאס-להמר.
תוכן עניינים |
[עריכה] המבחן
נתונים מספר ראשוני 2 < p, ומספר מרסן המתאים לו,
. המשימה היא לבדוק האם M ראשוני. נגדיר סדרה
ברקורסיה:
, ולכל
מוגדר
.
משפט. המספר M הוא ראשוני אם ורק אם
.
זהו מבחן יעיל ביותר, והוא משמש עד היום לבדיקת ראשוניות של מספרי מרסן. החישוב מבוצע כולו מודולו M, ודורש כ- p פעולות של העלאה בריבוע. בכתיב בינארי אלו פעולות מהירות יחסית: הריבוע האמיתי של מספר מתקבל מסיכום ההזזות שלו כלפי מעלה, וחישוב השארית מודולו M מהיר במיוחד מכיוון ש-
, כך שתוצאת ההעלאה בריבוע מודולו M היא סכום שתי המחציות בריבוע שהתקבל. בסך הכול מדובר בכ-
פעולות בינאריות, הישג חסר תחרות בין מבחני הראשוניות השונים.
[עריכה] תמצית הוכחת המשפט
נסתפק כאן בסקירה של ההוכחה לכיוון אחד של המשפט: אם M ראשוני, אז
.
מכיוון ש- p איזוגי,
ולכן M הוא שארית ריבועית מודולו 3. אבל
, ולכן משפט ההדדיות הריבועית מבטיח כי 3 איננו שארית ריבועית מודולו M. מכיוון שכך, סיפוח השורש הריבועי x של 3 לשדה
יוצר את השדה הסופי מסדר
. בשדה הזה, נסמן
.
כעת קל להווכח (באינדוקציה) ש-
, ובסופו של דבר
אם ורק אם
. מכיוון שהשדה בעל מאפיין M, מתקיים
, כלומר
. כדי להשלים חלק זה של ההוכחה, יש להראות שלשורש
של
אין, בתורו, שורש ריבועי.
הכיוון ההפוך דומה, אלא שבמקום השדה בגודל
יש לחשב בשדה בגודל
כאשר Q הוא גורם ראשוני של M שעבורו 3 איננו שארית ריבועית.
[עריכה] ראו גם
- מבחן לוקאס-להמר הכללי
- סדרת לוקאס
[עריכה] לקריאה נוספת
Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective, 1st edition, Springer. ISBN 0387947779. Section 4.2.1: The Lucas-Lehmer test, pp.167–170.

