משתמש:איתמר שטיין/הסבר הופכי

כאשר אנו מבצעים חישובים בשדה [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].