אז מה זה חשבון מודולרי?

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

לפני שנתחיל להיכנס לפרטים, הנה האינטואיציה הקלאסית: חשבון מודולורי הוא מה שכולנו עושים כשאנחנו מנסים לדעת מה תהיה השעה עוד כך וכך שעות. אם עכשיו השעה היא 19:00 ואנחנו שואלים “מה תהיה השעה עוד 10 שעות?” אנחנו מוסיפים 10 ל-19, מקבלים 29, ואז מחלקים ב-24 (מספר השעות ביממה), לוקחים את השארית - 5, וזו התשובה. חלקנו עושים את זה אחרת, כמובן; ראשית שואלים “עוד כמה שעות יש עד 24?”, רואים שזה 5, ואומרים “אוקיי, אז אחרי חצות יש עוד 5 שעות להוסיף, ומגיעים ל-5” אבל האפקט בשני המקרים הוא אותו אפקט, ואנחנו מקבלים את המספר שמתקבל מפעולת החשבון ה”רגילה” כשאחריה מחלקים ב-24 ולוקחים את השארית. חשבון מודולרי זה בדיוק זה, רק לאו דווקא עם 24 בתור מה שמחלקים בו.

ועכשיו בואו נעבור לפרטים.

מה זה חשבון “רגיל”, כולנו יודעים - יש לנו מספרים, יש לנו פעולות של חיבור, כפל, חיסור וחילוק, ואנחנו עושים איתן… דברים. בדרך כלל אנחנו מתחילים את המשחק מהמספרים הטבעיים - \( 0,1,2,3,\dots \) (שאני כולל בהם גם את 0). עכשיו, אני רוצה שתשימו לב לכך שבמובן מסויים אפשר להסתפק רק בפעולות של חיבור וכפל, ולהגדיר חיסור וחילוק באמצעותן. למשל, הפתרון למשוואה \( x=5-2 \) הוא מספר \( x \) אשר מקיים \( 2+x=5 \) (כלומר 3), והפתרון למשוואה \( x=6:3 \) הוא מספר אשר מקיים \( 3\cdot x=6 \) (כלומר 2). לא תמיד קיימים פתרונות למשוואות הללו במספרים הטבעיים, למשל למשוואה \( x=2-5 \) אין פתרון במספרים הטבעיים, ולכן אנחנו מכניסים לתמונה מספרים שליליים ושברים; אבל בפוסט הזה לא אדבר עליהם בכלל כי לא יהיה בכך צורך.

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

עכשיו, אם יש לנו מספר טבעי \( a \) ומספר טבעי \( n \) שהוא גדול מאפס, אז אפשר לחלק עם שארית את \( a \) ב-\( n \), כפי שרובנו למדנו בבית הספר היסודי. המשמעות של זה היא שאפשר למצוא מספרים שלמים \( q \) (“מנה”) ו-\( r \) (“שארית”) כך שמתקיים השוויון \( a=nq+r \), ובנוסף לכך \( 0\le r<n \). דרך נוחה להוכיח שאפשר לעשות זאת היא באינדוקציה על הגודל של \( a \): אם \( 0\le a<n \) אז \( a=n\cdot0+a \) הוא השוויון שלנו (כלומר, \( q=0,r=a \) עובד במקרה הזה). אם \( a\ge n \) אז נתבונן על \( a-n \): מהנחת האינדוקציה אנחנו יודעים שקיימים \( q,r \) כך ש-\( a-n=nq+r \) כך ש-\( 0\le r<n \), ולכן (על ידי העברת אגפים) נקבל ש-\( a=n\left(q+1\right)+r \) וזה שוב שוויון כפי שרצינו לקבל.

אם \( a=nq \), כלומר השארית של חלוקת \( a \) ב-\( n \) היא 0, אומרים (באופן מתבקש למדי) ש-\( n \) מחלק את \( a \) והסימון המקובל לכך הוא \( n|a \).

כעת נציג הגדרה חשובה במיוחד: שני מספרים \( a,b \) (טבעים או אפילו שלמים - כלומר, כולל שליליים, שלא תיארתי בפוסט הזה) הם שקולים מודולו \( n \), ואני כותב זאת \( a\equiv_{n}b \), אם השארית שלהם בחלוקה ב-\( n \) היא זהה. כלומר, אם קיים \( 0\le r<n \) וקיימים \( q_{1},q_{2} \) כך ש-\( a=nq_{1}+r \) ו-\( b=nq_{2}+r \) אז \( a\equiv_{n}b \). שימו לב שאם השוויונות הללו מתקיימים אז \( a-b=n\left(q_{1}-q_{2}\right)+\left(r-r\right)=n\left(q_{1}-q_{2}\right) \), כלומר \( n|a-b \), וגם ההפך נכון: אם \( n|a-b \) אז \( a-b=nq \) עבור איזה שהוא \( q \), כלומר \( a=nq+b \). נכתוב \( b=nt+r \) כך ש-\( 0\le r<n \) ונקבל ש-\( a=n\left(q+t\right)+r \), כלומר השארית של חלוקת \( a \) ב-\( n \) שווה לשארית של חלוקת \( b \) ב-\( n \) והיא \( r \). מסקנה: \( a\equiv_{n}b \) אם ורק אם \( n|a-b \). זה תנאי נוח יותר לבדיקה לעתים קרובות ולכן הצגתי אותו. עוד הערה קטנה היא שלרוב בספרות המתמטית כותבים \( a\equiv b\left(\mbox{mod }n\right) \) כדי לציין שקילות מודולו \( n \); אני אישית פחות אוהב את הסימון הזה והוא פחות נוח לי ולכן אני משתמש ב-\( a\equiv_{n}b \) (שגם הוא סימון סטנדרטי אבל הרבה פחות מקובל).

עכשיו, שקילות מודולו \( n \) היא מה שנקרא במתמטיקה יחס שקילות. זה אומר שהיא מקיימת שלוש תכונות: ראשית, \( a\equiv_{n}a \) לכל \( a,n \) טבעיים (כש-\( n>0 \); לא אטרח לציין זאת במפורש כל פעם). זאת מכיוון ש-\( a-a=0 \) וכמובן ש-\( n|0 \). התכונה לפיה כל \( a \) שקול מודולו \( n \) לעצמו נקראת רפלקסיביות.

כמו כן, שקילות מודולו \( n \) היא סימטרית, כלומר אם \( a\equiv_{n}b \) אז זה אומר ש-\( n|a-b \) ולכן \( n=q\left(a-b\right) \) עבור \( q \) כלשהו, ולכן \( n=-q\left(b-a\right) \) ולכן \( b\equiv_{n}a \), כלומר השאלה מי בצד ימין ומי בצד שמאל אינה ממש חשובה כשמדברים על שקילות מודולו \( n \).

לבסוף, שקילות מודולו \( n \) היא טרנזיטיבית, ומשמעות הדבר היא זו: אם \( a\equiv_{n}b \) וגם \( b\equiv_{n}c \) אז זה אומר שקיימים \( q_{1},q_{2} \) כך ש-\( q_{1}n=a-b \) ו-\( q_{2}n=b-c \). נחבר את שתי המשוואות ונקבל ש-\( \left(q_{1}+q_{2}\right)n=\left(a-b\right)+\left(b-c\right)=a-c \) ולכן \( a\equiv_{n}c \).

באופן כללי במתמטיקה, כל יחס שקילות שמוגדר על קבוצה כלשהי - במקרה שלנו, קבוצת המספרים הטבעיים \( \mathbb{N} \), אבל באותה מידה זה יעבוד עבור השלמים \( \mathbb{Z} \) - משרה על הקבוצה חלוקה למחלקות שקילות. מחלקת שקילות של מספר \( a \) כלשהי, שמסומנת בתור \( \left[a\right] \), היא קבוצת כל המספרים ששקולים לו על פי יחס השקילות הזה. זה מושג לא קל להבנה, אז בואו נראה מה הוא עבור המקרים שלנו. נתחיל בקטן - שקילות מודולו \( 2 \). מהי מחלקת השקילות של 0 מודולו 2? היא כוללת את כל המספרים \( a \) כך ש-\( 2|a-0 \), כלומר ש-\( 2|a \), כלומר את כל הזוגיים. מסמנים זאת \( \left[0\right]=\left\{ 0,2,4,6,8,\dots\right\} \). באופן דומה, \( \left[1\right]=\left\{ 1,3,5,7,9,\dots\right\} \), כלומר מחלקת השקילות של 1 כוללת את כל האי זוגיים (כי אי זוגי הוא תמיד מהצורה \( 2k+1 \), ולכן כשנחסר ממנו 1 נקבל משהו שמתחלק ב-2), ואלו כל מחלקות השקילות של היחס “שקילות מודולו 2”.

אפשר לעשות את אותו דבר עבור 3, ונגלה שיש שלוש מחלקות שקילות מודולו 3: \( \left[0\right]=\left\{ 0,3,6,9,12,\dots\right\} \) של כל המספרים שמתחלקים ב-3; \( \left[1\right]=\left\{ 1,4,7,10,13,\dots\right\} \) של כל המספרים שמתחלקים ב-3 עם שארית 1, ו-\( \left[2\right]=\left\{ 2,5,8,11,14,\dots\right\} \) של כל המספרים שמתחלקים ב-3 עם שארית 2. ומה קורה באופן כללי? עבור שקילות מודולו \( n \) יהיו לנו \( n \) מחלקות שקילות, שנוח לתאר בתור \( \left[0\right],\left[1\right],\dots,\left[n-1\right] \) - כאן המספרים \( 0,1,2,\dots,n-1 \) משמשים בתור נציגים של מחלקות השקילות.

ועכשיו נכנסת לתמונה ההגדרה המתמטית המרכזית בפוסט: לכל \( n \) טבעי, אנו מגדירים את הקבוצה \( \mathbb{Z}_{n}=\left\{ \left[0\right],\left[1\right],\dots,\left[n-1\right]\right\} \) של כל מחלקות השקילות מודולו \( n \) של מספרים טבעיים (אם לחדד, לרוב מדברים על מחלקות שקילות של מספרים שלמים, כלומר כולל השליליים, אבל לא היה לי צורך בזה כאן). הקבוצה הזו לכשעצמה היא לא מעניינת; מה שמעניין הוא שאפשר להגדיר עליה פעולות חדשות של חיבור וכפל ש”מושרות” באופן טבעי מהפעולות עבור מספרים רגילים. איך? ובכן, בהינתן \( \left[a\right],\left[b\right] \), איך אפשר להגדיר בצורה הטבעית ביותר את \( \left[a\right]+\left[b\right] \)? בבירור מתבקש להגדיר זאת על ידי \( \left[a\right]+\left[b\right]=\left[a+b\right] \). כלומר, מחלקת השקילות שתוחזר מהחיבור של מחלקות השקילות \( \left[a\right] \) ו-\( \left[b\right] \) תהיה מחלקת השקילות של האיבר \( a+b \). אלא שיש כאן בעיה שצצה באופן כללי כשמגדירים דברים על מחלקות שקילות בעזרת נציגים שלהן: לא מובטח שההגדרה עובדת, כי ייתכן שהיא תלויה בנציג, וצריך להוכיח במפורש שהיא לא.

למה אני מתכוון? ובכן, אני צריך להוכיח שהסיטואציה הבאה אינה אפשרית: שיש לנו \( a,a^{\prime} \) שמייצגים אותה מחלקת שקילות, כלומר \( \left[a\right]=\left[a^{\prime}\right] \), ושיש \( b,b^{\prime} \) כך ש-\( \left[b\right]=\left[b^{\prime}\right] \), אבל שמתקיים \( \left[a+b\right]\ne\left[a^{\prime}+b^{\prime}\right] \). כי אם שתי אלו הן מחלקות שונות, אני אקבל ש-\( \left[a\right]+\left[b\right]=\left[a+b\right]\ne\left[a^{\prime}+b^{\prime}\right]=\left[a^{\prime}\right]+\left[b^{\prime}\right]=\left[a\right]+\left[b\right] \) וקיבלתי סתירה במתמטיקה, שמצביעה על כך שפעולת החיבור של מחלקות שקילות שהגדרתי היא לא חוקית. למרבה המזל, זה לא מה שקורה בפועל; בואו נוכיח את זה.

אני רוצה להראות ש-\( \left[a+b\right]=\left[a^{\prime}+b^{\prime}\right] \), כלומר ש-\( a+b\equiv_{n}a^{\prime}+b^{\prime} \), כלומר ש-\( n|\left(a-a^{\prime}\right)+\left(b-b^{\prime}\right) \). כעת, אני יודע ש-\( a\equiv_{n}a^{\prime} \) ולכן יש \( q_{1} \) כך ש-\( a-a^{\prime}=nq_{1} \). בדומה, \( b\equiv_{n}b^{\prime} \) ולכן \( b-b^{\prime}=nq_{2} \) עבור איזה שהוא \( q_{2} \). מסקנה: \( \left(a-a^{\prime}\right)+\left(b-b^{\prime}\right)=n\left(q_{1}+q_{2}\right) \) ולכן באמת מתקיים \( a+b\equiv_{n}a^{\prime}+b^{\prime} \) ופעולת החיבור מוגדרת היטב. מעולה. ומה עם כפל?

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

הפתרון, למרבה המזל, אינו מסובך, ומשתמש בתעלול אלגברי נפוץ שחלקכם ודאי זוכרים מבית הספר: להוסיף ולהחסיר איבר “ביניים” כלשהו שמקל עלינו לפשט את הביטוי:

\( ab-a^{\prime}b^{\prime}=ab-ab^{\prime}+ab^{\prime}-a^{\prime}b^{\prime}=a\left(b-b^{\prime}\right)+b^{\prime}\left(a-a^{\prime}\right)=n\left(aq_{2}+b^{\prime}q_{1}\right) \)

זה מוכיח שפעולת הכפל של מחלקות שקילות מוגדרת היטב. אם כל זה קצת אבסטרקטי מדי עבורכם, הנה ניסוח “ברמת המשוואה” של מה שראינו: אם \( a\equiv_{n}a^{\prime} \) ו-\( b\equiv_{n}b^{\prime} \), אז

\( a+b\equiv_{n}a^{\prime}+b^{\prime} \)

\( ab\equiv_{n}a^{\prime}b^{\prime} \)

מה שאומר שבכל פעם שיש לנו משוואה פולינומית מודולרית, אפשר לקחת כל מספר שמופיע בה ולהחליף אותו במספר ששקול לו, מה שלעתים קרובות עוזר לפשט את התוצאה. הנה דוגמא: נניח שאנו רוצים לדעת מהו \( 10^{100} \) מודולו 9. אז אנחנו כותבים את המשוואה \( x\equiv_{9}10^{100} \). מה עכשיו? מכיוון ש-\( 10\equiv_{9}1 \), אפשר להמשיך את המשוואה ולכתוב:

\( x\equiv_{9}10^{100}\equiv_{9}1^{100}\equiv_{9}1 \)

קלי קלות, כי אנחנו יודעים ש-1 בחזקת כל דבר הוא 1. גם בחשבון מודולרי.

אם כן, חשבון מודולרי מודולו \( n \) הוא חשבון שמתבצע עם האיברים של \( \mathbb{Z}_{n} \) במקום עם מספרים טבעיים רגילים, או מנקודת מבט קצת אחרת - זה חשבון שמתבצע עם מספרים טבעיים רגילים, אבל כזה שבו אנחנו מחליטים על קבוצת נציגים (שהם מספרים טבעיים) למחלקות השקילות שמהוות את \( \mathbb{Z}_{n} \), עובדים רק עם הנציגים הללו, ובכל פעם שבה אנחנו “חורגים” מהם, אנחנו חוזרים אליהם (על ידי חלוקה ולקיחת שארית). מכיוון שלכתוב \( \left[0\right] \) ו-\( \left[a\right] \) וכדומה כל הזמן זה מסורבל, אנחנו לרוב נוקטים בפועל בשיטה השניה.

עכשיו בואו נדבר על שתי הפעולות שעליהן טרם דיברתי - חיסור וחילוק. מה זה חיסור, באופן כללי? ובכן, נתחיל מחיבור דווקא: יש לנו איבר שהוא “אדיש” לחיבור, במובן זה שאם מחברים אותו עם \( x \) כלשהו, מקבלים \( x \). האיבר הזה הוא 0. עכשיו, לכל מספר טבעי \( a \) קיים מספר נגדי, שאם מחברים אותו עם \( a \) מקבלים את האיבר האדיש לחיבור, כלומר \( 0 \). אנחנו מסמנים את המספר הנגדי הזה ב-\( -a \), ואנחנו יודעים שהוא לא מספר טבעי (אלא מספר שלילי). אלא שבחשבון מודולרי מתרחש “קסם” - אנחנו לא צריכים להרחיב את מערכת המספרים שלנו כדי לקבל איברים נגדיים: הנגדי של \( a \) הוא פשוט \( n-a \). מה שאומר שלפעמים איבר יכול להיות אפילו הנגדי של עצמו. למשל, בחשבון מודולו \( 6 \), הנגדי של 2 הוא 4, והנגדי של 3 הוא 3. זה אומר שאפשר לכתוב משוואות כמו \( 3\equiv_{6}-3 \) והן יהיו תקינות לחלוטין.

איך זה קשור לחיסור? ובכן, כי חיסור אפשר תמיד לראות כפעולה של “חיבור עם נגדי”. בואו ננסה להיזכר מאיפה נוצר הצורך בפעולת חיסור בכלל: נניח שיש לנו משוואה מהצורה \( x+a=b \); הדרך לפתור אותה היא לחסר \( a \) משני האגפים ולקבל \( x=b-a \). הסיבה שאנחנו מחסרים היא שאנחנו רוצים להיפטר מ-\( a \) באגף שמאל; אבל מה שאנחנו בעצם עושים כאן הוא לחבר לאגף שמאל את הנגדי של \( a \), ש”מאפס” אותו. לכן בחשבון מודולרי אפשר לחסר בלי בעיות - פשוט מחברים עם הנגדי. למשל, אם יש לנו את המשוואה \( x+2\equiv_{6}5 \) פשוט מחברים 4 לשני האגפים ומקבלים \( x\equiv_{6}5+4\equiv_{6}9\equiv_{6}3 \). לרוב אנחנו מרשים לעצמנו לכתוב דברים כמו \( -2 \) גם בחשבון מודולרי, מתוך הבנה שזה ייצוג של הנגדי של \( 2 \) (שמודולו 6, למשל, הוא 4). אגב, דרך פשוטה אחרת לחשוב על זה היא ש-\( -2 \) הוא פשוט מחלקת השקילות של \( -2 \) על פי יחס השקילות מודולו (כאשר מגדירים אותו על כל \( \mathbb{Z} \); אבל חלק מהפואנטה שלי בפוסט הזה היא שאפשר לחשוב על חשבון מודולרי גם בלי לדבר על שלילייים).

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

\( 0\cdot a=\left(0+0\right)\cdot a=0\cdot a+0\cdot a \)

ועל ידי העברת אגפים מקבלים \( 0\cdot a=0 \).

הדרך היחידה לפתור את הבעיה הזו בצורה שעדיין מותירה תקווה שיהיה הופכי ל-0 היא לטעון ש-\( 0=1 \), אבל אז לכל \( a \) נקבל \( 0=0\cdot a=1\cdot a=a \), כלומר הכל שווה לאפס ואנחנו בוודאי לא רוצים את זה. אז אין ברירה: אנחנו מצהירים ש-0 אינו הפיך, ולכן גם לא ניתן לחלק ב-0.

הבעיה בחשבון מודולרי היא שזה יכול לקרות לעוד איברים חוץ מ-0.

נתחיל ממקרה פשוט שבו זה דווקא לא קורה, חשבון מודולו 7: מי הוא, למשל, ההופכי של 3 מודולו 7? קל לראות שזה 5, כי \( 3\cdot5\equiv_{7}15\equiv_{7}1 \). אבל האם יש דרך שיטתית ומסודרת למצוא הופכי של מספרים מודולו משהו? התשובה חיובית ואסביר זאת בקרוב.

כעת, אם אני רוצה לחלק ב-3 מודולו 7, אני פשוט כופל ב-5. למשל, כדי לחלק את 6 ב-3 אני כופל ב-5 ומקבל 30, ששקול מודולו 7 ל-2. קסם! בדרך דומה אפשר לחלק בכל מספר מ-1 עד 6, אבל לא ב-0. אם כן, איפה כן יש בעיות עם מספרים ששונים מאפס?

בואו נעבור לדבר על חשבון מודולו 6. בחשבון מודולו 6 לא קשה לראות ש-5 הוא הפיך - תכפלו אותו בעצמו ותקבלו 1. אז כפל ב-5 וחלוקה ב-5 זה בעצם אותו דבר. כנ”ל עבור 1. אבל מה עם שאר המספרים? בואו נתחיל מ-2 ו-3. שימו לב שהמכפלה של שניהם נותנת 6, ששקול מודולו 6 לאפס, כלומר \( 2\cdot3\equiv_{6}0 \). זו תופעה שפשוט לא קיימת בחשבון “רגיל” - כופלים שני מספרים שונים מאפס, ומקבלים אפס. למספרים כאלו קוראים מחלקי אפס, ואני טוען שאם מספר הוא מחלק אפס מודולו \( n \) הוא לא יכול להיות הפיך מודולו \( n \). הסיבה פשוטה: אם \( ab\equiv_{n}0 \) ו-\( b\not\equiv_{n}0 \), ואם \( a \) הפיך, אז אפשר לחלק ב-\( a \) ולקבל \( b\equiv_{n}0 \), בסתירה למה שהנחנו.

במי עוד לא טיפלנו מודולו 6? ב-4. קל לראות שגם הוא מחלק 0, כי \( 4\cdot3=12\equiv_{6}0 \). זה מסיים את הסיפור: האיברים שהם הפיכים מודולו \( 6 \) הם רק \( 1,5 \). באופן כללי, את האיברים ב-\( \mathbb{Z}_{n} \) שהם הפיכים מודולו \( n \) נהוג לסמן בתור \( \mathbb{Z}_{n}^{*} \). כלומר, ראינו ש-\( \mathbb{Z}{}_{7}^{*}=\left\{ 1,2,3,4,5,6\right\} \) ואילו \( \mathbb{Z}_{6}^{*}=\left\{ 1,5\right\} \). אבל האם יש הגיון כללי שמאפשר לדעת מתי איבר הוא הפיך או מחלק אפס מודולו \( n \)? והאם איבר הוא בהכרח או זה או זה? (שימו לב לכך שבמספרים השלמים הטענה “איבר הוא או מחלק אפס או הפיך” אינה נכונה - למשל, 2 אינו הפיך ואינו מחלק אפס). כאן צריך להכניס לתמונה עוד קצת מתמטיקה; בפרט את מה שנקרא האלגוריתם האוקלידי.

בואו נתחיל מלדבר על שאלה שבמבט ראשון אולי נראית לא קשורה. נניח שיש לנו שני מספרים שלמים \( a,b \), ואנחנו מסתכלים על כל המספרים שניתן לקבל מחיבורים וחיסורים שלהם, כלומר על כל הצירופים הלינאריים \( ax+by \) כאשר \( x,y \) הם מספרים שלמים. האם יש דרך פשוטה לתאר את כל המספרים שיכולים להתקבל בצורה הזו?

יש שלל סיבות שבגללן השאלה הזו מעניינת, אבל בהקשר שלנו היא מעניינת כי תשובה לה נותנת לנו תשובה לשאלה “אילו ערכים מודולו \( n \) יש לכפולות של \( a \)?”. מה שנעשה הוא להתבונן על כל המספרים מהצורה \( t=ax+ny \), וכשניקח את המשוואה מודולו \( n \) נקבל \( t\equiv_{n}ax \) (כי \( ny\equiv_{n}0 \)). בפרט, \( a \) הפיך מודולו \( n \) אם ורק אם קיימים \( x,y \) כך ש-\( ax+ny=1 \). אם כן, שווה לחקור בצורה קצת יותר כללית את אוסף כל הצירופים הלינאריים \( ax+by \) ולהבין איך הוא מתנהג עבור \( a,b \) כלשהם.

נתחיל מאבחנה פשוטה: אם \( d \) הוא מספר טבעי כלשהו כך ש-\( d|a \) וגם \( d|b \) אז \( d|ax+by \) (זה תרגיל קל שדומה לחישובים שכבר עשינו בפוסט). לכן אפשר להציג את כל המספרים מהצורה \( ax+ny \) בתור כפולה של כל \( d \) אשר מחלק את \( a,b \). האם זה אומר גם ההפך - שכל כפולה של \( d \) ניתן לייצג כצירוף לינארי שכזה? הבה ונראה דוגמה. ניקח את המספרים \( a=12,b=8 \). שניהם מתחלקים על ידי 2 ולכן ברור שכל צירוף לינארי שלהם יהיה זוגי, אבל האם אפשר לכתוב את 2 כצירוף לינארי שלהם? על פניו לא ברור איך. את 4 קל לכתוב: \( 4=12-8 \). אבל את 2? אפשר לנסות לפעול שיטתית כך: ראשית “נקפיא” את \( 12 \) ונראה אילו מספרים אפשר לקבל כשמחברים ומחסרים את 8 ממנו: נגלה את הסדרה \( \dots,-20,-12,-4,4,12,20,\dots \). נראה ש”פספסנו” את 2. עכשיו, בואו נחבר את 12 לעצמו ונקבל 24. איזו סדרה אפשר לקבל כשמחברים או מחסרים כפולות של 8 מ-24? הסדרה \( \dots,-16,-8,0,8,16,24,32,\dots \). שוב “פספסנו” את 2. אבל אולי אם נתחיל מ-36? הבנתם את הרעיון.

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

הסיבה שבגללה כל כפולה של 4 יכולה להתקבל היא שאפשר לקבל את 4 עצמו בתור צירוף לינארי של 12 ו-8. באופן כללי, אם עבור \( d \) כלשהו מתקיים \( d=ax+by \) אז כדי לקבל כפולה כלשהי של \( d \) פשוט נכפיל את המשוואה במה שאנו זקוקים לו, ונקבל \( td=axt+aty \). מה שהופך את 4 למיוחד הוא שמצד אחד, אפשר לקבל את כל הכפולות שלו כצירוף לינארי של 8 ו-12, ומצד שני הוא מחלק כל צירוף לינארי של 8 ו-12, ולכן קבוצת “הצירופים הלינאריים של 8 ו-12” וקבוצת “הכפולות של 4” הן בדיוק אותה קבוצה. זה גם מבהיר מדוע אנחנו לא מסוגלים לקבל את 2 כצירוף לינארי של 8 ו-12: פשוט מאוד, 4 אינו מחלק את 2.

הטענה הזו עובדת באופן כללי. בהינתן \( a,b \) אנו מסמנים ב-\( d=\mbox{gcd}\left(a,b\right) \) את המחלק המשותף המקסימלי של \( a,b \). כדי להוכיח שכל כפולה של \( d \) מתקבלת כצירוף לינארי של \( a,b \) צריך להוכיח שקיים צירוף לינארי שלהם שנותן את \( d \) עצמו, כלומר שקיימים \( x,y \) כך ש-\( ax+by=d \). אציג כעת אלגוריתם, האלגוריתם האוקלידי שבהינתן \( a,b \) גם מוצא את \( d \) וגם כותב אותו כצירוף לינארי של \( a,b \), ובנוסף לכך הוא גם עושה זאת ביעילות, מה שקריטי לחלוטין עבור תורת המספרים החישובית.

האלגוריתם הוא רקורסיבי באופיו, כלומר מתבסס על קריאה לעצמו על מקרה פשוט יותר. בואו נניח שאנחנו מקבלים כקלט \( a,b \) שהם טבעיים ומקיימים \( a>b \). אז אפשר לחלק את \( a \) ב-\( b \) עם שארית ולקבל \( a=qb+r \). כעת, אם \( r=0 \) זה אומר ש-\( b \) מחלק את \( a \) ולכן המחלק המשותף הגדול ביותר של שניהם הוא \( b \) עצמו, שאפשר להציג בתור צירוף לינארי טריוויאלי: \( a\cdot0+b\cdot1=b \).

כעת, אם \( r \) גדול מ-0, מגיעה האבחנה המרכזית הבאה: \( \mbox{gcd}\left(a,b\right)=\mbox{gcd}\left(b,r\right) \). כדי לראות זאת, מספיק לשים לב לכך ש-\( a=qb+r \) ולכן אם מישהו מחלק את \( b,r \) הוא בוודאי מחלק את \( a \), וש-\( r=a-qb \) ולכן אם מישהו מחלק את \( a,b \) הוא בוודאי מחלק את \( r \). לכן הקבוצה “המחלקים המשותפים של \( a,b \)” והקבוצה “המחלקים המשותפים של \( b,r \)” שוות. הוכחנו את האבחנה, וממנה נובעת שארית האלגוריתם: באופן רקורסיבי, אנו מוצאים \( x^{\prime},y^{\prime} \) כך ש-\( \mbox{gcd}\left(a,b\right)=bx^{\prime}+ry^{\prime} \), וכעת אנו מציבים \( a-qb \) במקום \( r \), ומקבלים \( \mbox{gcd}\left(a,b\right)=ay^{\prime}+b\left(x^{\prime}-qy^{\prime}\right) \), כלומר \( \mbox{gcd}\left(a,b\right)=ax+by \) כאשר \( x=y^{\prime} \) ו-\( y=x^{\prime}-qy^{\prime} \). קל מאוד לתכנת את זה בפועל.

חזרה לענייננו: יהא \( n \) טבעי כלשהו ונרצה לדעת מתי \( a \) הפיך מודולו \( n \). כפי שהראיתי כבר, אם \( \mbox{gcd}\left(a,n\right)=1 \) אז קיימים \( x,y \) כך ש-\( ax+ny=1 \) ולכן \( ax\equiv_{n}1 \) ומכאן ש-\( a \) הפיך ו-\( x \) הוא ההופכי שלו ויש לנו אלגוריתם יעיל למצוא אותו (ולכן אלגוריתם יעיל לביצוע פעולות חילוק מודולו \( n \)). ומה אם \( \mbox{gcd}\left(a,n\right)=d>1 \)? במקרה הזה \( a \) הוא מחלק אפס, כי בואו נסתכל על \( a\cdot\frac{n}{d} \): מכיוון ש-\( d \) מחלק את \( n \), הרי ש-\( \frac{n}{d} \) הוא מספר שלם, וקטן מ-\( n \) (כי \( d>1 \)). מצד שני, הביטוי הזה שווה ל-\( \frac{a}{d}\cdot n\equiv_{n}0 \) כי \( d \) מחלק גם את \( a \). אז מצאנו ש-\( a \) כפול משהו שאיננו 0 מודולו \( n \) שווה ל-0 מודולו \( n \), והמסקנה היא ש-\( a \) אינו הפיך.

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

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