סדרות לוקאס ומבחני ראשוניות

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

המבחן מתבסס על סדרת מספרים שנקראת סדרת לוקאס-להמר ומתחילה כך: \( 4,14,194,37634,1416317954 \). הנוסחה שלה פשוטה מאוד: \( a_{0}=4 \) ו-\( a_{n+1}=a_{n}^{2}-2 \). כלומר, כל איבר מתקבל על ידי העלאה בריבוע של קודמו וחיסור 2. כעת, למבחן: אם \( p \) הוא מספר ראשוני אז מספר מרסן \( M_{p}=2^{p}-1 \) הוא ראשוני אם ורק אם \( a_{p-2} \) מתחלק ב-\( M_{p} \). לכן רק צריך לחשב את \( a_{p-2} \) ולבדוק. בפועל החישוב הזה לא טריוויאלי לגמרי - מהר מאוד האיברים של לוקאס-להמר הופכים לענקיים בגודלם, אבל מצד שני לא צריך לזכור את כל האיבר אלא רק את השארית שלו בחלוקה ב-\( M_{p} \) ויש עוד תעלולים שלא אכנס אליהם כאן. השורה התחתונה היא שזה אלגוריתם יעיל מאוד.

אתם עשויים לשאול למה אני דורש ש-\( p \) יהיה ראשוני דווקא. הסיבה לכך פשוטה: אם \( n \) הוא מספר פריק, אז אין סיכוי ש-\( 2^{n}-1 \) יהיה ראשוני. כי נניח ש-\( n=ab \) אז \( 2^{ab}-1=\left(2^{a}\right)^{b}-1 \) וכשניקח את המשוואה הזו מודולו \( 2^{a}-1 \), נקבל \( 2^{a}\equiv1 \) ולכן נקבל \( 1^{b}-1\equiv0 \), כלומר \( 2^{a}-1 \) מחלק את \( 2^{n}-1 \) (וכך גם \( 2^{b}-1 \) ולכן עבור \( n \) לא ראשוני נמצא מחלק לא טריוויאלי של \( 2^{n}-1 \)). לא הבנתם מה עשיתי פה? זו הייתה בדיקה כדי לראות אם אתם מכירים את מושגי היסוד שיהיו הכרחיים בהמשך הפוסט. לכל הפחות יהיה צורך להכיר חשבון מודולרי.

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

הסיפור מתחיל ונגמר בסדרות לוקאס המדוברות. אלו סדרות של מספרים שלמים, שאסמן ב-\( u_{0},u_{1},u_{2},\dots \) שמקיימות את נוסחת הנסיגה \( u_{n}=au_{n-1}-bu_{n-2} \) כאשר \( a,b \) הם פרמטרים שלמים. הסדרה הידועה ביותר שהיא סדרת לוקאס היא סדרת מספרי פיבונאצ'י שמוגדרת על ידי \( F_{0}=0,F_{1}=1 \) ו-\( F_{n}=F_{n-1}+F_{n-2} \), כלומר זו סדרת לוקאס עם פרמטרים \( a=1,b=-1 \) ותנאי התחלה \( F_{0}=0 \) ו-\( F_{1}=1 \). יש עוד סדרות מספרים שמקיימות נוסחת נסיגה מסוג זה - למשל, מספרי מרסן בעצמם:

\( M_{n}=2^{n}-1=3\left(2^{n-1}-1\right)-2\left(2^{n-2}-1\right)=3M_{n-1}-2M_{n-2} \)

כלומר כאן \( a=3,b=2 \) ותנאי ההתחלה הם \( M_{0}=0,M_{1}=1 \).

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

לא ממש הגבלתי את תנאי ההתחלה האפשריים עבור סדרות לוקאס, אבל מסתבר שהסדרות המעניינות ביותר מתקבלות עבור שני סטים אפשריים של ערכי התחלה. ראשית, ערכי ההתחלה \( u_{0}=0,u_{1}=1 \) שנתנו לנו את פיבונאצ’י ואת מרסן, ושנית - תנאי ההתחלה \( u_{0}=2 \) ו-\( u_{1}=a \) (כאשר \( a \) הוא הפרמטר שמגדיר את נוסחת הנסיגה: \( u_{n}=au_{n-1}-bu_{n-2} \)). בינתיים אדבר על סדרות שמתקבלות מתנאי ההתחלה הראשון. נתחיל בלראות משהו מגניב שקורה ספציפית בפיבונאצ’י, ואז נכליל אותו.

הדבר המגניב הוא זה: אם \( n \) הוא מספר ראשוני, אז \( n \) חייב לחלק את מספר פיבונאצ’י במקום שהוא “כמעט \( n \)”. מה זאת אומרת “כמעט”? או שזה יהיה המספר במקום ה-\( n \), או שזה יהיה המספר במקום ה-\( n+1 \) או שזה יהיה המספר במקום ה-\( n-1 \). זה תלוי בתכונה כלשהי של \( n \). במפורש:

• אם \( n \) מתחלק ב-\( 5 \) אז \( n \) מחלק את \( F_{n} \).
• אם \( n \) מחזיר שארית 1 או 4 בחלוקה ב-5 אז \( n \) מחלק את \( F_{n-1} \).
• אם \( n \) מחזיר שארית 2 או 3 בחלוקה ב-5 אז \( n \) מחלק את \( F_{n+1} \).

בואו נראה דוגמאות. נכתוב את האיברים הראשונים של פיבונאצ’י: \( 0,1,1,2,3,5,8,13,21,34,55 \). עכשיו בואו נעבור על ראשוניים: 2 מחזיר שארית 2 בחלוקה ב-\( 5 \) ואכן מחלק את \( F_{3}=2 \). 3 אכן מחלק את \( F_{4}=3 \). 5 אכן מחלק את \( F_{5}=5 \). 7 אכן מחלק את \( F_{8}=21 \). 11 אכן מחלק את \( F_{10}=55 \), וזה נמשך ונמשך ונמשך. זו תוצאה ממש נחמדה! האם היא מספיקה כדי להוכיח שמספר הוא ראשוני? ובכן, לא: אפשר להראות, למשל, ש-323 מחלק את \( F_{324} \) אבל הוא לא ראשוני כי \( 323=17\cdot19 \). לכן למספר שמקיים את הקריטריון הזה קוראים פסאודוראשוני פיבונאצ'י. לא כדאי לזלזל במבחנים שבודקים אם מספר הוא פסאודוראשוני: זו דרך מאוד טובה לסנן מספרים פריקים לפני שזורקים עליהם אלגוריתם שיודע להוכיח ראשוניות והוא כנראה כבד יחסית. מבחן פסואודוראשוניות אחד כנראה לא יהיה מספיק, אבל אם משלבים כמה מקבלים סינון אפקטיבי מאוד.

עכשיו בואו נוריד חלק מהמיסטיקה סביב הניסוח של המשפט הזה. ה”כמעט במקום ה-\( n \)” הוא מעצבן כי הוא מייצר חלוקה למקרים שנראית שרירותית מאוד, אבל בפועל היא לא שרירותית בכלל: היא תלויה בשאלה האם \( n \) הוא שארית ריבועית מודולו \( 5 \). יש לי פוסט בנושא אבל הנה תזכורת: מספר \( a \) הוא שארית ריבועית מודולו \( n \) אם הוא ריבוע ב-\( \mathbb{Z}_{n}^{*} \), כלומר אם למשוואה \( x^{2}=n \) קיים פתרון ב-\( \mathbb{Z}_{n}^{*} \). ספציפית עבור \( z=5 \) קל לראות שעבור 1 ו-4 יש פתרונות (1 ו-2, כמובן) אבל עבור 2 ו-3 אין פתרונות (כי 3 בריבוע מודולו 5 נותן 4 ואילו 4 בריבוע נותן 1 - אלו השורשים הנוספים שיש ל-1 ו-4, כי בשדה כמו \( \mathbb{Z}_{5} \) אם למספר יש שורש יש לו בדיוק שני שורשים). שימו לב שההגדרה שלי דיברה על \( \mathbb{Z}_{n}^{*} \), כלומר על אוסף כל המספרים שזרים ל-5; לכן המקרה של \( n \) מתחלק ב-5 הוא מיוחד.

כעת, יש סימון מקובל לתיאור האם מספר הוא שארית ריבועית או לא, שהתגלה כשימושי במיוחד והוא שימושי גם כאן: אם \( p \) ראשוני ו-\( n \) הוא מספר כלשהו, אז \( \left(\frac{n}{p}\right)=1 \) אם \( n \) הוא שארית ריבועית מודולו \( p \), \( \left(\frac{n}{p}\right)=-1 \) אם \( n \) הוא לא שארית ריבועית אבל זר ל-\( p \), ואילו \( \left(\frac{n}{p}\right)=0 \) אם \( n \) לא זר ל-\( p \). לסימן הזה קוראים סימן לז'נדר (ובמקרה שבו ה”מכנה” הוא לא ראשוני, קוראים לו סימן יעקובי). צריך כמובן לומר במפורש שהסימן הזה לא מתאר שבר. קו השבר בין \( n \) ל-\( p \) הוא סתם סימון, ומההקשר מבינים שלא מדובר על שבר. עכשיו אפשר לנסח את המשפט בצורה קצת יותר קומפקטית: אם \( n \) הוא ראשוני, אז \( n \) מחלק את \( F_{n-\left(\frac{n}{5}\right)} \). הנה, הסימון כבר מתחיל לעבוד לטובתנו.

עד עכשיו נראה היה שתיארתי תכונה מעניינת של סדרת פיבונאצ'י. אבל בפועל מדובר על תכונה מעניינת של סדרות לוקאס באופן כללי - ליתר דיוק, אלו עם תנאי ההתחלה 0,1. הנה המשפט הכללי: תהא \( U_{k} \) סדרת לוקאס עם תנאי התחלה \( 0,1 \) ונוסחת נסיגה \( U_{k}=aU_{k-1}-bU_{k-2} \). נסמן \( \Delta=a^{2}-4b \). אם \( p \) הוא מספר ראשוני שזר ל-\( 2b\Delta \) אז \( p \) מחלק את \( U_{p-\left(\frac{\Delta}{p}\right)} \).

מה קורה אצל פיבונאצ’י? במקרה הזה \( a=1,b=-1 \) ולכן \( \Delta=1^{2}+4=5 \) - מכאן הגיע ה-5 הזה. כעת, \( 2b\Delta=10 \) ולכן כל ראשוני פרט ל-\( 2,5 \) זר ל-\( 2b\Delta \) (ועבורם המשפט עובד בכל מקרה כאן). לכן המסקנה היא ש-\( p \) מחלק את \( U_{p-\left(\frac{5}{p}\right)} \). זה נראה כמעט כמו המשפט על פיבונאצ’י רק ששמשהו התהפך כאן: כתוב \( \left(\frac{5}{p}\right) \) במקום \( \left(\frac{p}{5}\right) \). הסיבה לכך שאפשר לבצע את ההיפוך הזה היא משפט נפלא שנקרא משפט ההדדיות הריבועית שאומר שאם \( p,q \) הם ראשוניים אז \( \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)} \), ובמילים: אם \( p \) או \( q \) שקולים ל-1 מודולו 4 אז \( \left(\frac{p}{q}\right)=\left(\frac{q}{p}\right) \), ואם שניהם שקולים ל-3 מודולו 4 אז \( \left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right) \). מכיוון ש-\( 5 \) שקול ל-1 מודולו 4 אנחנו במקרה הראשון ולכן ניתן “להפוך” כפי שהפכנו.

עכשיו לשאלה המעניינת - למה המשפט הכללי נכון? כאן מגיעים הניסים והנפלאות. הרעיון הבסיסי יהיה לחשוב על אברי הסדרה \( U_{k} \) לא בתור “סתם” מספרים שלמים, אלא בתור יצורים שחיים בתוך מרחב גדול יותר - השדה הסופי \( \mathbb{F}_{p^{2}} \). תכף אסביר בדיוק על מה מדובר, אבל לפני כן אני רוצה להתלהב מהרעיון הכללי כאן. זו תופעה מאוד נפוצה במתמטיקה בכלל, ובתורת המספרים בפרט: יש לנו אובייקט שאנחנו מסוגלים להבין אינטואיטיבית, אבל פתאום צצות תכונות יפהפיות שלו שאין לנו מושג איך להסביר באמצעות התיאור הרגיל שלנו של האובייקט. רק כשאנחנו מתחילים לחשוב על האובייקט בתור משהו שחי בעולם גדול יותר, ומסובך יותר, ואולי גם נוגד אינטואיציה הרבה יותר, פתאום התכונות מתחילות לצוץ כמעט מאליהן. זה מתרחש בגלל שהאובייקט שלנו מקיים יחסי גומלין עם האובייקטים של העולם הגדול והמסובך יותר, גם אם מבחינתנו זה שקוף לחלוטין כל עוד אנחנו נשארים בחיק החמים של האינטואיציה שלנו, שמסתירה מפנינו את העולם הגדול יותר. כמה פעמים שמעתם מישהו אומר ש”הוא לא מבין למה מספרים מרוכבים הם מספרים בכלל”? זו דוגמת האבטיפוס: יש שלל תכונות שהדרך הנכונה להבין מדוע המספרים הממשיים/השלמים מקיימים אותן שצצות רק כשחושבים על המספרים הללו בתור יצורים שחיים בשדה המספרים המרוכבים. למרוכבים לא אכפת אם אתם מקבלים אותם או לא; הם קיימים, והם מרתקים, וגם אם אנחנו מנסים לאטום את החלון ולא לראות אותם, מדי פעם קרני שמש חודרות מבעד למעטה שלנו ונופלות על אותו חלק קטן מהמספרים המרוכבים שאנחנו מוכנים ברוב טובנו להכיר בקיומו.

טוב, מספיק עם הפילוסופיה; היא דרושה כדי להכין אתכם לזבנג שאני הולך לתת עוד שניה למי שלא רגיל לנושאים הללו. כאמור, אני רוצה לחשוב על ה-\( U_{k} \)-ים בתור איברים בשדה סופי עם \( p^{2} \) איברים. יש לי כאן הסברים על מהם שדות כאלו אז לא אכנס למלוא הפרטים כרגע. השאלה המעניינת מבחינתנו היא איך אנחנו רוצים לייצג את אברי השדה הסופי הזה. השיטה המקובלת לבנייה של שדה סופי בן \( p^{2} \) איברים היא זו: מתחילים מהשדה \( \mathbb{Z}_{p}=\left\{ 0,1,\dots,p-1\right\} \), ולוקחים פולינום \( f\left(x\right) \) ממעלה שניה מעליו שהוא אי פריק, כלומר שאין לו שורש ב-\( \mathbb{Z}_{p} \). ועכשיו מסתכלים על חוג המנה שמתקבל כשמחלקים את חוג הפולינומים מעל \( \mathbb{Z}_{p} \) באידאל שנוצר מהפולינום \( f\left(x\right) \). מה זה אומר בתכל’ס? שמסתכלים על קבוצת הפולינומים מהצורה \( sx+t \) עם פעולות חיבור וכפל “מודולו \( f\left(x\right) \)” - כלומר, אחרי שמחברים או כופלים מחלקים ב-\( f\left(x\right) \) ולוקחים את השארית (בפועל על חיבור זה לא משפיע, רק על כפל).

עכשיו מגיע החלק המוזר למראה. כזכור, אנחנו מסתכלים על הסדרה \( U_{k} \) שמוגדרת על ידי הפרמטרים \( a,b \). זה אומר שמתקיים \( U_{k+2}=aU_{k+1}-bU_{k} \). בואו נשחק לרגע משחק: במקום \( U_{k+i} \) נכתוב \( x^{i} \). כלומר, \( x^{2}=ax^{1}-bx^{0} \) או בקיצור \( x^{2}=ax-b \). נעביר אגפים ונקבל \( x^{2}-ax+b=0 \). בואו נקרא לפולינום שבצד שמאל \( f\left(x\right) \), כלומר \( f\left(x\right)=x^{2}-ax+b \). הפולינום הזה מאפשר לנו להגדיר את הסדרה \( U_{k} \) בתור סדרה של פולינומים באופן הבא, שייראה לכם מאוד מוזר במבט ראשון ולכן אני מבטיח שהוא מאוד שימושי:

\( U_{k}\triangleq\frac{x^{k}-\left(a-x\right)^{k}}{x-\left(a-x\right)}\left(\mbox{mod }f\left(x\right)\right) \)

מה טוב בהגדרה המוזרה הזו? שזו לא הגדרה רקורסיבית. מצד שני, קל לראות שהיא מגדירה את הסדרה \( U_{k} \) שתיארתי קודם. בפרט, זו נראית כמו סדרה של פולינומים, אבל בפועל נקבל סדרה של מספרים שלמים. כדי לראות את זה, בואו קודם כל נציב \( k=0 \) ונקבל

\( U_{0}=\frac{x^{0}-\left(a-x\right)^{0}}{x-\left(a-x\right)}=\frac{1-1}{x-\left(a-x\right)}=0 \)

וכעת נציב \( k=1 \) ונקבל

\( U_{1}=\frac{x^{1}-\left(a-x\right)^{1}}{x-\left(a-x\right)}=\frac{x-\left(a-x\right)}{x-\left(a-x\right)}=1 \)

אז קיבלנו את הערכים ההתחלתיים שציפינו להם. כעת, למה \( U_{k} \) מקיים את נוסחת הנסיגה? בשביל זה צריך להבין מה המשמעות של חישובים מודולו \( f\left(x\right) \). זה אומר שאנחנו יכולים להחליף כל מופע של \( x^{2}-ax+b \) באפס, או באופן שקול, להחליף כל מופע של \( x^{2} \) ב-\( ax-b \) וההפך. אז בואו נעשה חישובים עם הנשק החדש הזה שלנו:

\( x^{2}=ax-b \)

\( \left(a-x\right)^{2}=a^{2}-2ax+x^{2}=a^{2}-2ax+\left(ax-b\right)=a^{2}-ax-b=a\left(a-x\right)-b \)

ולכן:

\( x^{k+2}=x^{k}\left(ax-b\right)=ax^{k+1}-bx^{k} \)

\( \left(a-x\right)^{k+2}=\left(a-x\right)^{k}\left(a-x\right)^{2}=a\left(a-x\right)^{k+1}-b\left(a-x\right)^{k} \)

ומכאן:

\( U_{k+2}=\frac{x^{k+2}-\left(a-x\right)^{k+2}}{x-\left(a-x\right)}=a\frac{x^{k+1}-\left(a-x\right)^{k+1}}{x-\left(a-x\right)}-b\frac{x^{k}-\left(a-x\right)^{k}}{x-\left(a-x\right)}=aU_{k+1}-bU_{k} \)

כלומר, ה-\( U_{k} \) היא עדיין הסדרה המוכרת והאהובה עלינו, רק כתובה בצורה מוזרה עם פולינומים שבסוף בכלל לא באים לידי ביטוי כי כל האיקסים מצטמצמים. אבל הפולינומים הללו הם בדיוק ה”עולם רחב יותר” שאני מדבר עליו.

בואו נחזור לרגע לדבר על העולם ונראה במפורש איך מתנהגות פעולות החיבור והכפל בו. זכרו: הן מתנהגות כמו חיבור וכפל פולינומים רגיל, בתוספת היכולת שלנו להשתמש במשוואה \( x^{2}=ax-b \). לכן נקבל:

\( \left(s_{1}x+t_{1}\right)+\left(s_{2}x+t_{2}\right)=\left(s_{1}+s_{2}\right)x+\left(t_{1}+t_{2}\right) \)

\( \left(s_{1}x+t_{1}\right)\cdot\left(s_{2}x+t_{2}\right)=s_{1}s_{2}x^{2}+\left(s_{1}t_{2}+s_{2}t_{1}\right)x+t_{1}t_{2}= \)

\( \left(s_{1}t_{2}+s_{2}t_{1}+as_{1}s_{2}\right)x+\left(t_{1}t_{2}-bs_{1}s_{2}\right) \)

זה ייצוג מפורש של פעולות החשבון, גם עבור מי שלא מבין את הדיבורים הגבוהים על חלוקה באידאלים של חוגי פולינומים. עכשיו אפשר לעבור לאקשן של הוכחת המשפט. המשפט, כזכור, אומר שאם \( p \) הוא מספר ראשוני שזר ל-\( 2b\Delta \) אז \( p \) מחלק את \( U_{p-\left(\frac{\Delta}{p}\right)} \), כאשר \( \Delta=a^{2}-4b \).

הגיע הזמן להבין מאיפה הגיע \( \Delta \) הזה. אולי אתם זוכרים מהתיכון שזה סימון של דיסקרימיננטה, שזה “המשהו שמתחת לשורש” בפתרון משוואה ריבועית. זה לא מקרי. ההפרדה למקרים שלנו עוסקת בדיוק בשאלה האם הפולינום \( x^{2}-ax+b \) הוא אי-פריק (ואז חלוקה בו נותנת שדה) או שהוא פריק (ואז עדיין אפשר להגדיר את פעולות החשבון כמו למעלה אבל נקבל משהו שאינו שדה). לשם כך משתמשים בנוסחת השורשים, שנכונה גם מעל שדות סופיים: שורשי הפולינום הזה הם \( \frac{a\pm\sqrt{a^{2}-4b}}{2}=\frac{a\pm\sqrt{\Delta}}{2} \) ולכן יש לפולינום הזה שורש אם ורק אם ל-\( \Delta \) יש שורש, כלומר אם ורק אם \( \left(\frac{\Delta}{p}\right)=1 \) (בלתי אפשרי שיתקיים ש-\( \Delta \) היא 0 ב-\( \mathbb{Z}_{p} \) כי המשמעות של כך היא ש-\( \Delta \) לא זרה ל-\( p \), בניגוד להנחה שלנו).

אם \( \left(\frac{\Delta}{p}\right)=-1 \), כלומר \( \Delta \) איננו ריבוע, קיבלנו שאוסף הפולינומים שלנו מודולו \( f\left(x\right) \) הוא שדה. עכשיו מגיע השלב שבו אנחנו מגלים שמשתלם לנו לחשוב לא רק על מספרים שלמים אלא גם על עולם רחב יותר מזה - אפשר להשתמש בידע שיש לנו בתורת השדות. ספציפית, הידע הזה מלמד אותנו במקרה הזה שבתוך השדה שלנו, \( x^{p}=a-x \) ואילו \( \left(a-x\right)^{p}=x \). למה? ובכן, ראשית נשים לב לכך שבתוך השדה שבנינו, \( x \) הוא שורש של הפולינום \( f\left(t\right)=t^{2}-at+b \) (אני כותב אותו בכוונה עם \( t \) הפעם כדי לא ליצור בלבול - ה-\( x \) הוא איבר של ממש בשדה, בעוד שסימון המשתנה שאיתו אנחנו בוחרים לתאר פולינום הוא לגמרי בשליטתנו). כמו כן, אפשר לראות שגם \( a-x \) הוא שורש של הפולינום הזה, על ידי הצבה ישירה:

\( \left(a-x\right)^{2}-a\left(a-x\right)+b=a^{2}-2ax+x^{2}-a^{2}+ax+b=-ax+ax-b+b=0 \)

עכשיו, תוצאה בסיסית בתורת השדות היא שבהינתן שדה סופי \( \mathbb{F}_{p^{k}} \), הפונקציה \( a\mapsto a^{p} \) היא אוטומורפיזם של השדה, שזוכה לשם המיוחד אוטומורפיזם פרובניוס. ידוע גם שהפונקציה הזו היא הזהות בדיוק על שדה הבסיס \( \mathbb{F}_{p}=\mathbb{Z}_{p} \), ואנחנו יודעים בדיוק מה עושה אוטומורפיזם של שדה \( E \) שהוא הזהות בדיוק על שדה הבסיס \( F \), כשנותנים לו שורשים של פולינומים שהמקדמים שלהם כולם מתוך \( F \): הוא חייב לבצע פרמוטציה של השורשים הללו. כלומר, חופש הבחירה של האוטומורפיזם לאן הוא רוצה לשלוח את השורשים מוגבל לשורשים אחרים של אותו הפולינום. האבחנה הזו היא הבסיס לתורת גלואה, אבל לא אכנס לכך כרגע. השורה התחתונה היא שלמי שיש נסיון בתורת השדות ברור כמעט מייד שיתקיימו שני השוויונות שכתבתי למעלה. וזה אומר את הדבר הבא:

\( U_{p+1}=\frac{x^{p+1}-\left(a-x\right)^{p+1}}{x-\left(a-x\right)}=\frac{x\left(a-x\right)-\left(a-x\right)x}{x-\left(a-x\right)}=0 \)

כלומר, \( U_{p+1} \) מתחלק ב-\( p \), בדיוק כפי שרצינו.

המקרה השני, \( \left(\frac{\Delta}{p}\right)=1 \), הוא קצת שונה אבל בצורה שהופכת אותו לפשוט יותר. במקרה הזה אוסף הפולינומים שלנו לא מהווה שדה אלא “סתם” חוג - אז איזה חוג זה? בעזרת משפט השאריות הסיני בגרסה מוכללת שלו אפשר להראות שאם מחלקים חוג \( R \) במכפלה של אידאלים \( IJ \) אז מקבלים את המכפלה של חלוקת החוג בכל אידאל בנפרד, כלומר \( R/IJ\cong R/I\times R/J \). במקרה שלנו אנחנו מחלקים באידאל שנוצר על ידי פולינום; אם הפולינום מתפרק, אפשר לכתוב את האידאל שהוא יוצר בתור מכפלת האידאלים של המרכיבים של הפירוק. כל אחד מהם הוא פולינום ממעלה 1 ולכן החוג שמתקבל מחלוקה בהם איזומורפי לחוג המקורי. כל להטוטי האלגברה הללו מובילים למסקנה הפשוטה: במקרה השני החוג שלנו הוא \( \mathbb{Z}_{p}\times\mathbb{Z}_{p} \). החוג הזה נחמד מאוד כי קל לראות שכאשר מעלים איבר כלשהו בו בחזקת \( p \) מקבלים חזרה את האיבר המקורי. לכן במקרה הזה \( x^{p}=x \) ו-\( \left(a-x\right)^{p}=a-x \) ולכן אחרי צמצום (צריך לנמק למה אפשר לצמצם את האיברים הללו - נסו!) מקבלים \( x^{p-1}=\left(a-x\right)^{p-1}=1 \) ואנחנו מקבלים:

\( U_{p-1}=\frac{x^{p-1}-\left(a-x\right)^{p-1}}{x-\left(a-x\right)}=\frac{1-1}{x-\left(a-x\right)}=0 \)

כלומר \( U_{p-1} \) מתחלק ב-\( p \), כפי שרצינו.

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

המבחן אומר את הדבר הבא: בואו ניקח \( f\left(x\right)=x^{2}-ax+b \) כמו קודם ונסמן \( \Delta=a^{2}-4b \) כמו קודם, וניקח מספר \( n \) חיובי כלשהו שהוא זר ל-\( 2b \) ומקיים \( \left(\frac{\Delta}{n}\right)=-1 \). ראשית כל נבדוק האם \( U_{n+1} \) מתחלק ב-\( n \), כמו קודם: אם \( n \) ראשוני זה חייב להתקיים. אבל זה לא מספיק כדי להוכיח שהוא ראשוני. אבל אפשר לחזק את זה: בואו ניקח מחלק כלשהו של \( n+1 \) ונסמן אותו ב-\( F \). נניח שאנחנו מכירים את הפירוק לגורמים ראשוניים של \( F \). לכל גורם ראשוני \( q \) של \( F \), נבדוק אם \( U_{\frac{n+1}{q}} \) זר ל-\( n \). אם כן, זה מוכיח שלכל \( p \) ראשוני שמחלק את \( n \) מתקיים \( p\equiv\left(\frac{\Delta}{p}\right) \) מודולו \( F \).

רגע, מה? המסקנה של המשפט ממש לא ברורה. את מי זה מעניין? ובכן עבור ערכים קטנים של \( F \) זה לא כל כך מעניין. אבל נניח ש-\( n \) לא ראשוני ולקחנו \( F>\sqrt{n}+1 \), אז בהכרח כל הגורמים הראשוניים של \( n \) יהיו קטנים מ-\( F \), ולכן מודולו \( F \) יהיו שווים לעצמם. מה שאומר שהמשוואה \( p\equiv\left(\frac{\Delta}{p}\right) \) לא תוכל להתקיים בכלל. מכאן שאם מצאנו \( F>\sqrt{n}+1 \) שמקיים את הבדיקה שלעיל (\( U_{\frac{n+1}{q}} \) זר ל-\( n \) לכל \( q \) ראשוני שמחלק את \( F \)), זה מוכיח ש-\( n \) ראשוני.

למה זה נכון? ובכן, ראשית בואו נסמן ב-\( r_{f}\left(n\right) \) את האינדקס של המספר הראשון בסדרה \( U_{k} \) שמתחלק ב-\( n \). קוראים לזה דרגת ההופעה של \( n \). אפשר להוכיח עם קצת עבודה טכנית שאדלג עליה שדרגת ההופעה של \( n \) מחלקת כל מופע אחר של \( n \): דהיינו, \( U_{k} \) כלשהו מתחלק ב-\( n \) אם ורק אם \( k \) מתחלק ב-\( r_{f}\left(n\right) \). ניקח עכשיו מספר ראשוני \( p \) שמחלק את \( n \): המשפט שראינו קודם אמר שאם \( p \) ראשוני אז הוא מחלק את \( U_{p-\left(\frac{\Delta}{p}\right)} \). כלומר, קיבלנו ש-\( r_{f}\left(p\right) \) מחלק את \( p-\left(\frac{\Delta}{p}\right) \), ובניסוח שקול: \( p\equiv\left(\frac{\Delta}{p}\right) \) מודולו \( r_{f}\left(p\right) \) מתקיים תמיד. זו המשוואה שרצינו להגיע אליה, אבל לא מודולו \( r_{f}\left(p\right) \) אלא מודולו מחלק \( F \) של \( n+1 \) שמקיים כך-וכך. לצורך כך יספיק לנו להוכיח ש-\( F \) שמקיים כך-וכך מחלק את \( r_{f}\left(p\right) \) (כי אם \( F \) מחלק את \( r_{f}\left(p\right) \) הוא מחלק גם כל דבר שמתחלק על ידי \( r_{f}\left(p\right) \)).

בואו נזכור מה הכך-וכך ש-\( F \) מקיים. ראשית, \( U_{n+1} \) מתחלק ב-\( n \) ולכן בפרט מתחלק ב-\( p \), ואנחנו יודעים ש-\( F \) מחלק את \( n+1 \). אם היינו יכולים לטעון משהו כמו \( r_{f}\left(p\right)=n+1 \) היינו מסיימים כאן. אבל זה לא בהכרח נכון. אנחנו יודעים שבגלל ש-\( p \) מחלק את \( U_{n+1} \) אז \( r_{f}\left(p\right) \) מחלק את \( n+1 \), אבל הוא לא חייב להיות שווה לו. אני חושב שהכי ברור להציג את הסיטואציה הזו באופן הבא: אפשר לכתוב את הפירוק לגורמים של \( n+1 \): \( n+1=q_{1}^{k_{1}}\cdots q_{t}^{k_{t}} \). כעת, המשמעות של “\( r_{f}\left(p\right) \) מחלק את \( n+1 \)” הוא שיש ל-\( r_{f}\left(p\right) \) את אותו פירוק לגורמים אבל עם חזקות שהן אולי נמוכות יותר. במילים אחרות, אפשר להגיע מ-\( n+1 \) אל \( r_{f}\left(p\right) \) על ידי סדרה של צעדים, שבכל אחד מהם אנחנו לוקחים גורם ראשוני \( q \) של \( n+1 \) ומחלקים את המספר שיש לנו ביד כרגע בגורם הזה. והנה הפאנץ’: כל עוד הגורם \( q \) הזה איננו גורם של \( F \), אז \( F \) ימשיך לחלק את התוצאה שלנו (כי אנחנו לא מקטינים את החלק של \( F \) בתוך \( n+1 \)).

כאן נכנס לתמונה התנאי הנוסף שאנחנו בודקים: אם עבור גורם \( q \) של \( F \) מתקיים ש-\( U_{\frac{n+1}{q}} \) זר ל-\( n \), אז בפרט הוא לא מתחלק על ידי אף גורם של \( n \), כלומר \( p \) לא מחלק את \( U_{\frac{n+1}{q}} \). זה מבטיח שלא ייתכן ש-\( r_{f}\left(p\right) \) יחלק את \( \frac{n+1}{q} \) כי אמרנו שאם אינדקס ההופעה של \( p \) מחלק אינדקס אחר, אז \( p \) מופיע גם באינדקס הזה (דהיינו, \( p \) מחלק את \( U \) עבור האינדקס הזה). המסקנה היא שבמעבר מ-\( n+1 \) אל \( r_{f}\left(p\right) \) אנחנו לא מחלקים אף פעם ב-\( q \), עבור אף \( q \) שהוא מחלק של \( F \). לכן התוצאה שנקבל בסוף, שהיא \( r_{f}\left(p\right) \), מתחלקת ב-\( F \) וסיימנו את ההוכחה הזו.

יפה, עוד עצירה לצורך השבת הנשימה והתמקדות מה שכבר עשינו ומה שנשאר לעשות. מה שעשינו היה להוכיח מבחן הוכחת ראשוניות כללי, שנקרא “מבחן ה-\( n+1 \)”. אני אומר “מבחן הוכחת ראשוניות” כי המבחן הזה לא יודע להוכיח שמספר הוא לא ראשוני; הוא רק יודע להוכיח, עבור חלק מהמספרים הראשוניים, שהם אכן כאלו. למבחן הזה יש חיסרון בולט - צריך להכיר את הפירוק לגורמים של \( n+1 \), ובאופן כללי בעיית הפירוק לגורמים היא קשה משמעותית יותר מבעיית בדיקת הראשוניות. עדיין, זה שמדובר על בעיה קשה לא אומר שלפעמים לא קל לפרק מספרים לגורמים. נניח שיש לכם מספר \( n \) שממש קריטי עבורכם להוכיח שהוא ראשוני והאלגוריתמים הרגילים רצים ורצים עליו ולא מסיימים - אין שום סיבה לא לתת למבחן ה-\( n+1 \) הזדמנות, אולי במזל יוצא שאת \( n+1 \) דווקא קל לפרק לגורמים במקרה הזה ואז אפשר יהיה להשתמש במבחן. כל כלי נוסף שמאפשר לנו להוכיח ראשוניות הוא דבר טוב.

אבל פרט להצדקות הכלליות הללו, המבחן מן הסתם מעניין במיוחד במקרה שבו \( n+1 \) הוא מספר פשוט במיוחד, ואין סיטואציה פשוטה יותר מאשר זו שבה \( n \) הוא מספר מרסן, כלומר \( n=2^{k}-1 \). במקרה הזה, \( n+1 \) הוא פשוט חזקה של 2. לא רק שאנחנו יודעים לפרק אותה עד הסוף, יש לנו גם גורם יחיד, וגורם שהוא בסיסי מאוד. זה לגמרי מזמין נסיון להוכיח שבמקרה הספציפי הזה, אפשר לעשות יותר מסתם להוכיח ראשוניות בחלק מהמקרים - אנחנו הרי רוצים מבחן שעונה תשובה ודאית של כן/לא.

בשביל לבצע את הצעד האחרון, אנחנו צריכים וריאציה על מבחן ה-\( n+1 \) שהיא טיפ-טיפה יותר מתאימה לנו. בשביל לעשות את זה, אנחנו מכניסים לתמונה סוג חדש של סדרת לוקאס שהזכרתי בחטף בתחילת הפוסט: סדרה \( V_{k} \) שגם היא מוגדרת בעזרת נוסחת נסיגה \( V_{k+2}=aV_{k+1}-bV_{k} \), אבל תנאי ההתחלה שלה שונים: \( V_{0}=2,V_{1}=a \). גם לסדרה הזו יש ייצוג נחמד בתור פולינומים: \( V_{k}\triangleq x^{k}+\left(a-x\right)^{k} \). אם תזכרו ש-\( U_{k}\triangleq\frac{x^{k}-\left(a-x\right)^{k}}{x-\left(a-x\right)} \) בוודאי תראו מייד שמתקיים \( U_{k}V_{k}=U_{2k} \) (זה נובע מהתכונה הנחמדה \( \left(a+b\right)\left(a-b\right)=a^{2}-b^{2} \)), כך ששתי הסדרות הללו מקיימות ביניהם קשרים ברורים למדי.

בואו ננסח את מבחן ה-\( n+1 \) בוריאציה שמערבת את ה-\( V_{k} \)-ים הללו: אם \( n \) זר ל-\( 2b \) ו-\( \left(\frac{\Delta}{n}\right)=-1 \), ניקח מחלק זוגי \( F \) של \( n+1 \) ונבדוק את שני התנאים הבאים:

• \( V_{F/2} \) מתחלק ב-\( n \).
• \( V_{F/2q} \) זר ל-\( n \) עבור כל \( q \) אי זוגי שמחלק את \( F \).

אז במקרה הזה קורה מה שקרה קודם - כל \( p \) שמחלק את \( n \) מקיים \( p\equiv\left(\frac{\Delta}{p}\right) \) מודולו \( F \).

הניסוח הזה מושלם עבור מספרי מרסן בגלל שהתנאי השני בכלל לא יכול לבוא לידי ביטוי: אם \( F \) מחלק את \( n+1 \), שהוא חזקה של 2, אז גם \( F \) הוא בסך הכל חזקה של 2 ולכן אין לו גורמים אי זוגיים. בואו נסביר בזריזות למה הגרסה הזו של מבחן ה-\( n+1 \) נכונה ואז נגיע סוף סוף להוכחת לוקאס-להמר.

מן הסתם אין לי כוונה להוכיח את מבחן ה-\( n+1 \) החדש הזה מאפס - אני מבצע פה רדוקציה למבחן הקודם, עם ה-\( U_{k} \)-ים. ראשית, אני צריך להראות ש-\( U_{n+1} \) מתחלק ב-\( n \). אם \( F \) מחלק את \( n+1 \) יהיה מספיק להוכיח ש-\( U_{F} \) מתחלק ב-\( n \) (כי אפשר להראות שאם \( k \) מחלק את \( t \) אז \( U_{k} \) מחלק את \( U_{t} \)). מכיוון ש-\( U_{F}=U_{F/2}V_{F/2} \) ומכיוון שאנחנו מניחים ש-\( V_{F/2} \) מתחלק ב-\( n \), יש לנו את התנאי הזה.

התנאי השני של מבחן ה-\( n+1 \) המקורי הוא ש-\( U_{\frac{n+1}{q}} \) זר ל-\( n \) עבור כל מחלק ראשוני \( q \) של \( F \). בשביל זה מספיק להראות ש-\( U_{\frac{F}{2q}} \) זר ל-\( n \) (כי \( U_{\frac{F}{2q}} \) מחלק את \( U_{\frac{n+1}{q}} \)), ובשביל זה מספיק להראות ש-\( U_{F/2} \) זר ל-\( n \). שימו לב שאנחנו כבר יודעים ש-\( V_{F/2} \) לא רק שהוא לא זר ל-\( n \) אלא שהוא ממש מתחלק בו, כלומר כל מחלק של \( n \) מחלק את \( V_{F/2} \). לכן כדי לסיים את זה מספיק להוכיח שלכל \( k \), אין ל-\( U_{k},V_{k} \) בו זמנית מחלקים משותפים שהם גם מחלקים של \( n \). ליתר דיוק, נראה שכל מחלק משותף כזה חייב לחלק את \( 2b \), ונשתמש בהנחה שלנו ש-\( 2b \) זר ל-\( n \).

הנימוק עכשיו חוזר להגדרה הבסיסית של \( U_{k},V_{k} \). נניח ש-\( p \) הוא מחלק ראשוני של \( n \) שמחלק בו זמנית את \( U_{k} \) ואת \( V_{k} \). אז יש לנו את שתי המשוואות הבאות מודולו \( p \) (ומודולו \( f\left(x\right) \) אבל מי זוכר את זה): \( \frac{x^{k}-\left(a-x\right)^{k}}{x-\left(a-x\right)}=0 \) ו-\( x^{k}+\left(a-x\right)^{k}=0 \). מהראשונה נקבל את \( x^{k}-\left(a-x\right)^{k}=0 \) ואחרי שנחבר את שתיהן נקבל \( 2x^{k}=0 \). אפשר לצמצם פה ב-2 כי הוא זר ל-\( p \), ולכן נקבל \( x^{k}=0 \). איך זה קשור ל-\( b \)? ובכן, \( b=x\left(a-x\right) \) מודולו \( f\left(x\right) \) (כי \( f\left(x\right) \) הוא הפולינום \( x^{2}-ax+b \)) ולכן \( b^{k}=x^{k}\left(a-x\right)^{k}=0 \) מודולו \( f\left(x\right) \) ו-\( p \). בפרט, \( p \) מחלק את \( b^{k} \) ולכן הוא מחלק את \( b \) וסיימנו.

אנחנו ממש בסיום. הראינו וריאציה למבחן ה-\( n+1 \) שמשתמשת בסדרת ה-\( V \)-ים במקום בסדרת ה-\( U \)-ים. עכשיו נבחן מה קורה כשאנחנו משתמשים במבחן הזה ספציפית על מספרי מרסן. במקרה הזה, \( n=M_{p}=2^{p}-1 \) עבור \( p \) ראשוני כלשהו. כמו כן, אנחנו צריכים להחליט על \( f\left(x\right) \) קונקרטי שנבנה את המבחן סביבו - מה שיוצא טוב במקרה הזה הוא \( f\left(x\right)=x^{2}-4x+1 \), דהיינו \( a=4,b=1 \), ולכן \( \Delta=a^{2}-4b=12 \). האם \( n \) זר ל-\( 2\Delta=24 \)? הוא בוודאי לא זוגי, אבל אולי הוא מתחלק ב-3? ובכן, לא: 2 בחזקת מספר אי זוגי שקול תמיד ל-2 מודולו 3 ולכן חזקה של 2 פחות 1 שקולה ל-1 מודולו 3. זה מראה ש-\( n \) זר ל-\( \Delta \). עדיין צריך להשתכנע ש-\( \left(\frac{\Delta}{n}\right)=-1 \) כדי שאפשר יהיה להשתמש במבחן. חישוב של סימן יעקובי שכזה הוא עניין סטנדרטי למדי שלא אוכיח את פרטיו פה: הרעיון הוא ש-\( \left(\frac{\Delta}{n}\right)=\left(\frac{24}{n}\right)=\left(\frac{2}{n}\right)\left(\frac{4}{n}\right)\left(\frac{3}{n}\right)=\left(\frac{2}{n}\right)\left(\frac{3}{n}\right) \) ועכשיו אפשר לטפל בנפרד במוכפלים. ידוע ש-\( \left(\frac{2}{n}\right)=1 \) אם \( n \) שקול ל-7 מודולו \( 8 \) (וזה יהיה המקרה פה כי \( n+1 \) הוא חזקה גבוהה של 2 ולכן מתחלק ב-8). עבור \( \left(\frac{3}{n}\right) \) צריך להשתמש במשפט ההדדיות: \( \left(\frac{3}{n}\right)=-\left(\frac{n}{3}\right) \) (המינוס נובע מכך שגם ה-3 שב”מונה” וגם ה-\( n \) שב”מכנה” הם שניהם 3 מודולו 4). כעת, אפשר להחליף את \( n \) שב”מונה” במספר ששקול לו מודולו 3, שהוא כאמור 2, ואנחנו יודעים ש-2 איננו שארית ריבועית מודולו 3, ולכן נקבל פה \( -\left(\frac{n}{3}\right)=-\left(-1\right)=1 \) בסופו של דבר.

עכשיו נותר לבחור מחלק זוגי \( F \) של \( n+1 \) כדי להפעיל עליו את המבחן. משתלם לבחור כאן את \( 2^{p-1} \). עם הבחירה הזו, התנאי הראשון של המבחן שיש לבדוק הוא ש-\( V_{2^{p-2}} \) מתחלק ב-\( M_{p} \). והתנאי השני? הוא נעלם, כי הוא מערב מחלקים אי זוגיים של \( F \) ואין כאלו.

נותרנו, אם כן, עם השאלה איך אפשר לחשב את \( V_{2^{p-2}} \). כאן סוף סוף נכנסת לתמונה סדרת לוקאס-להמר מתחילת הפוסט. זו שהוגדרה באמצעות הכלל \( a_{0}=4 \) ו-\( a_{n+1}=a_{n}^{2}-2 \). זו פשוט \( V_{k} \) עם הפולינום המגדיר \( x^{2}-4x+1 \) בתחפושת, כשאנחנו מתקדמים ב”קפיצות” וכל פעם מכפילים את האינדקס שלנו. קל לראות את זה מההגדרה ה”פולינומית” של \( V_{k} \):

\( V_{2k}=x^{2k}+\left(4-x\right)^{2k}=\left(x^{k}+\left(4-x\right)^{k}\right)^{2}-2x^{k}\left(4-x\right)^{k}\equiv V_{k}^{2}-2 \)

כאשר המעבר האחרון הוא מודולו \( f\left(x\right)=x^{2}-4x+1 \) (מה שחוקי לעשות כי כל הסדרה מוגדרת מודולו הפולינום הזה מלכתחילה).

גם את תנאי ההתחלה קל להבין כעת: אמרנו ש-\( V_{0}=2 \) ו-\( V_{1}=a \), ובמקרה שלנו \( V_{1}=4 \). כלומר, הסדרה \( a_{n} \) באמת מוגדרת בתור \( a_{0}=V_{1} \) ובאופן כללי, \( a_{n}=V_{2^{n}} \). לכן \( a_{p-2} \) הוא בדיוק \( V_{2^{p-2}} \) שלנו, כמבוקש.

האם סיימנו? לא! עדיין לא! זאת מכיוון שראינו רק כיוון אחד: מבחן ה-\( n+1 \) מוכיח רק שאם \( n \) עובר אותו, אז \( n \) ראשוני. אבל זה עדיין לא מוכיח שאם \( n \) ראשוני אז בהכרח הוא יעבור את המבחן. במילים אחרות, אנחנו עדיין צריכים להראות שאם \( M_{p} \) ראשוני אז \( a_{p-2} \) יתחלק על ידו. זה דומה באופי שלו למבחן הפיבונאצ’י מתחילת הפוסט, וגם ההוכחה די דומה.

נניח אם כן ש-\( n \) הוא אכן ראשוני. כבר ראינו קודם ש-\( \left(\frac{\Delta}{n}\right)=-1 \) במקרה הנוכחי, ולכן כשמסתכלים על חוג הפולינומים מודולו \( n \) ו-\( f\left(x\right) \) מקבלים שדה סופי עם \( n^{2} \) איברים (זה דומה למה שהלך בהוכחה של פיבונאצ’י). בשדה כזה, כפי שראינו קודם, מתקיים \( x^{n}=4-x \). עכשיו נבצע להטוט אלגברי שמטרתו לחשב את \( \left(x-1\right)^{n+1} \) בשתי דרכים שונות. החישובים שלנו יתבצעו כולם בתוך השדה, כלומר אני אעשה הכל מודולו \( n \) ומודולו \( f\left(x\right) \) (דהיינו תוך שימוש בשוויון \( x^{2}=4x-1 \)) בלי להזכיר זאת אפילו. כעת:

\( \left(x-1\right)^{2}=x^{2}-2x+1=2x \)

ולכן:

\( \left(x-1\right)^{n+1}=\left(2x\right)^{\frac{n+1}{2}}=2\cdot2^{\frac{n-1}{2}}x^{\frac{n+1}{2}} \)

אני רוצה לנטרל את ה-\( 2^{\frac{n-1}{2}} \) הזה שבאמצע ולטעון שהוא שווה ל-1 (מודולו \( n \)); זו עוד תוצאה סטנדרטית על שאריות ריבועיות שלא אוכיח כרגע (לכל מספר \( a \) וראשוני \( p \) מתקיים ש-\( \left(\frac{a}{p}\right)=a^{\frac{p-1}{2}} \) מודולו \( p \)). קיבלנו, אם כן, את השוויון

\( \left(x-1\right)^{n+1}=2x^{\frac{n+1}{2}} \)

עכשיו לחישוב בדרך השניה. אני הולך להתבסס על כך ש-\( \left(a+b\right)^{n}=a^{n}+b^{n} \) מודולו \( n \) (זה נכון רק כש-\( n \) ראשוני, כמו במקרה שלנו) ולכן \( \left(x-1\right)^{n}=x^{n}+\left(-1\right)^{n}=x^{n}-1 \) (המעבר האחרון נכון רק כש-\( n \) אי זוגי, כמו במקרה שלנו) ועל מה שהזכרתי לפני רגע, ש-\( x^{n}=4-x \):

\( \left(x-1\right)^{n+1}=\left(x-1\right)\left(x-1\right)^{n}=\left(x-1\right)\left(x^{n}-1\right)=\left(x-1\right)\left(3-x\right)=4x-x^{2}-3=-2 \)

ולכן קיבלנו:

\( 2x^{\frac{n+1}{2}}=-2 \)

כלומר:

\( x^{\frac{n+1}{2}}=-1 \).

בואו ניזכר עכשיו מה זה \( n \): זה \( n=2^{p}-1 \), כלומר \( \frac{n+1}{2}=2^{p-1} \). לכן קיבלנו \( x^{2^{p-1}}=-1 \). את כל העסק הזה אפשר להעלות בחזקת \( n \) כדי להפוך את ה-\( x \) ל-\( 4-x \); אגף ימין לא ישתנה כי \( n \) אי-זוגי. נקבל \( \left(4-x\right)^{2^{p-1}}=-1 \). מכיוון ש-\( U_{2^{p-1}} \) הוא הפרש שני אלו חלקי משהו מודולו \( n \), נקבל שהוא מתחלק ב-\( n \). עכשיו, \( U_{2^{p-1}}=U_{2^{p-2}}V_{2^{p-2}} \); מכיוון ש-\( n \) ראשוני, אם הוא מחלק את המכפלה שלהם הוא חייב לחלק אחד מהם. אם הוא מחלק את \( V_{2^{p-2}} \), סיימנו; זה בדיוק מה שרצינו להראות. נשאר רק להשתכנע שהוא לא מחלק את \( U_{2^{p-2}} \). אם הוא כן, אז נקבל את השוויון \( x^{2^{p-2}}=\left(4-x\right)^{2^{p-2}} \), ועל כן:

\( -1=x^{2^{p-1}}=x^{2^{p-2}}\cdot x^{2^{p-2}}=x^{2^{p-2}}\left(4-x\right)^{2^{p-2}}=\left(x\left(4-x\right)\right)^{2^{p-2}}=1^{2^{p-2}}=1 \)

וזו סתירה, כי גם מודולו \( f\left(x\right) \) ומודולו \( n \), עדיין \( 1\ne-1 \), מה שמסיים את ההוכחה.

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