הבדלים בין גרסאות בדף "משתמש:איתמר שטיין/הסבר הופכי"
איתמר שטיין (שיחה | תרומות) (←חישוב ההופכי) |
איתמר שטיין (שיחה | תרומות) (←חישוב ההופכי) |
||
שורה 83: | שורה 83: | ||
אבל שוב, בשלב קודם ראינו ש | אבל שוב, בשלב קודם ראינו ש | ||
<math>r_{k-4} - q_{k-3}r_{k-3} =r_{k-2}</math> | <math>r_{k-4} - q_{k-3}r_{k-3} =r_{k-2}</math> | ||
− | ואפשר להציב את | + | |
− | <math>r_{k-2}</math> | + | ואפשר להציב את <math>r_{k-4} - q_{k-3}r_{k-3}</math> ב <math>r_{k-2}</math> |
+ | |||
שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה | שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה | ||
<math>xr_{k-4}+yr_{k-3}=1</math> | <math>xr_{k-4}+yr_{k-3}=1</math> | ||
+ | עבור <math>x,y</math> כלשהם | ||
וכן הלאה עד שנגיע לביטוי מהצורה | וכן הלאה עד שנגיע לביטוי מהצורה |
גרסה מ־17:58, 12 ביולי 2012
כאשר אנו מבצעים חישובים בשדה (נזכור ש
חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י מעבר על כל האפשרויות,
אם אז יש
איברים שיכולים להיות הופכי:
(למעשה יש פחות, כי לעולם לא יהיה הופכי ו
הופכי רק ב
)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב ? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו אומרים ש
מחלק את
(ומסמנים
)
אם קיים
כך ש
.
הגדרה: יהיו המחלק המשותף המירבי של
(מסומן
) הוא המספר הגדול ביותר שמחלק גם את
וגם את
.
כלומר
ההגדרה הזאת בעייתית כאשר במצב זה אומרים ש
.
נשים לב שאם מספר ראשוני ו
אז
משפט: יהיו ו
אזי קיימים
כך ש
.
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב , כי אם
אז
לכן קיימים
כך ש
.
אם נפעיל על שני צידי המשוואה הזאת נקבל
שהופך ל
לכן
הוא הפכי מתאים ל
.
כל זה טוב ויפה, אבל איך מוצאים את ?
חישוב ההופכי
עבור שני מספרים כך ש
נתאר שיטה שבעזרתה ניתן למצוא את המספרים
כך ש
.
- נתחיל מהמקרה
נניח ש , נסמן
.
(אם אז נסמן הפוך)
נחפש את המספר הגדול ביותר כך ש
.
ונסמן .
כעת נחפש את המספר הגדול ביותר כך ש
ונסמן .
נמשיך כך עד שנגיע לשלב שבו
.
(היות ו מובטח לנו שנגיע מתישהוא ל
)
עד כאן החלק הקל,
עכשיו צריך להתחיל חישוב אחורה
השלב האחרון שהגענו אליו היה
אבל בשלב הקודם קיבלנו ש
לכן אפשר להציב
שהופך ל:
אבל שוב, בשלב קודם ראינו ש
ואפשר להציב את ב
שמופיע בביטוי ולקבל ביטוי מהצורה
עבור
כלשהם
וכן הלאה עד שנגיע לביטוי מהצורה
שזה בדיוק
.
- אם
או
אז מוצאים
מתאימים עבור
ואז ואז
אם לוקחים
(אחרת
)
אם לוקחים
(אחרת
)
- אם
הסיכוי היחיד ש
זה אם
או
וזה מקרה פשוט
כנ"ל אם
דוגמא
מצא את ההופכי של ב
.
נחשב
עכשיו נחשב אחורה
.
לכן ההופכי של 27 ב הוא 15.