הבדלים בין גרסאות בדף "משתמש:איתמר שטיין/הסבר הופכי"
איתמר שטיין (שיחה | תרומות) (←כמה מושגים בתורת המספרים) |
איתמר שטיין (שיחה | תרומות) (←כמה מושגים בתורת המספרים) |
||
שורה 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>a</math>. | לכן <math>n~mod~p</math> הוא הפכי מתאים ל <math>a</math>. | ||
+ | |||
+ | כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>? | ||
+ | == חישוב ההפכי == | ||
+ | |||
+ | עבור שני מספרים <math>a,b \in \mathbb{Z}</math> כך ש <math>gcd(a,b)=1</math> | ||
+ | נתאר שיטה שבעזרתה ניתן למצוא את המספרים <math>n,m</math> כך ש <math>na+mb=1</math>. | ||
+ | |||
+ | |||
+ | נתחיל מהמקרה <math>a,b>0</math> | ||
+ | |||
+ | נניח ש <math>b>a</math>, נסמן <math>r_1=b \quad r_2 = a</math>. | ||
+ | |||
+ | (אם <math>a>b</math> אז נסמן הפוך) | ||
+ | |||
+ | נחפש את המספר <math>q_2\in \mathbb{N}</math> הגדול ביותר כך ש <math>r_1-q_2r_2>0</math>. | ||
+ | |||
+ | ונסמן <math>r_1-q_2r_2 = r_3</math>. | ||
+ | |||
+ | כעת נחפש את המספר הגדול ביותר <math>q_3\in \mathbb{N}</math> כך ש <math>r_2-q_3r_3>0</math> | ||
+ | |||
+ | ונסמן <math>r_2-q_3r_3 = r_4</math>. | ||
+ | |||
+ | נמשיך כך עד שנגיע לשלב <math>k</math> שבו <math>r_k=1</math>. | ||
+ | |||
+ | |||
+ | עד כאן החלק הקל, | ||
+ | עכשיו צריך להתחיל חישוב אחורה | ||
+ | <math>r_{k-2}-q_{k-1}r_{k-1} = r_k = 1</math> | ||
+ | |||
+ | אבל בשלב הקודם קיבלנו ש <math>r_{k-3} - q_{k-2}r_{k-2} = r_{k-1}</math> | ||
+ | |||
+ | לכן אפשר להציב | ||
+ | |||
+ | <math>r_{k-2}-q_{k-1}(r_{k-3} - q_{k-2}r_{k-2}) = 1</math> | ||
+ | |||
+ | שהופך ל: | ||
+ | <math>(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1</math> <math>(\ast)</math> | ||
+ | |||
+ | אבל שוב, בשלב קודם ראינו ש | ||
+ | <math>r_{k-4} - q_{k-3}r_{k-3} =r_{k-2}</math> | ||
+ | ואפשר להציב את התוצאה ב | ||
+ | <math>r_{k-2}</math> | ||
+ | שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה | ||
+ | |||
+ | <math>xr_{k-4}+yr_{k-3}=1</math> | ||
+ | |||
+ | וכן הלאה עד שנגיע לביטוי מהצורה | ||
+ | <math>mr_1+nr_2=1</math> | ||
+ | |||
+ | שזה בדיוק | ||
+ | <math>mb+na=1</math>. | ||
+ | |||
+ | |||
+ | אם <math>a,b<0</math> אז מוצאים <math>n,m</math> מתאימים עבור <math>|a|,|b|</math> | ||
+ | |||
+ | ואז <math>(-n)a+(-m)b=n|a|+m|b|=1</math> אז פשוט לוקחים את <math>-n,-m</math>. | ||
+ | |||
+ | |||
+ | == דוגמא == | ||
+ | |||
+ | מצא את ההפכי של ב <math>\mathbb{Z}_{101}</math>. |
גרסה מ־11:30, 11 ביולי 2012
כאשר אנו מבצעים חישובים בשדה (נזכור ש חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י ניחוש, אם אז יש איברים שיכולים להיות הופכי:
(למעשה יש פחות, כי לעולם לא יהיה הופכי ו הופכי רק ב)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב ? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו אומרים ש מחלק את (ומסמנים ) אם קיים כך ש .
הגדרה: יהיו המחלק המשותף המירבי של (מסומן ) הוא המספר הגדול ביותר שמחלק גם את וגם את .
כלומר
ההגדרה הזאת בעייתית כאשר במצב זה אומרים ש .
נשים לב שאם מספר ראשוני ו אז
משפט: יהיו ו אזי קיימים כך ש .
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב , כי אם אז
לכן קיימים כך ש .
אם נפעיל על שני צידי המשוואה הזאת נקבל שהופך ל לכן הוא הפכי מתאים ל .
כל זה טוב ויפה, אבל איך מוצאים את ?
חישוב ההפכי
עבור שני מספרים כך ש נתאר שיטה שבעזרתה ניתן למצוא את המספרים כך ש .
נתחיל מהמקרה
נניח ש , נסמן .
(אם אז נסמן הפוך)
נחפש את המספר הגדול ביותר כך ש .
ונסמן .
כעת נחפש את המספר הגדול ביותר כך ש
ונסמן .
נמשיך כך עד שנגיע לשלב שבו .
עד כאן החלק הקל,
עכשיו צריך להתחיל חישוב אחורה
אבל בשלב הקודם קיבלנו ש
לכן אפשר להציב
שהופך ל:
אבל שוב, בשלב קודם ראינו ש ואפשר להציב את התוצאה ב שמופיע בביטוי ולקבל ביטוי מהצורה
וכן הלאה עד שנגיע לביטוי מהצורה
שזה בדיוק .
אם אז מוצאים מתאימים עבור
ואז אז פשוט לוקחים את .
דוגמא
מצא את ההפכי של ב .