משתמש:איתמר שטיין/הסבר הופכי
מתוך Math-Wiki
כאשר אנו מבצעים חישובים בשדה (נזכור ש חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י ניחוש, אם אז יש איברים שיכולים להיות הופכי:
(למעשה יש פחות, כי לעולם לא יהיה הופכי ו הופכי רק ב)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב ? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו אומרים ש מחלק את (ומסמנים ) אם קיים כך ש .
הגדרה: יהיו המחלק המשותף המירבי של (מסומן ) הוא המספר הגדול ביותר שמחלק גם את וגם את .
כלומר
ההגדרה הזאת בעייתית כאשר במצב זה אומרים ש .