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

חשבון מוֹדוּלַרי (הידוע גם כחשבון קונגרואנציות) הוא שיטה מתמטית, בה מחליפים מספרים בשארית החלוקה במספר קבוע. לדוגמה, בחשבון מודולו 7 מתקיים השוויון $\,5+6=4\,$, מכיוון ש: $5+6=11$, ושארית החילוק של 11 ב-7 היא 4.

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

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

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

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

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

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

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

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

בנוסף לזה, פעולות החיבור והכפל בין מחלקות השקילות מוגדרות היטב: אם $\ a\equiv b{\pmod {n}}$ וכן $\ c\equiv d{\pmod {n}}$, אז$\ a+c\equiv b+d{\pmod {n}}$ וכן $\ ac\equiv bd{\pmod {n}}$. לכן קבוצת המספרים השלמים מודולו $\ 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\ ({\mbox{mod }}n)$, נעשית באמצעות אלגוריתם אוקלידס המורחב, המספק ערכים x,y המקיימים $\ ax+ny=1$, משום שאז $\ ax\equiv 1{\pmod {n}}$. לדוגמה: ההופכי כפלי של $\ a=8\ ({\mbox{mod }}19)$ הוא $\ 12$ כיוון ש-$\ 19\cdot 3+8\cdot -7=1$ לכן $\ a^{-1}=-7=19-7=12$.

חילוק

ערך מורחב – חילוק מודולרי

כפל של $\ a$, בהופכי כפלי של שלם $\ b$ כלשהו שקול לחילוק ב-$\ b$, כלומר $\ ab^{-1}$ שקול ל-$\ a/b$ (מודולו $\ n$).

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

משפט אוילר

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

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

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

גם פעולת הכפל בחשבון מודולרי היא קומוטטיבית ואסוציאטיבית, ואיבר היחידה בה הוא 1, אך לא לכל איבר יש איבר הופכי (כלומר, כזה שמכפלתם של שני האיברים תהיה איבר היחידה 1). לכן אוסף השאריות מודולו n הוא מונואיד ולא חבורה. במונואיד הזה יש מחלקי אפס, כגון $\!\,4\cdot 3\equiv 0{\pmod {6}}$. לאבר שהוא מחלק אפס לא יכול להיות הפכי כפלי; ובמונואיד של השאריות מודולו n זו המניעה היחידה לקיומו של הפכי. מספר הוא הפיך מודולו n אם הוא זר ל-n, ומחלק אפס אחרת. אוסף השאריות השונות מאפס הוא חבורה אם ורק אם n ראשוני. באופן כללי יותר, אוסף השאריות ההפיכות נקרא חבורת אוילר של n.

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

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