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

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

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

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

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

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

$latex 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}$

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

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

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

הדבר המגניב הוא זה: אם $latex n$ הוא מספר ראשוני, אז $latex n$ חייב לחלק את מספר פיבונאצ'י במקום שהוא "כמעט $latex n$". מה זאת אומרת "כמעט"? או שזה יהיה המספר במקום ה-$latex n$, או שזה יהיה המספר במקום ה-$latex n+1$ או שזה יהיה המספר במקום ה-$latex n-1$. זה תלוי בתכונה כלשהי של $latex n$. במפורש:

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

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

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

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

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

מה קורה אצל פיבונאצ'י? במקרה הזה $latex a=1,b=-1$ ולכן $latex \Delta=1^{2}+4=5$ – מכאן הגיע ה-5 הזה. כעת, $latex 2b\Delta=10$ ולכן כל ראשוני פרט ל-$latex 2,5$ זר ל-$latex 2b\Delta$ (ועבורם המשפט עובד בכל מקרה כאן). לכן המסקנה היא ש-$latex p$ מחלק את $latex U_{p-\left(\frac{5}{p}\right)}$. זה נראה כמעט כמו המשפט על פיבונאצ'י רק ששמשהו התהפך כאן: כתוב $latex \left(\frac{5}{p}\right)$ במקום $latex \left(\frac{p}{5}\right)$. הסיבה לכך שאפשר לבצע את ההיפוך הזה היא משפט נפלא שנקרא משפט ההדדיות הריבועית שאומר שאם $latex p,q$ הם ראשוניים אז $latex \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)}$, ובמילים: אם $latex p$ או $latex q$ שקולים ל-1 מודולו 4 אז $latex \left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$, ואם שניהם שקולים ל-3 מודולו 4 אז $latex \left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)$. מכיוון ש-$latex 5$ שקול ל-1 מודולו 4 אנחנו במקרה הראשון ולכן ניתן "להפוך" כפי שהפכנו.

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

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

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

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

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

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

וכעת נציב $latex k=1$ ונקבל

$latex 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$

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

$latex x^{2}=ax-b$

$latex \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$

ולכן:

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

$latex \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}$

ומכאן:

$latex 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}$

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

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

$latex \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)$

$latex \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}=$

$latex \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)$

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

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

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

$latex \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$

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

$latex 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$

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

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

$latex 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$

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

סיימנו את ההוכחה של משפט מאוד נחמד שנותן לנו מבחן של פסאודוראשוניות, אבל בואו נתאפס לרגע – התחלנו את הפוסט הזה עם אלגוריתם לוקאס-להמר ואנחנו עדיין ממש לא שם. על פניו כל מה שעשינו כרגע בכלל לא היה קשור. בפועל אנחנו כבר מאוד קרובים אל לוקאס-להמר, אבל לפני כן אני צריך להציג מבחן כללי יותר שיכול להוכיח ראשוניות – נקרא לו "מבחן ה-$latex n+1$". לוקאס-להמר יתקבל בתור מקרה פרטי נחמד במיוחד שלו.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$latex 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$

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

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

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

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

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

ולכן:

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

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

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

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

$latex \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$

ולכן קיבלנו:

$latex 2x^{\frac{n+1}{2}}=-2$

כלומר:

$latex x^{\frac{n+1}{2}}=-1$.

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

$latex -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$

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

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

כתיבת תגובה

האימייל לא יוצג באתר.