הבדלים בין גרסאות בדף "משתמש:איתמר שטיין/הסבר הופכי"
איתמר שטיין (שיחה | תרומות) (←חישוב ההופכי) |
איתמר שטיין (שיחה | תרומות) (←כמה מושגים בתורת המספרים) |
||
(2 גרסאות ביניים של אותו משתמש אינן מוצגות) | |||
שורה 35: | שורה 35: | ||
<math>(na+mp)mod~p = 1mod~p</math> | <math>(na+mp)mod~p = 1mod~p</math> | ||
שהופך ל <math>(na)mod~p = 1</math> | שהופך ל <math>(na)mod~p = 1</math> | ||
− | לכן <math>n~mod~p</math> הוא | + | לכן <math>n~mod~p</math> הוא הופכי מתאים ל <math>a</math>. |
כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>? | כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>? | ||
שורה 80: | שורה 80: | ||
שהופך ל: | שהופך ל: | ||
<math>(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1</math> <math>(\ast)</math> | <math>(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1</math> <math>(\ast)</math> | ||
+ | |||
אבל שוב, בשלב קודם ראינו ש | אבל שוב, בשלב קודם ראינו ש | ||
שורה 85: | שורה 86: | ||
ואפשר להציב את <math>r_{k-4} - q_{k-3}r_{k-3}</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> ולקבל ביטוי מהצורה | ||
שורה 98: | שורה 98: | ||
− | * אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>|a|,|b|</math> | + | * אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>|a|,|b|</math> בשיטה שתוארה קודם |
ואז <math>n'|a|+m'|b|=1</math> ואז | ואז <math>n'|a|+m'|b|=1</math> ואז |
גרסה אחרונה מ־18:02, 12 ביולי 2012
כאשר אנו מבצעים חישובים בשדה (נזכור ש חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י מעבר על כל האפשרויות, אם אז יש איברים שיכולים להיות הופכי:
(למעשה יש פחות, כי לעולם לא יהיה הופכי ו הופכי רק ב)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב ? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו אומרים ש מחלק את (ומסמנים ) אם קיים כך ש .
הגדרה: יהיו המחלק המשותף המירבי של (מסומן ) הוא המספר הגדול ביותר שמחלק גם את וגם את .
כלומר
ההגדרה הזאת בעייתית כאשר במצב זה אומרים ש .
נשים לב שאם מספר ראשוני ו אז
משפט: יהיו ו אזי קיימים כך ש .
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב , כי אם אז
לכן קיימים כך ש .
אם נפעיל על שני צידי המשוואה הזאת נקבל שהופך ל לכן הוא הופכי מתאים ל .
כל זה טוב ויפה, אבל איך מוצאים את ?
חישוב ההופכי
עבור שני מספרים כך ש נתאר שיטה שבעזרתה ניתן למצוא את המספרים כך ש .
- נתחיל מהמקרה
נניח ש , נסמן .
(אם אז נסמן הפוך)
נחפש את המספר הגדול ביותר כך ש .
ונסמן .
כעת נחפש את המספר הגדול ביותר כך ש
ונסמן .
נמשיך כך עד שנגיע לשלב שבו .
(היות ו מובטח לנו שנגיע מתישהוא ל )
עד כאן החלק הקל,
עכשיו צריך להתחיל חישוב אחורה
השלב האחרון שהגענו אליו היה
אבל בשלב הקודם קיבלנו ש
לכן אפשר להציב
שהופך ל:
אבל שוב, בשלב קודם ראינו ש
ואפשר להציב את ב שמופיע בביטוי ולקבל ביטוי מהצורה
עבור כלשהם
וכן הלאה עד שנגיע לביטוי מהצורה
שזה בדיוק .
- אם או אז מוצאים מתאימים עבור בשיטה שתוארה קודם
ואז ואז
אם לוקחים (אחרת )
אם לוקחים (אחרת )
- אם הסיכוי היחיד ש זה אם או וזה מקרה פשוט
כנ"ל אם
דוגמא
מצא את ההופכי של ב .
נחשב
עכשיו נחשב אחורה
.
לכן ההופכי של 27 ב הוא 15.