הבדלים בין גרסאות בדף "משתמש:איתמר שטיין/הסבר הופכי"

גרסה מ־10:35, 11 ביולי 2012

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

@@ שורה 9: / שורה 9: @@
 שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב <math>\mathbb{Z}_{101}</math>? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
+כדי להסביר איך מוצאים הופכי ב <math>\mathbb{Z}_p</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>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>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>.