#abstract_algebra #computer_science

אלגוריתם אוקלידס

הגדרה: יהי $a, b$ מספרים שלמים. נאמר ש $a$ מחלק את $b$ אם קיים $k \in Z$ כך ש $k a = b$ , הסימון של זה הוא $a | b$ . למשל $- 5 | 10$ .

משפט החילוק

\forall_{b > 0, a \in Z} \exists!_{q, r \in Z} : a = b q + r

ויתקיים

0 \leq r < b

במילים זה אומר שלכל שתי מספרים שלמים כשאחד מהם הוא לא 0, קיימים $q, r$ יחידים שלמים שיקיימו את הנ״ל.

ההוכחה של זה היא דוגמה מאוד טובה כדי להוכיח קיום ו יחידות. כלומר נרצה קודם כל להוכיח שאכן קיימים כאלה $q, d$ .
יהי

S = {a - b k : k \in Z \land a - b k \geq 0}

וכעת נחלק למקרים:
א) $0 \in S$ אז יתקיים ש $b | a$ ו $q = k$ .
ב) אם $0 \notin S$ נוכל להשתמש בעקרון מבדידה שאנחנו יודעים שלכל קבוצה לא ריקה של מספרים שלמים יש איבר מינימום. עקרון זה נקרא Well-ordering.
ראשית, נרצה להראות ש $a$ אינה קבוצה ריקה.
אם $a > 0$ אז כמובן ש $a - 0 b \in S$ ואם $a < 0$ אז $a (1 - 2 b) = a - 2 a b \in S$ . אם כן, $S$ אינה ריקה בוודאות.
נסמן את המספר הקטן ביותר בקבוצה $S$ כ $r = a - b q$ ויתקיים

r \geq 0 and a = b q + r

כל שנשאר לעשות הוא להראות ש $r$ מקיים את התנאים הדרושים כלומר $r < | b |$ . נב״ש ש $r > | b |$ אז יתקיים

a - b (q + 1) = a - b q - b = r - b > 0

כיוון שב $b > 0$ קיבלנו ש $r - b \in S$ בסתירה למינימליות של $r$ . (נשים לב גם ש $r \neq b$ אחרת $0$ היה בקבוצה בסתירה גם כן)

אם כן, נשאר להוכיח יחידות:

\begin{matrix} a = b q_{1} + r_{1} = b q_{2} + r_{2} \\ b (q_{1} - q_{2}) = r_{2} - r_{1} \end{matrix}

כלומר $b | r_{2} - r_{1}$ וגם $0 \leq r_{1} - r_{2} \leq r_{1} < b$ כלומר $b$ מחלק מספר שקטן ממנו והדרך היחידה שזה יקרה היא אם $r_{2} - r_{1} = 0$ כלומר $r_{2} = r_{1}$ כדרוש.

נשים לב מתקיים ש $a \mod b = r$ .

שקילות mod

נגדיר ש $a, b$ שקולים מודולו $n$ ונסמן $a \equiv_{n} b$ אם קיים $q$ כך ש $a = q \cdot n + b$ .

נשים לב
לכל $a$ מתקיים $a \equiv_{n} r_{a}$ כאשר $r_{a}$ היא השארית של $a$ מודולו $n$ .

משפט: $a b \equiv_{n} r_{a} r_{b}$
הוכחה:

\begin{matrix} a = q_{a} n + r_{a} \\ b = q_{b} n + r_{b} \\ a b = q_{a} q_{b} n^{2} + q_{a} n r_{b} + q_{b} n r_{a} + r_{a} r_{b} \\ = (q_{a} q_{b} n + q_{a} r_{b} + q_{b} r_{a}) n + r_{a} r_{b} \end{matrix}

באופן דומה : $a + b \equiv_{n} r_{a} + r_{b}$ וגם $a^{k} \equiv_{n} (r_{a})^{k}$

gcd

יהיו $n, k \in Z$ נגדיר את $gcd (n, k)$ להיות הטבעי הגדול ביותר שמחלק גם את $n$ וגם את $k$ . באופן פורמלי

gcd (n, k) = max {d \in N | d | n \land d | k}

אם המחלק המשותף הגדול ביותר הוא $1$ נאמר שהאיברים זרים.

קיצור: במקום $g d c (n, k)$ נרשום פשוט $(n, k)$ .

טענה אם $n > k$ אז $gcd (n, k) = g c d (n - k, k)$ , ההוכחה נובעת ישירות מהעובדה שאם $d$ מחלק של $n, k$ אז הוא בהכרח מחלק גם את ההפרש (וכל צירוף ליניארי אחר) ולכן קבוצת המחלקים של שניהם שקולה (וסופית) ולכן גם המקסימום זהה לשתי הקבוצות.

למשל- $17, 49$ יקיימו ש

gcd (49, 17) = gcd (15, 17) = gcd (17, 15) = gcd (2, 15) = 1

טענה כל מחלק משותף של $n, k$ מחלק כל צירוף ליניארי $a n + b k$ . בפרט נכון עבור ה $gcd (n, k)$ . לכן כל $d$ מחלק משותף הוא בעצמו צירוף ליניארי מהצורה הנ״ל.
אם כן , נוכל להגדיר את הממ״מ כצירוף ליניארי מזערי כלומר

gcd (n, k) = min {a n + b k \in N | a, b \in Z}

משפט: אם $n = q m + r$ אז $(n, m) = (m, r)$ .
הוכחה-
נסמן $d = (n, m)$ וצריך להראות ש $d = (m, r)$ . אנו יודעים כי $d | n$ וגם $d | m$ . כמו כן בהכרח אנחנו יודעים שקיימים $q, r$ עבורם $n = q m + r$ . נשים לב ש $r$ הוא בעצם צירוף ליניארי של $n, m$ ולכן $d | r$ כלומר הוא מחלק את $r$ אבל אבל הוא לא בהכרח המחלק המשותף הגדול ביותר בין $(m, r)$ , רק משותף לפי ההגדרה ולכן

d \leq (m, r)

כעת, כמובן שמתקיים ש $(m, r)$ מחלק את $r, m$ . אלו הם בסך הכל צירוף ליניארי של $n$ ולכן $(m, r) | n$ אבל הוא מחלק גם של $m$ לפי מה שאמרנו ולכן כיוון ש $d$ הוא המחלק המשותף הגדול ביותר בין $n, m$ מתקיים

(m, r) \leq d = (n, m)

סך הכל מתקיים

(m, n) = d = (m, r)

אלגוריתם אוקלידס הבסיסי

עם הטענות הנ״ל נוכל למצוא את המחלק המשותף המקסימלי באמצעות אלגוריתם אוקלידס, נוכל להניח ש $0 \leq m < n$ :
א) אם $m = 0$ אז $(n, m) = n$ או אם $m = 1$ החזר $1$
ב) חשב $n = q m + r$ .
ג) המשך עם $(n, m) = (m, r)$ .

דוגמה
נחשב את הממ״מ של $53, 47$

\begin{matrix} (53, 47) \overset{53 = 1 \cdot 47 + 6}{=} (47, 6) \\ \overset{47 = 7 \cdot 6 + 5}{=} (6, 5) = (5, 1) \overset{5 = 1 \cdot 5 + 0}{=} (1, 0) = 1 \end{matrix}

אלגוריתם אוקלידס המורחב

כדי למצוא את המקדמים שמאפיינים את ה $gcd$ נשתמש באלגוריתם אוקלידס המורחב , בכל שלב באלגוריתם אוקלידס הרגיל, לפני פעולת ההחלפה, נבטא את השארית כצירוף ליניארי ונעדכן אותו עד שנגיע לממ״מ.

דוגמה

\begin{matrix} (234, 61) \overset{234 = 3 \cdot 61 + 51, 51 = 234 - 3 \cdot 61}{=} (61, 51) \\ \overset{61 = 51 + 10, 10 = 61 - 51 = 61 - 234 + 3 \cdot 61}{=} (51, 10) \\ \overset{51 = 10 \cdot 5 + 1, 1 = 51 - 5 \cdot (61 - 234 + 3 \cdot 61)}{=} (10, 1) = 1 \end{matrix}

סך הכל נפשט את הביטוי תוך שמירה על המתחלקים ונקבל

51 - 5 (4 \cdot 61 - 234) = 51 - 20 \cdot 61 + 5 \cdot 234 + 234 - 3 \cdot 61 = - 23 \cdot 61 + 6 \cdot 234

lcm

בהינתן שני מספרים שלמים $n, m$ הכפולה המשותפת המזערית כמ״מ שלהם מוגדרת להיות

l c m (n, m) = min {d \in N | n | d \land m | d}

לעתים נסמן רק $[n, m]$ . למשל $[6, 10] = 30$ .

תכונות

חישוב סדר של איבר

תהי $G$ חבורה ויהיו $a, b \in G$ איברים מתחלפים ( $a b = b a$ ) וגם $⟨ a ⟩ \cap ⟨ b ⟩ = {e}$ אזי

o (a b) = [o (a), o (b)]

הוכחה-
נסמן $n = o (a)$ ו $m = o (b)$ . מתקיים

(a b)^{[n, m]} = a^{[n, m]} b^{[n, m]} = e \cdot e

נובע מהטענה שאמרנו שאיבר בחזקה הוא איבר היחידה אמ״מ הסדר מחלק את החזקה. כיוון שבכל אחת מהחזקות הנ״ל הסדר מחלק את החזקה בוודאות מהגדרת $l c m$ אז זה מתקיים. סף הכל הראנו

(a b)^{[n, m]} = e

ולכן $o (a b) | [n, m]$ .

כעת נרצה להראות מינימליות. כלומר אם החזקה הזאת נותנת את $e$ אז כל חזקה קטנה יותר עד ל 0 לא נותנת את $e$ . נב״שׁ שקיים $t < [n, m]$ עבורו $(a b)^{t} = e$ כעת יתקיים מהנתון שהאיברים מתחלפים

a^{t} = b^{- t} \in ⟨ a ⟩ \cap ⟨ b ⟩ = {e}

ולכן $a^{t} = b^{- t} = e$ כלומר $n | t, m | t$ ובפרט $[n, m] | t$ .

סך הכל קיבלנו ש

o (a b) | [n, m] \land [n, m] | t \to o (a b) | t

בסתירה לכך ש $t < o (a b)$ .

סדר של תמורה

מהמשפט הנ״ל אחת המסקנות השימושיות יהיו שסדר של תמורה הוא הlcm של הסדרים של המחזורים הזרים שמרכיבים אותה.

סדר של חזקה

לכל חבורה $G$ , $a \in G$ וחזקה טבעית $d$ מתקיים

o (a^{d}) = \frac{o (a)}{(d, o (a))}

סדר של איבר במכפלה ישרה

הlcm של הסדרים של כל איבר בזוג הסדור של המכפלה