משתמש:איתמר שטיין/הסבר הופכי: הבדלים בין גרסאות בדף
איתמר שטיין (שיחה | תרומות) אין תקציר עריכה |
איתמר שטיין (שיחה | תרומות) |
||
| שורה 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
כאשר אנו מבצעים חישובים בשדה [math]\displaystyle{ \mathbb{Z}_p }[/math] (נזכור ש [math]\displaystyle{ p }[/math] חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י ניחוש, אם [math]\displaystyle{ a\in \mathbb{Z}_p }[/math] אז יש [math]\displaystyle{ p }[/math] איברים שיכולים להיות הופכי: [math]\displaystyle{ \{0,1,\ldots,p-1\} }[/math]
(למעשה יש פחות, כי [math]\displaystyle{ 0 }[/math] לעולם לא יהיה הופכי ו [math]\displaystyle{ 1 }[/math] הופכי רק ב[math]\displaystyle{ \mathbb{Z}_2 }[/math])
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב [math]\displaystyle{ \mathbb{Z}_{101} }[/math]? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב [math]\displaystyle{ \mathbb{Z}_p }[/math] נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו [math]\displaystyle{ a,b\in \mathbb{Z} }[/math] אומרים ש [math]\displaystyle{ a }[/math] מחלק את [math]\displaystyle{ b }[/math] (ומסמנים [math]\displaystyle{ a|b }[/math]) אם קיים [math]\displaystyle{ c\in \mathbb{Z} }[/math] כך ש [math]\displaystyle{ ac=b }[/math].
הגדרה: יהיו [math]\displaystyle{ a,b\in \mathbb{Z} }[/math] המחלק המשותף המירבי של [math]\displaystyle{ a,b }[/math] (מסומן [math]\displaystyle{ gcd(a,b) }[/math]) הוא המספר הגדול ביותר שמחלק גם את [math]\displaystyle{ a }[/math] וגם את [math]\displaystyle{ b }[/math].
כלומר [math]\displaystyle{ gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\} }[/math]
ההגדרה הזאת בעייתית כאשר [math]\displaystyle{ a=b=0 }[/math] במצב זה אומרים ש [math]\displaystyle{ gcd(0,0)=0 }[/math].
נשים לב שאם [math]\displaystyle{ p }[/math] מספר ראשוני ו [math]\displaystyle{ 1\geq a\geq p-1 }[/math] אז [math]\displaystyle{ gcd(a,p)=1 }[/math]
משפט: יהיו [math]\displaystyle{ a,b\in \mathbb{Z} }[/math] ו [math]\displaystyle{ g=gcd(a,b) }[/math] אזי קיימים [math]\displaystyle{ m,n\in\mathbb{Z} }[/math] כך ש [math]\displaystyle{ na+mb=g }[/math].
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב [math]\displaystyle{ \mathbb{Z}_p }[/math], כי אם [math]\displaystyle{ 0\neq a\in\mathbb{Z}_p }[/math] אז
[math]\displaystyle{ gcd(a,p)=1 }[/math] לכן קיימים [math]\displaystyle{ m,n }[/math] כך ש [math]\displaystyle{ na+mp=1 }[/math].
אם נפעיל [math]\displaystyle{ mod~p }[/math] על שני צידי המשוואה הזאת נקבל [math]\displaystyle{ (na+mp)mod~p = 1mod~p }[/math] שהופך ל [math]\displaystyle{ (na)mod~p = 1 }[/math]
לכן [math]\displaystyle{ n~mod~p }[/math] הוא הפכי מתאים ל [math]\displaystyle{ a }[/math].