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

חשבון מודולרי (נקרא גם חשבון קונגרואנציות) מחליף מספרים בשארית החלוקה במספר קבוע n. למשל בחשבון מודולו 7 מתקיים 5+6=11 ושארית חלוקת 11 ב-7 היא 4, לכן אומרים שהתוצאה היא 4. דוגמה נפוצה היא שעון של 24 שעות: אם עכשיו 20:00 ונוסיפים 9 שעות, נקבל 5:00 (20+9 נותן שארית 5 בחלוקה ב-24).

יהי n מספר טבעי. אומרים ש-a ו-b שקולים מודולו n אם ההפרש a-b מתחלק ב-n. שקילות כזו משמעותה שאותם מספרים נותנים את אותה שארית בחלוקה ב-n. בדרך כלל מייצגים כל מחלקת שקילות על ידי אחת מהשאריות 0 עד n-1.

יחס השקילות הוא יחס שקילות אמיתי: הוא רפלקסיבי, סימטרי וטרנזיטיבי. חיבור וכפל מתנהגים טוב עם שקילות: אם a שקול ל-b ו-c שקול ל-d, אז a+c שקול ל-b+d וגם a·c שקול ל-b·d. הקבוצה הזו מסודרת כחוג קומוטטיבי שמסמנים ב-Z_n. החוג הזה הוא תחום שלמות (כלומר אין מחלקי אפס) אם ורק אם n ראשוני, במקרה זה הוא שדה.

איבר a ב-Z_n הוא הפיך אם קיים b כך ש-a·b נותן שארית 1 בחלוקה ב-n. b נקרא ההופכי הכפלי של a. אפשר למצוא הופכי בעזרת אלגוריתם אוקלידס המורחב, שמוצא x,y עם ax+ny=1 ולכן ax נותן שארית 1. לדוגמה, ההופכי של 8 מודולו 19 הוא 12, כי 8·12 = 96 ושארית חלוקת 96 ב-19 היא 1.

חילוק מודולרי מבוצע באמצעות כפל בהופכי. כלומר a/b מודולו n שקול ל-a·b^{-1}, אם ההופכי של b קיים. אם הכפלת בשדה נותנת איבר אפס, לא יהיה להופכי. בכללי, אם ax≡ay מודולו n אז אפשר להסיק ש-x≡y מודולו n/(gcd(a,n)), כאשר gcd(a,n) הוא המחלק המשותף הגדול של a ו-n.

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

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

חשבון מודולרי עובד עם שאריות. שארית היא מה שמתקבל אחרי חילוק. לדוגמה, בחלוקה ב-7, 11 נותן שארית 4, לכן 5+6 בחשבון זה שווה 4.

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

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

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

כדי לחלק צריך שהמחלק יהיה הפיך. אם אין הופכי, אי אפשר לחלק.

אומרים ששני מספרים זרים אם אין להם מחלק משותף חוץ מ-1. פונקציית אוילר, φ(n), סופרת כמה מספרים קטנים מ-n זרים לו. אם a זר ל-n, כוח של a במספר זה נותן שארית 1.

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