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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

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

[עריכה] תכונות משוואות מודולריות

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

חיבור (או חיסור) של ערכים שווים.
כפל של ערכים שווים.
העלאה בחזקה במעריך זהה.
חילוק בערך זהה (אולם המשוואה החדשה שתתקבל תהיה המחלק המשותף המקסימלי של הערך ובסיס המודול).

על אף ההגבלות, לעתים משוואות מודולריות גמישות יותר ממשוואות רגילות. לדוגמה, נניח כי נתונה המשוואה:

$\!\, 5x\equiv4\pmod{7}$ (במשוואה זו בסיס המודול הוא 7).

כיצד נפתור את המשוואה (בהנחה ש-x מספר שלם)? בחשבון מודולרי, משוואה זו זהה למשוואה:

$\!\, -2x\equiv4\pmod{7}$

כעת ניתן לחלק את שני צידי המשוואה:

$\!\, x\equiv(-2)\pmod{7}$

$\!\, x = 5$

וזהו הפתרון.

ישנן מספר בעיות מתמטיות ייחודיות לחשבון המודולרי. אחת מהן היא חיפוש הופכי כפלי מודולרי.

[עריכה] דוגמאות

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

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

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

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