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

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

באופן כללי, הופכי של מספר $\ 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). ניתן למצוא הופכי כפלי מודולרי באמצעות גרסה מורחבת של האלגוריתם האוקלידי. ההופכי של איבר בחבורת אוילר הוא ההופכי הכפלי המודולרי שלו.

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

ראו גם

• חילוק מודולרי

קישורים חיצוניים

• הופכי כפלי מודולרי, באתר MathWorld (באנגלית)

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.