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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

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

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

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

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

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

ראו גם

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

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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