הבדלים בין גרסאות בדף "משתמש:איתמר שטיין/הסבר הופכי"
איתמר שטיין (שיחה | תרומות) |
איתמר שטיין (שיחה | תרומות) (←כמה מושגים בתורת המספרים) |
||
| שורה 13: | שורה 13: | ||
== כמה מושגים בתורת המספרים == | == כמה מושגים בתורת המספרים == | ||
| − | הגדרה: יהיו <math>a,b\in \mathbb{Z}</math> אומרים ש <math>a</math> מחלק את <math>b</math> (ומסמנים <math>a|b</math>) | + | '''הגדרה''': יהיו <math>a,b\in \mathbb{Z}</math> אומרים ש <math>a</math> מחלק את <math>b</math> (ומסמנים <math>a|b</math>) |
אם קיים <math>c\in \mathbb{Z}</math> כך ש <math>ac=b</math>. | אם קיים <math>c\in \mathbb{Z}</math> כך ש <math>ac=b</math>. | ||
| − | הגדרה: יהיו <math>a,b\in \mathbb{Z}</math> המחלק המשותף המירבי של <math>a,b</math> (מסומן <math>gcd(a,b)</math>) הוא המספר הגדול ביותר שמחלק גם את <math>a</math> וגם את <math>b</math>. | + | '''הגדרה''': יהיו <math>a,b\in \mathbb{Z}</math> המחלק המשותף המירבי של <math>a,b</math> (מסומן <math>gcd(a,b)</math>) הוא המספר הגדול ביותר שמחלק גם את <math>a</math> וגם את <math>b</math>. |
כלומר <math>gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\}</math> | כלומר <math>gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\}</math> | ||
ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>. | ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>. | ||
| + | |||
| + | נשים לב שאם <math>p</math> מספר ראשוני ו <math>1\geq a\geq p-1</math> אז <math>gcd(a,p)=1</math> | ||
| + | |||
| + | |||
| + | '''משפט''': יהיו <math>a,b\in \mathbb{Z}</math> ו <math>g=gcd(a,b)</math> אזי קיימים <math>m,n\in\mathbb{Z}</math> כך ש <math>na+mb=g</math>. | ||
| + | |||
| + | |||
| + | הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב <math>\mathbb{Z}_p</math>, כי אם <math>0\neq a\in\mathbb{Z}_p</math> אז | ||
| + | <math>gcd(a,p)=1</math> לכן קיימים <math>m,n</math> כך ש <math>na+mp=1</math>. | ||
| + | |||
| + | אם נפעיל <math>mod~p</math> על שני צידי המשוואה הזאת נקבל | ||
| + | <math>(na+mp)mod~p = 1mod~p</math> | ||
| + | שהופך ל <math>(na)mod~p = 1</math> | ||
| + | |||
| + | לכן <math>n~mod~p</math> הוא הפכי מתאים ל <math>a</math>. | ||
גרסה מ־10:59, 11 ביולי 2012
כאשר אנו מבצעים חישובים בשדה 
(נזכור ש 
חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י ניחוש,
אם 
אז יש איברים שיכולים להיות הופכי: 
(למעשה יש פחות, כי 
לעולם לא יהיה הופכי ו 
הופכי רק ב
)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב 
? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו 
אומרים ש 
מחלק את 
(ומסמנים 
)
אם קיים 
כך ש 
.
הגדרה: יהיו המחלק המשותף המירבי של 
(מסומן 
) הוא המספר הגדול ביותר שמחלק גם את וגם את .
כלומר 
ההגדרה הזאת בעייתית כאשר 
במצב זה אומרים ש 
.
נשים לב שאם מספר ראשוני ו 
אז 
משפט: יהיו ו 
אזי קיימים 
כך ש 
.
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב , כי אם 
אז
לכן קיימים 
כך ש 
.
אם נפעיל 
על שני צידי המשוואה הזאת נקבל
שהופך ל 
לכן 
הוא הפכי מתאים ל .
