חשבון מודולרי

חישובי שעות בשעון זה הם מודולו 12

חשבון מוֹדוּלַרי (באנגלית: Modular arithmetic, ידוע גם כחשבון קונגרואנציות) הוא שיטה מתמטית, בה מחליפים מספרים בשארית החלוקה במספר קבוע.

למשל, בחשבון מודולו 7 מתקיים השוויון $5+6=4$, מכיוון ש־$5+6=11$ ושארית החילוק של 11 ב־7 היא 4.

הדוגמה הידועה ביותר לחשבון מודולרי היא החשבון על־פני השעון, שהוא חשבון מודולרי מודולו 24. כאשר השעה כעת היא 20:00, ואנו רוצים לדעת מה תהיה השעה 9 שעות מאוחר יותר, הפעולה שאנו עושים היא $20+9\equiv 5{\pmod {24}}$.

הגדרה פורמלית

יהי $n$ מספר טבעי. המספרים $a,b$ שקולים מודולו $n$ אם הם נותנים אותה שארית בחלוקה ב־$n$, וזה אם ורק אם $n$ גם מחלק את ההפרש $a-b$.

${\begin{aligned}a=pn+r,\ b=qn+r\quad :0\leq r\leq n-1\\a-b=(pn+r)-(qn+r)=n(p-q)\end{aligned}}$

במקרה זה מסמנים $a\equiv b{\pmod {n}}$ (אומרים גם כי $a,b$ קונגרואנטיים מודולו $n$).

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

תכונות השקילות המודולרית

יחס השקילות המודולרית הוא אכן יחס שקילות, כלומר הוא

• רפלקסיבי: $a\equiv a{\pmod {n}}$
• סימטרי: אם $a$ שקול ל־$b$ אז $b$ שקול ל־$a$.
• טרנזיטיבי: אם $a$ שקול ל־$b$ ו־$b$ שקול ל־$c$ אזי $a$ שקול ל־$c$.

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

${\begin{aligned}a_{1}\equiv b_{1}{\pmod {n}}\\a_{2}\equiv b_{2}{\pmod {n}}\end{aligned}}\ \implies \ {\begin{aligned}a_{1}\pm a_{2}&\equiv b_{2}\pm a_{1}{\pmod {n}}\\a_{1}a_{2}&\equiv b_{1}b_{2}{\pmod {n}}\end{aligned}}$

לכן קבוצת המספרים השלמים מודולו $n$ מהווה חוג קומוטטיבי, עם הכפל והחיבור הטבעיים, שאותו מסמנים $\mathbb {Z} _{n}$ או $\mathbb {Z} /n\mathbb {Z}$ (הסימון האחרון רומז לכך שזהו חוג מנה של חוג המספרים השלמים ביחס לאידאל של המספרים המתחלקים ב־$n$). החוג הזה הוא תחום שלמות אם ורק אם $n$ מספר ראשוני (ואז הוא שדה).

הופכי ביחס לכפל

איבר $a\in \mathbb {Z} _{n}$ הוא הפיך אם קיים $b\in \mathbb {Z} _{n}$ עבורו $ab\equiv 1{\pmod {n}}$. במקרה זה $b$ הוא ההופכי כפלי של $a$. את ההופכי שלו מסמנים כנהוג $a^{-1}$.

מציאת הופכי כפלי מודולרי, כלומר פתרון המשוואה $ax\equiv 1{\pmod {n}}$, נעשית באמצעות אלגוריתם אוקלידס המורחב, המספק ערכים $x,y$ המקיימים $ax+ny=1$, משום שאז $ax\equiv 1{\pmod {n}}$. למשל: ההופכי הכפלי של $a\equiv 8{\pmod {19}}$ הוא $12$ כיוון ש־$19\cdot 3+8\cdot (-7)=1$ לכן $a^{-1}=-7=19-7=12$.

חילוק מודולרי

כפל של $a$ בהופכי כפלי של שלם $b$ כלשהוא שקול לחילוק ב־$b$, כלומר $ab^{-1}\equiv {\frac {a}{b}}{\pmod {n}}$.

מכיוון שלא כל מספר הפיך מודולו $n$, לא תמיד אפשר לחלק שוויונות מודולריים. למעשה, אם $ax\equiv ay{\pmod {n}}$, אז מובטח רק כי $x\equiv y{\pmod {\frac {n}{\gcd(a,n)}}}$.

משפט אוילר

שני מספרים שלמים נקראים זרים או "ראשוניים הדדית", אם המחלק המשותף המרבי שלהם הוא 1.

פונקציית אוילר המסומנת $\varphi (n)$ מייצגת את מספר השלמים בטווח $[1,n-1]$ הזרים ל־$n$ או הראשוניים ביחס ל־$n$, כלומר שהמחלק המשותף המרבי שלהם עם $n$ הוא 1.

אם $n$ ראשוני אזי כל המספרים עד $n-1$ זרים ל־$n$, כיוון שמספר ראשוני אינו מתחלק באף אחד מהמספרים הנמוכים ממנו מעצם ההגדרה. משפט אוילר קובע כי עבור כל שלם $a$ הזר ל־$n$ מתקיים $a^{\varphi (n)}\equiv 1{\pmod {n}}$. כאשר $p$ מספר ראשוני מתקבל כמקרה פרטי המשפט הקטן של פרמה: $a^{p-1}\equiv 1{\pmod {p}}$ לכל $a$ שלא מתחלק ב־$p$.

חבורות מודולריות

פעולת החיבור בחשבון מודולרי היא, בדומה לחיבור הרגיל, קומוטטיבית ואסוציאטיבית, וכן יש בה איבר יחידה (0), ולכל מספר יש אבר נגדי. לפיכך חיבור בחשבון מודולרי יוצר חבורה קומוטטיבית שהיא החבורה הציקלית מסדר $n$.

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

למשל: $4\cdot 3\equiv 0{\pmod {6}}$. שני המספרים $3,4$, בהקשר הנוכחי של הדיון, נקראים מחלקי אפס מכיוון שמכפלתם היא אפס. לאבר שהוא מחלק אפס לא יכול להיות הפכי כפלי.

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

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

• גדי אלכסנדרוביץ', אז מה זה בעצם חשבון מודולרי?, באתר "לא מדויק"
• חשבון מודולרי, באתר MathWorld (באנגלית)   

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