Oiler group

#abstract_algebra #computer_science

נרצה לקרב את העולם של כפליות לחוג השאריות.

טענה
בחוג השאריות $Z_{n}$ איבר $k$ יהיה הפיך תחת פעולת הכפל מודולו אמ״מ $n, k$ זרים.
הוכחה- יהי $0 < k \leq n - 1$ . נניח ש $n, k$ אינם זרים ונוכיח ש $k$ אינו הפיך. אם הם אינם זרים אז
$(n, k) = a > 1$ ונגדיר $n = t a, k = q a$ .

t k = t q a = q n = 0

(תחת פעולת ה mod)

ומכאן מתקיים ש $t k$ מחלקי 0 . כעת במצב זה אם $k$ היה הפיך היינו מקבלים ש

t k k^{- 1} = 0 \to t = 0

בסתירה כיוון ש $a | n$ ולכן $t > 0$ .

במצב בו $n, k$ זרים אחד לשני כלומר $(n, k) = 1$ נסמן

(n, k) = a n + b k = 1

מהגדרת שקילות מודולו מתקיים $1 \equiv_{n} b k$ וגם אנחנו יודעים ש $b \equiv_{n} r_{b}$ כלומר $b k \equiv_{n} r_{b} k$ . סך הכל $1 \equiv_{n} r_{b} k$ כלומר $k^{- 1} = r_{b}$ כי הם שקולים מודולו ל $1$ שזה הפעולה שאיתה אנחנו עובדים.

מסקנה- $Z_{n}$ שדה אמ״מ $n$ ראשוני.

למשל ב $Z_{12}$ ההפיכים הם $1, 5, 7, 11$ .

המשפט הקטן של פרמה

יהי $p$ ראשוני ויהי $1 \leq a < p$ אזי $a^{p - 1} \equiv_{p} 1$ . עם זה מאוד קל להראות שמספר הוא לא ראשוני אל יכול להיות מצב שישנה שקילות מודולו ל $1$ אבל המספר אינו ראשוני. יש לזה חשיבות באלגוריתמי הצפנה שצריכים לבדוק האם מספר הוא ראשוני או לא.

חבורת אוילר

יהי $n \in N$ נגדיר את חבורת אוילר $U_{n}$ להיות קבוצת כל המספרים ההפיכים ב $Z_{n}$ עם כפל מודולו $n$ .

למשל

U_{7} = {1, 2, 3, 4, 5, 6}

פונקציית אוילר

יהי $n \in N$ נגדיר את פונקציית אוילר להיות $φ (n) = | U_{n} |$ .

משפט אוילר :
לכל $a \in U_{n}$ מתקיים $a^{φ (n)} \equiv_{n} 1$ .
נכונות נובעת בגלל ש $o (a) | φ (n)$ כי סדר של איבר מחלק את סדר החבורה ולכן

φ (n) = t \cdot o (a)

ולכן ממשפט מתקיים

a^{φ (n)} m o d n = 1 \to a^{φ (n)} \equiv_{n} 1

הבחנה

ממשפט פרמה הקטן ומהנ״ל נובע ש אם $p$ הוא ראשוני, אז $U_{p} = Z_{p}^{*}$ כאשר $Z^{*} = Z_{p} - {0}$

נוסחה לחישוב פונקציית אוילר

φ (n) = n \cdot (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{k}})

כאשר לפי המשפט היסודי של האריתמטיקה כל מספר $n$ שלם ניתן לפרק למכפלת חזקות של גורמים ראשוניים כלומר

n = p_{1}^{m_{1}} \cdot p_{2}^{m_{2}} \dots p_{k}^{m_{k}}

כלומר נוכל לחשב את הסדר של חבורת אוילר על ידי פירוק $n$ לגורמים ראשוניים והצבה בנוסחה.