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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

הגדרה פורמלית[עריכת קוד מקור | עריכה]

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

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

חילוק[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – חילוק מודולרי

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

חבורות מודולריות[עריכת קוד מקור | עריכה]

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

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