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

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

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

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

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

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