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

כאשר אנו מבצעים חישובים בשדה $\mathbb{Z}_p$ (נזכור ש $p$ חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.

שיטה אחת לבצע זאת היא ע"י ניחוש, אם $a\in \mathbb{Z}_p$ אז יש $p$ איברים שיכולים להיות הופכי: $\{0,1,\ldots,p-1\}$

(למעשה יש פחות, כי $0$ לעולם לא יהיה הופכי ו $1$ הופכי רק ב$\mathbb{Z}_2$)

אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.

שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב $\mathbb{Z}_{101}$? בשיטה הזאת נצטרך לנסות 99 אפשרויות.

כדי להסביר איך מוצאים הופכי ב $\mathbb{Z}_p$ נצטרך להביא כמה הקדמות מתורת המספרים.

כמה מושגים בתורת המספרים

הגדרה: יהיו $a,b\in \mathbb{Z}$ אומרים ש $a$ מחלק את $b$ (ומסמנים $a|b$) אם קיים $c\in \mathbb{Z}$ כך ש $ac=b$.

הגדרה: יהיו $a,b\in \mathbb{Z}$ המחלק המשותף המירבי של $a,b$ (מסומן $gcd(a,b)$) הוא המספר הגדול ביותר שמחלק גם את $a$ וגם את $b$.

כלומר $gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\}$

ההגדרה הזאת בעייתית כאשר $a=b=0$ במצב זה אומרים ש $gcd(0,0)=0$.

נשים לב שאם $p$ מספר ראשוני ו $1\geq a\geq p-1$ אז $gcd(a,p)=1$

משפט: יהיו $a,b\in \mathbb{Z}$ ו $g=gcd(a,b)$ אזי קיימים $m,n\in\mathbb{Z}$ כך ש $na+mb=g$.

הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב $\mathbb{Z}_p$, כי אם $0\neq a\in\mathbb{Z}_p$ אז $gcd(a,p)=1$ לכן קיימים $m,n$ כך ש $na+mp=1$.

אם נפעיל $mod~p$ על שני צידי המשוואה הזאת נקבל $(na+mp)mod~p = 1mod~p$ שהופך ל $(na)mod~p = 1$

לכן $n~mod~p$ הוא הפכי מתאים ל $a$.