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

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

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

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

על פי ההגדרה הפורמלית, 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 (באנגלית)

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