הופכי כפלי מודולרי

הופכי כפל מודולרי הוא מושג במתמטיקה ובפרט בחשבון מודולרי.

באופן כללי, הופכי של מספר $a$ בפעולה * הוא מספר $b$ כך שמתקיים a*b=e כאשר לכל מספר a מתקיים a*e = a למשל, עבור מספרים רציונליים ההופכי של $a$ בכפל הוא הוא $\frac{1}{a}$ , ובחיבור a-.

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

על פי ההגדרה הפורמלית, a,b הם הופכיים כפליים מודולריים מודולו n, אם $a b \equiv 1 (mod n)$ . לדוגמה, מודולו 9, ההופכי הכפלי של 2 הוא 5, מכיוון ש: $2 \cdot 5 = 1 (mod 9)$ . על כן ניתן להגיד ש: $3 : 2 = 3 \cdot 5 (mod 9)$ . אפשר לבדוק ולהיווכח שאכן 5 הוא ההופכי של 2 בדוגמה זו, כלומר אחרי שנבצע פעולה והיפוכה נקבל בחזרה 3. מתקיים: $(3 : 2) \cdot 2 (mod 9) \equiv (3 \cdot 5) \cdot 2 (mod 9) = 3$

ל-a יש הופכי מודולו n אם ורק אם a ו-n זרים. זאת מכיוון שחוג המספרים השלמים הוא תחום ראשי, עבור כל שני מספרים זרים a ו-n אפשר למצוא מספרים שלמים u ו-v כך ש- $u a + v n = 1$ (משפט Bézout). ניתן למצוא הופכי כפלי מודולרי באמצעות גרסה מורחבת של האלגוריתם האוקלידי. ההופכי של איבר בחבורת אוילר הוא ההופכי הכפלי המודולרי שלו.