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

הופכי כפל מודולרי (באנגלית: 'Modular multiplicative inverse) הוא מושג במתמטיקה ובפרט בחשבון מודולרי.

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

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

על פי ההגדרה הפורמלית, $a,b$ הם הופכיים כפליים מודולרים מודולו $n$ , אם $ab\equiv 1{\pmod {n}}$ .

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

ל- $a$ יש הופכי מודולו $n$ אם ורק אם $a,n$ זרים. זאת מכיוון שחוג המספרים השלמים הוא תחום ראשי, עבור כל שני מספרים זרים $a,b$ אפשר למצוא מספרים שלמים $x,y$ עבורם $ax+by=1$ . ניתן למצוא הופכי כפלי מודולרי באמצעות אלגוריתם אוקלידס המורחב. ההופכי של איבר בחבורת אוילר הוא ההופכי הכפלי המודולרי שלו.