משתמש:איתמר שטיין/הסבר הופכי
כאשר אנו מבצעים חישובים בשדה (נזכור ש חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י מעבר על כל האפשרויות, אם אז יש איברים שיכולים להיות הופכי:
(למעשה יש פחות, כי לעולם לא יהיה הופכי ו הופכי רק ב)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב ? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו אומרים ש מחלק את (ומסמנים ) אם קיים כך ש .
הגדרה: יהיו המחלק המשותף המירבי של (מסומן ) הוא המספר הגדול ביותר שמחלק גם את וגם את .
כלומר
ההגדרה הזאת בעייתית כאשר במצב זה אומרים ש .
נשים לב שאם מספר ראשוני ו אז
משפט: יהיו ו אזי קיימים כך ש .
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב , כי אם אז
לכן קיימים כך ש .
אם נפעיל על שני צידי המשוואה הזאת נקבל שהופך ל לכן הוא הפכי מתאים ל .
כל זה טוב ויפה, אבל איך מוצאים את ?
חישוב ההופכי
עבור שני מספרים כך ש נתאר שיטה שבעזרתה ניתן למצוא את המספרים כך ש .
נתחיל מהמקרה
נניח ש , נסמן .
(אם אז נסמן הפוך)
נחפש את המספר הגדול ביותר כך ש .
ונסמן .
כעת נחפש את המספר הגדול ביותר כך ש
ונסמן .
נמשיך כך עד שנגיע לשלב שבו .
עד כאן החלק הקל,
עכשיו צריך להתחיל חישוב אחורה
אבל בשלב הקודם קיבלנו ש
לכן אפשר להציב
שהופך ל:
אבל שוב, בשלב קודם ראינו ש ואפשר להציב את התוצאה ב שמופיע בביטוי ולקבל ביטוי מהצורה
וכן הלאה עד שנגיע לביטוי מהצורה
שזה בדיוק .
אם אז מוצאים מתאימים עבור
ואז אז פשוט לוקחים את .
דוגמא
מצא את ההופכי של ב .
נחשב
עכשיו נחשב אחורה
.
לכן ההופכי של 27 ב הוא 15.