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

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

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

המבחן מחשב בצורה מהירה את האבר ה־ בסדרת לוקאס ובודק האם הוא שקול ל־0 מודולו (כאשר הוא המספר שצריך לבדוק את ראשוניותו).

המבחן

נתונים מספר ראשוני ומספר מרסן המתאים לו . המשימה היא לבדוק האם ראשוני. נגדיר סדרה ברקורסיה:

משפט. המספר ראשוני אם ורק אם .

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

תמצית הוכחת המשפט

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

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

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

הכיוון ההפוך דומה, אלא שבמקום השדה בגודל יש לחשב בשדה בגודל כאשר גורם ראשוני של שעבורו 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.

קישורים חיצוניים


Logo hamichlol.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0