תתי-חבורות וחבורות ציקליות

בפוסט הקודם הצגתי את המושג של חבורה. ראינו כמה דוגמאות, ואז ניסינו להבין מהן החבורות הפשוטות ביותר. הגענו עד גודל 5 לפני שהתייאשנו משיטת העבודה עם טבלת כפל והגענו למסקנה שצריך כלים יותר נוחים, אבל כבר הספקנו לראות תופעה מוזרה: הייתה רק חבורה בודדת לכל גודל מ-1 עד 3, בעוד שמגודל 4 היו כבר שתי חבורות שונות, ואז בגודל 5 פתאום הייתה שוב רק חבורה אחת. מה השתבש? עד סוף הפוסט נבין את זה.

תת-חבורות

דרך מועילה אחת להבין חבורה היא על ידי הסתכלות בתת-הקבוצות שלה שהן בעצמן חבורה, עם אותה פעולה כמו החבורה המקורית. לכאלו דברים קוראים תת-חבורה של החבורה המקורית. מתבקש לפתוח כאן בדוגמה, אז בואו נלך לדוגמה האהובה עלי - המספרים השלמים, \( \mathbb{Z} \). איזו תת-קבוצה מפורסמת של המספרים השלמים קיימת? מדגדג אולי לצרוח “ראשוניים!!!!!” או משהו, אבל תמיד כדאי לחשוב פשוט יותר, ותת-הקבוצה המפורסמת ביותר של השלמים, מלבד הטבעיים (שאינם חבורה) כמובן היא המספרים הזוגיים, שאסמן בתור \( 2\mathbb{Z}=\left\{ 0,2,-2,4,-4,\dots\right\} \).

מכיוון שהזוגיים הם תת-קבוצה של \( \mathbb{Z} \), פעולת החיבור שמוגדרת על השלמים מוגדרת גם עליהם. אבל האם הם מהווים חבורה ביחס לפעולת החיבור הזו? צריך לבדוק ארבעה דברים. ראשית, שהפעולה הזו היא באמת פעולה בינארית מעל המספרים הזוגיים. כלומר, שכאשר מזינים לה קלטים שהם מספרים זוגיים, גם הפלט יהיה מספר זוגי. אומרים על זה לפעמים שהזוגיים סגורים ביחס לפעולה הזו. לפעמים כשמתארים חבורות דורשים סגירות באופן מפורש בתור אקסיומה - בפוסט הקודם אמרתי שאצלי זה פשוט מובלע באמירה שהפעולה הבינארית היא “מעל” הקבוצה.

במקרה של הזוגיים סגירות כזו בוודאי מתקיימת - סכום של שני זוגיים הוא זוגי. אבל במקרה של האי-זוגיים היא לא מתקיימת, \( 1+1=2 \) למשל, ועל כן כבר אבוד לאי-זוגיים להיות תת-חבורה של השלמים - אבל אל תדאגו, האי-זוגיים עוד יחזרו בהמשך.

מה התכונות הנוספות שחבורה צריכה לקיים? הפעולה צריכה להיות אסוציאטיבית, אבל זה ברור - חיבור הוא פעולה אסוציאטיבית על השלמים, כלומר לכל שלשה של שלמים כלשהם \( a,b,c \) מתקיים \( a+\left(b+c\right)=\left(a+b\right)+c \). המשוואה הזו בפרט תתקיים אם אני אזין אליה רק סוג מסויים של שלמים, במקרה שלנו זוגיים. לכן אסוציאטיביות של פעולה היא תמיד משהו שאנחנו מקבלים בחינם כשאנחנו בודקים תת-קבוצה של משהו שאנחנו כבר יודעים שהוא חבורה.

כעת, 0 הוא זוגי, אז יש לנו איבר אדיש בזוגיים, ולכל זוגי \( a \) גם \( -a \) הוא זוגי ולכן גם יש לנו הופכי. כלומר, הזוגיים הם אכן תת-חבורה של השלמים; זו הדוגמה הראשונה שלנו. באופן דומה אפשר לראות שלכל \( n \) טבעי, \( n\mathbb{Z}=\left\{ 0,n,-n,2n,-2n,\dots\right\} \) הוא תת-חבורה (“כל המספרים שמתחלקים ב-\( n \)”). בהמשך נראה שאלו גם תת-החבורות היחידות של \( \mathbb{Z} \).

באופן כללי, אם \( G \) היא חבורה ו-\( H\subseteq G \) היא תת-קבוצה של \( G \), אומרים ש-\( H \) היא תת-חבורה של \( G \) אם \( H \) סגורה ביחס לפעולה של \( G \) ומהווה חבורה ביחס אליה. זה אומר שאם \( e \) הוא האדיש של \( G \) הוא יהיה חייב להיות גם האדיש של \( H \), ולכל \( a\in H \) יתקיים גם \( a^{-1}\in H \) כאשר \( a^{-1} \) הוא ההופכי של \( a \) ב-\( G \). אם תחשבו על זה רגע תראו שמסתתר פה תרגיל כלשהו - מי אומר לנו ש-\( e \) חייב להיות ב-\( H \)? למה שלא יהיה ב-\( H \) איבר כלשהו, נקרא לו \( f \), כך ש-\( fa=a \) לכל איבר של \( H \), למרות שיש איברים ב-\( G \) שהם לא ב-\( H \) שאותם \( f \) לא מקבעת? ובכן, הסבר פשוט במיוחד: כי \( f \) בפרט צריכה לקיים \( f\cdot f=f \) ואת זה יכול לקיים רק האדיש \( e \) (כי \( ef=f \) ולכן \( ef=ff \) גורר \( e=f \), על פי מה שראינו בפוסט הקודם).

את כל הדרישות שלנו מתת חבורה - סגירות לפעולה, ש-\( e \) יהיה בפנים, שההופכיים יהיו בפנים - אפשר לקפל לתוך מבחן בודד:

• קבוצה לא ריקה \( H\subseteq G \) היא תת-חבורה של \( G \) אם ורק אם לכל \( x,y\in H \) מתקיים \( xy^{-1}\in H \)

סגירות נובעת מזה כך: אם אנחנו רוצים לוודא שעבור \( a,b\in H \) מתקיים \( ab\in H \) פשוט נבחר \( x=a \) ו-\( y=b^{-1} \) (כי אז \( y^{-1}=\left(b^{-1}\right)^{-1}=b \)). עבור אדיש: הנחנו ש-\( H \) לא ריקה ולכן יש בה \( a \). לכן עבור \( x=y=a \) אמור להתקיים ש-\( e=aa^{-1}\in H \). ולגבי הופכי: עבור \( a \) נבחר \( x=e \) ו-\( y=a \) ונקבל \( a^{-1}=ea^{-1}\in H \).

הדרך האינטואיטיבית לחשוב על איבר כמו \( ab^{-1} \) הוא בתור ה”חיסור” של \( b \) מ-\( a \), או ה”חלוקה” של \( a \) ב-\( b \), תלוי אם אנחנו חושבים על הפעולה של החבורה בתור משהו דמוי חיבור או בתור משהו דמוי כפל. אם כך, האינטואיציה שלנו לגבי תת-חבורה היא שזו תת-קבוצה לא ריקה של \( G \) שסגורה לחילוק וכל היתר נובע מכך.

עכשיו אני רוצה להציג תרגיל נחמד שיתן לנו מוטיבציה לנושא הבא שאציג פה. אני טוען שאם \( H \) היא תת-קבוצה סופית ולא ריקה של \( G \) אז כדי לבדוק שהיא תת-חבורה מספיק לבדוק שהיא סגורה לכפל, לא לחילוק. הסופיות היא קריטית פה, אחרת \( \mathbb{N} \) הייתה “תת-חבורה” של \( \mathbb{Z} \) (שכן היא סגורה לפעולת ה”כפל” של \( \mathbb{Z} \) שהיא פעולת החיבור הרגילה שאנחנו מכירים). מה שצריך להראות בפועל הוא שאם \( a\in H \) אז גם \( a^{-1}\in H \), כי יחד עם הסגירות לכפל זה מאפשר לנו להראות שלכל \( x,y\in H \) מתקיים \( xy^{-1}\in H \) (“ראשית, \( y\in H \) ולכן \( y^{-1}\in H \) על פי מה שראינו; שנית, מסגירות לכפל נקבל \( xy^{-1}\in H \)”). איך נעשה את זה?

ובכן, זה אחד מהתרגילים הנחמדים הללו שבהם גם אם אין לנו שמץ של מושג מה לעשות, בגלל שאומרים לנו שאפשר לעשות את זה אנחנו אופטימיים מספיק בשביל פשוט לעשות דברים. יש לנו ביד את \( a \). אומרים לנו “מצאו את ההופכי של \( a \)! אנחנו מאמינים בכם!”. מה יש לנו לעשות עם \( a \)? שום דבר כמעט. מה אנחנו יודעים עליו? \( a \) הוא איבר של חבורה. כל מה שאנחנו יודעים הוא שלחבורה יש פעולה שמאפשרת לכפול איברים. את מי נכפול ב-\( a \)? את \( e \)? זה לא יתן שום דבר מעניין. אז מה נשאר? נכפול את \( a \) בעצמו. שוב, ושוב, ושוב. כלומר, נבנה את הסדרה \( a,a\cdot a,a\cdot a\cdot a,\dots \).

אוי ואבוי, ראיתם מה קיבלנו? הסימון \( a,a\cdot a,a\cdot a\cdot a,\dots \) הוא בלתי קריא בעליל. חייבים למצוא קיצור נורמלי. מכיוון שאנחנו משתמשים בסימון דמוי כפל לתיאור הפעולה של החבורה, אפשר להשתמש בסימון דמוי חזקה כדי לתאר הפעלות נשנות של הפעולה על אותו איבר. כלומר, אני מסמן ב-\( a^{n} \) את הפעולה של כפל \( a \) בעצמו \( n \) פעמים, עבור \( n>1 \) טבעי. כעת יותר ברור מה אני מציע לעשות - נבנה את הסדרה \( a^{1},a^{2},a^{3},\dots \) וכן הלאה עד לנצח. בגלל הסגירות של \( H \) לכפל, נקבל סדרה שכל אבריה שייכים ל-\( H \).

בסדרה הזו יש אינסוף מקומות. אבל ב-\( H \) יש רק מספר סופי של איברים. המסקנה (“עקרון שובך היונים”) היא יש בסדרה הזו לפחות שני מקומות שבהם מופיע אותו איבר פעמיים. כלומר, שמתקיים \( a^{n}=a^{k} \) עבור \( n,k \) חיוביים כלשהם, ונניח ש-\( k<n \). מה עכשיו?

עכשיו אני רוצה לקחת את המשוואה \( a^{n}=a^{k} \) ולכפול אותה \( k \) פעמים ב-\( a^{-1} \) (שאני יודע שקיים ב-\( G \)) זה גם כן מזמין סימון. איך נסמן את \( \left(a^{-1}\right)^{k} \) בצורה מקוצרת? כמובן, \( a^{-k} \). קל לבדוק שחוקי החזקות ה”רגילים” יתקיימו כאן: \( a^{n}\cdot a^{-k}=a^{n-k} \). רק צריך עוד סימון אחד כדי שזה יעבוד טוב: \( a^{0}=e \), שהוא ממילא סימון טבעי שכן, נאמר, \( a=a^{1}=a^{0}\cdot a^{1}=e\cdot a \).

אם כן, כפלנו את \( a^{n}=a^{k} \) ב-\( a^{-k} \); נקבל \( a^{n-k}=e \). כלומר, קיבלנו שקיים מספר חיובי \( t \) שמקיים \( a^{t}=e \). נכפול ב-\( a^{-1} \) ונקבל \( a^{t-1}=a^{-1} \), ואנחנו יודעים ש-\( a^{t-1}\in H \) בגלל הסגירות לכפל. בכך סיימנו את ההוכחה של התרגיל שלנו, אבל הצגנו כמה רעיונות מעניינים הרבה יותר מהתרגיל עצמו. ראשית, ראינו שיש משהו מעניין במספר חיובי \( t \) שמקיים \( a^{t}=e \) (“חיובי”, כי \( a^{0}=e \) לא מעניין במיוחד - זו בסך הכל ההגדרה). באופן כללי אם יש לנו מספרים טבעיים חיוביים שעושים משהו מעניין, זה כלל אצבע לא רע לחפש את הקטן ביותר מביניהם (זו התכונה המיוחדת של טבעיים - בכל קבוצה של טבעיים יש איבר קטן ביותר). למספר הטבעי החיובי הקטן ביותר שעבורו \( a^{t}=e \) (אם קיים כזה) קוראים הסדר של \( a \), ומסמנים אותו ב-\( o\left(a\right) \). מה שההוכחה הקודמת הראתה הוא שבחבורה סופית, לכל איבר יש סדר סופי. ב-\( \mathbb{Z} \) לעומת זאת לאף איבר פרט ל-\( 0 \) אין סדר סופי (הסדר של האדיש בחבורה הוא תמיד 1). האם יש חבורות אינסופיות עם איברים מסדר סופי? בטח, ונראה כאלו בהמשך.

לבינתיים, תכונה מועילה של סדר של איבר היא זו: אם \( a^{t}=e \) עבור \( t \) חיובי כלשהי, אז הסדר של \( a \) מחלק את \( t \). בסימונים, \( o\left(a\right)|t \). ההוכחה מאוד דומה בסגנונה להוכחות כלליות שמסתמכות על “הטבעי הקטן ביותר ש…”. אנחנו מחלקים את \( t \) ב-\( o\left(a\right) \) ומקבלים מנה \( q \) ושארית \( 0\le r<o\left(a\right) \), כלומר \( t=q\cdot o\left(a\right)+r \). כעת נשתמש בחוקי החזקות:

\( e=a^{t}=a^{q\cdot o\left(t\right)+r}=\left(a^{o\left(t\right)}\right)^{q}\cdot a^{r}=e^{q}\cdot a^{r}=a^{r} \)

וקיבלנו ש-\( a^{r}=e \). כעת, \( o\left(a\right) \) הוא הטבעי החיובי הקטן ביותר שכשמעלים את \( a \) בחזקה שלו מקבלים \( e \). מכיוון ש-\( r \) קטן ממנו, לא ייתכן שגם הוא חיובי, ולכן \( r=0 \), כלומר \( t \) מתחלק ב-\( o\left(a\right) \).

חבורות ציקליות

הדבר המרכזי שקיבלנו מהתרגיל של “תת-קבוצה סופית של חבורה שסגורה לכפל היא תת-חבורה” היה שיש עניין בדיבור על חזקות של איבר \( a \). גם על חזקות חיוביות וגם על חזקות שליליות (שהן דרך אחרת לומר “חזקות חיוביות של ההופכי של \( a \)”). אני לא אטרח להוכיח שחוקי החזקות מתקיימים, אבל הם מתקיימים: \( a^{n}\cdot a^{k}=a^{n+k} \) לכל \( n,k\in\mathbb{Z} \) (כאן \( \mathbb{Z} \) הם על תקן “המספרים השלמים” ולא על תקן “חבורה”) וכמו כן \( \left(a^{n}\right)^{k}=a^{nk} \). אתם יכולים לנסות להוכיח את זה אם זה ממש חשוב לכם; אני אשתמש בזה באופן חופשי מכאן ואילך.

כעת, המשוואה \( a^{n}\cdot a^{-k}=a^{n-k} \) מראה לנו שאוסף החזקות של \( a \) סגור תחת חילוק (\( x=a^{n},y=a^{k} \)). זה אומר שלכל חבורה \( G \), ולכל איבר \( a\in G \), הקבוצה \( H=\left\{ \dots,a^{-2},a^{-1},a^{0},a^{1},a^{2},\dots\right\} \) היא תת-חבורה של \( G \). את תת-החבורה הזו מסמנים לפעמים ב-\( \left\langle a\right\rangle \) וקוראים לה תת-החבורה הנוצרת על ידי \( a \). באופן כללי, אם \( G \) היא חבורה כלשהי כך ש-\( G=\left\langle a\right\rangle \) עבור \( a\in G \), אומרים ש-\( G \) היא חבורה ציקלית. חבורות ציקליות הן הסוג הפשוט ביותר של חבורות שקיים, ולכן גם אחד מהסוגים החשובים ביותר; בהמשך נראה, למשל, שכל חבורה אבלית סופית אפשר לתאר באמצעות מכפלה ישרה של חבורות ציקליות (עוד לא הגדרתי במפורש מה זו מכפלה ישרה). שימו לב שהגודל של \( G=\left\langle a\right\rangle \) שווה בדיוק לסדר של \( a \) . זה אולי נותן מוטיבציה כלשהי לכך שבתורת החבורות, נהוג לקרוא למספר האיברים ב-\( G \) בשם הסדר של \( G \). שימו גם לב לכך שלפי חוקי החזקות, \( a^{n}\cdot a^{k}=a^{n+k}=a^{k}\cdot a^{n} \), כלומר בחבורה ציקלית פעולת הכפל היא תמיד קומוטטיבית - כל חבורה ציקלית היא בפרט חבורה אבלית.

יש שלושה דברים טובים במיוחד עם חבורות ציקליות. ראשית, הן שימושיות מאוד. שנית, אין הרבה מהן. לבסוף, אנחנו מבינים את מה שכן יש באופן מושלם. את השימושיות נראה בהמשך. את הקטע של “אין הרבה מהן” אפשר להסביר עכשיו אבל עדיין לא להוכיח בצורה רצינית: החבורות הציקליות היחידיות שקיימות הן \( \mathbb{Z} \) ו-\( \mathbb{Z}_{n} \) לכל \( n \) טבעי. כלומר, לכל מספר טבעי \( n \) יש בדיוק חבורה ציקלית אחת עם \( n \) איברים, ויש גם חבורה ציקלית אחת עם \( \aleph_{0} \) איברים (“אינסוף איברים”). זה לא אומר שאי אפשר לתת דוגמאות אחרות לחבורות ציקליות, רק שבמובן מסויים הן יהיו “אותו הדבר”. ואני אתן דוגמא פשוטה. הביטו בחבורה \( \mathbb{Z}_{7}^{*} \). זו חבורת המספרים \( \left\{ 1,2,3,4,5,6\right\} \) עם פעולת כפל מודולו 7. בואו ניקח את \( 3 \) ונתחיל לחשב את החזקות שלו: \( 3^{2}=2 \) (כי \( 3^{2}=9 \) במספרים טבעיים, ועכשיו תחלקו ב-7 וקחו את השארית), \( 3^{3}=6 \) (פשוט תכפלו את \( 3^{2} \) ב-\( 3 \) שוב), \( 3^{4}=4 \), \( 3^{5}=5 \) ו-\( 3^{6}=1 \). כזכור, \( 1 \) הוא איבר היחידה של \( \mathbb{Z}_{7}^{*} \) כך שקיבלנו שהסדר של \( 3 \) הוא 6. במקרה או שלא במקרה, זה גם מספר האיברים ב-\( \mathbb{Z}_{7}^{*} \). קיבלנו שחזקות של 3 יוצרות את כל האיברים של \( \mathbb{Z}_{7}^{*} \) ולכן זו חבורה ציקלית בת 6 איברים. איזו עוד חבורה ציקלית בת 6 איברים יש? \( \mathbb{Z}_{6} \). אלו כמובן חבורות שונות - הפעולה בהן שונה, האיברים שלהן שונים… אבל אם נקרא ל-3 בשם “1” ול-2 בשם “2” ול-6 בשם “3” וכן הלאה, ובמקום לבצע כפל נבצע חיבור, נקבל את אותה החבורה. אני אפרמל את הטענה הזו בהמשך.

נקודה מאוד חשובה שאני רוצה לציין כאן הוא שאמנם ראינו פה ש-\( \mathbb{Z}_{6} \) ו-\( \mathbb{Z}_{7}^{*} \) הן תיאורים שונים לאותה החבורה, אבל זה לא אומר שאין חשיבות לכך שהתיאורים הללו הם שונים. יש לזה חשיבות אדירה. כשמתעסקים עם חבורות, הייצוג שיש לנו לחבורה כלשהי קובע כמה קל או קשה יהיה לנו לעבוד איתה. דוגמה בסיסית שאני אוהב לתת פה: לא מעט אלגוריתמי הצפנה מתבססים על בעיה שנקראת “בעיית הלוגריתם הדיסקרטי”. היא אומרת דבר כזה: נותנים לכם חבורה \( G \) כלשהי, ונותנים לכם איבר \( a\in G \) ואיבר \( b\in G \) כך שידוע שמתקיים \( a^{n}=b \). עכשיו לכו תמצאו מהו \( n \) (אם \( a,b \) ו-\( n \) הם מספרים ממשיים חיוביים זו הבעיה של מציאת \( \log_{a}b \), ומכאן השם של הבעיה). כעת, אם \( G=\mathbb{Z}_{6} \) ו-\( a=1 \) הבעיה הזו היא כמובן טריוויאלית: בהינתן \( b \) כלשהו, \( n=b \). לעומת זאת, אם \( G=\mathbb{Z}_{7}^{*} \) ו-\( a=3 \), אז הרבה פחות ברור איזו פרוצדורה חישובית תניב לנו מ-\( b=5 \) את \( n=5 \). בפועל בעיית הלוגריתם הדיסקרטי בחבורות \( \mathbb{Z}_{n}^{*} \) - גם אלו מהן שהן ציקליות - היא בעיה קשה מבחינה חישובית, בזמן שבחבורות \( \mathbb{Z}_{n} \) היא טריוויאלית. אופן הייצוג משפיע על הקושי. תשאלו: אם כן, בהינתן \( \mathbb{Z}_{n}^{*} \) ציקלית, למה לא לעבור לעבוד עם הייצוג השני, הנוח לנו יותר? התשובה היא שגם למצוא את ההתאמה המדויקת שמעבירה אותנו מייצוג אחד לשני זה קשה…

בואו נחזור עכשיו ל-\( \mathbb{Z}_{n} \). בשיטת הייצוג הזו של חבורה ציקלית עם \( n \) איברים, יחסית קל להבין את המבנה של החבורה. ראשית כל, מהן תת-החבורות שלה? אני טוען שהן כולן ציקליות. כדי לראות את זה, בואו ניקח תת-חבורה \( H \) כלשהי של \( \mathbb{Z}_{n} \). זו קבוצה של מספרים טבעיים, כך שאני יכול לבחור את החיובי הקטן ביותר מביניהם - בואו נקרא לו \( a \). עכשיו ניקח איבר \( b\in H \) כלשהו וננקוט בתעלול שכבר הראיתי יותר מוקדם בפוסט - נחלק את \( b \) ב-\( a \) ונקבל \( b=qa+r \) כאשר \( 0\le r<a \). המשוואה הזו פירושה גם \( r=b-qa \), אבל מכיוון ש-\( H \) היא תת-חבורה היא סגורה לחיסור; והביטוי \( b-qa \) זו דרך לומר “לחסר את \( a \) מ-\( b \) בדיוק \( q \) פעמים” (או, אם \( q \) שלילי, “לחבר את \( a \) ל-\( b \) מינוס \( q \) פעמים”). לכן \( r=b-qa\in H \). מכיוון שלקחנו את \( a \) להיות הטבעי החיובי המינימלי ב-\( H \) ו-\( r<a \) בהכרח \( r=0 \), כלומר \( a \) מחלק את \( b \), וזאת לכל \( b\in H \). דהיינו, \( H=\left\langle a\right\rangle \) (ההוכחה הזו עובדת גם עבור \( \mathbb{Z} \)).

מכיוון שכל איבר בחבורה יוצר תת-חבורה ציקלית, אנחנו יודעים עכשיו בדיוק מהן תת-החבורות של \( \mathbb{Z}_{n} \) - אלו תת-החבורות שנוצרות על ידי כל אברי \( \mathbb{Z}_{n} \). השאלה המעניינת הבאה היא זו: מה גודל תת-החבורה שנוצרת על ידי \( a \)? הגודל שלה שווה לסדר של \( a \), כך שהשאלה בעצם היא מה הסדר של \( a \) מודולו \( n \). בניסוח בשיטת הסימון של \( \mathbb{Z}_{n} \), השאלה היא מהו \( k \) הטבעי הקטן ביותר כך ש-\( k\cdot a=0 \) מודולו \( n \). כלומר, מהו ה-\( k \) הטבעי הקטן ביותר כך ש-\( n \) מחלק את \( k\cdot a \). כאן מבקר אותנו מושג מתורת המספרים האלמנטרית - הכפולה המשותפת המינימלית. \( k\cdot a=\text{lcm}\left(a,b\right) \) היא הכפולה המשותפת המינימלית של \( a,n \). מתורת המספרים ידוע ש-\( \text{lcm}\left(a,n\right)=\frac{a\cdot n}{\text{gcd}\left(a,n\right)} \) כאשר \( \text{gcd}\left(a,n\right) \) הוא המספר הגדול ביותר שמחלק את \( a \) ו-\( n \) גם יחד - המחלק המשותף המקסימלי - ולכן \( k=\frac{n}{\text{gcd}\left(a,n\right)} \).

בפרט, קיבלנו פה ש-\( k \) מחלק את \( n \). כלומר: הסדר של כל תת-חבורה של \( \mathbb{Z}_{n} \) מחלק את הסדר של \( \mathbb{Z}_{n} \), שהוא \( n \). זו לא תוצאה מקרית אלא מקרה פרטי של המשפט המרכזי שאני חותר אליו כרגע ואגיע בפוסט הבא - משפט לגראנז', שאומר שלכל חבורה סופית \( G \) ולכל תת-חבורה \( H \) של \( G \), הסדר של \( H \) חייב לחלק את הסדר של \( G \). כבר עכשיו אפשר להבין השלכה אחת של המשפט הזה. ראשית, מכיוון שהסדר של איבר בחבורה שווה לסדר של תת-החבורה שהוא יוצר, מסקנה מיידית ממשפט לגרנז’ היא שבחבורה סופית, הסדר של איבר חייב לחלק את סדר החבורה (בחבורה אינסופית אין מגבלה על הסדר של איבר).

עכשיו, נאמר ש-\( G \) היא חבורה כלשהי מסדר \( p \) כאשר \( p \) ראשוני. בואו ניקח \( a\in G \) כך ש-\( a\ne e \). מה הסדר של \( a \) יכול להיות? מספר ראשוני מתחלק רק ב-1 ובעצמו, אז הסדר של \( a \) יכול להיות רק 1 או \( p \). אבל האיבר היחיד מסדר \( 1 \) הוא \( e \), ולכן הסדר של \( a \) חייב להיות \( p \), מה שאומר שבתת-החבורה של \( G \) שנוצרת על ידי \( a \) יש \( p \) איברים, כמו ב-\( G \) עצמה. במילים אחרות, \( G=\left\langle a\right\rangle \). נחדד: המשפט שהראינו כרגע אומר שכל חבורה מסדר ראשוני היא ציקלית ונוצרת על ידי כל איבר בה פרט ל-\( e \). זה מסביר את התוצאה ה”מוזרה” מהפוסט הקודם שקיימת רק חבורה אחת מסדר 5.

כדי לסיים את הנושא של חבורות ציקליות אני רוצה לדבר עוד קצת על המבנה שלהן. ראינו כבר שכל תת-החבורות של חבורה ציקלית הן ציקליות בעצמן והסדר שלהן מחלק את הסדר של החבורה. אבל כמה כאלו יש? התשובה אלגנטית להפליא: ל-\( \mathbb{Z}_{n} \) יש בדיוק תת-חבורה אחת מסדר \( k \) עבור כל \( k \) שמחלק את \( n \). כדי להבין את זה כדאי לראות דוגמה. נאמר, \( \mathbb{Z}_{6} \). מה תת-החבורות של החבורה הזו? יש את \( \left\{ 0\right\} \) ויש את \( \left\{ 1,2,3,4,5,0\right\} \) ויש את \( \left\{ 2,4,0\right\} \) ויש את \( \left\{ 3,0\right\} \). כאן לקחתי את תתי-החבורות שנוצרות על ידי 0,1,2,3. אם אקח את זו שנוצרת על ידי \( 4 \) אקבל \( \left\{ 4,2,0\right\} \) ואותה כבר ראינו; ובדומה, אם אקח את \( 5 \) אקבל את \( \left\{ 1,2,3,4,5,0\right\} \) שכבר ראינו.

למה זה עובד? ובכן, ראשית, יהא \( k \) כלשהו שמחלק את \( n \), אז \( \left\langle \frac{n}{k}\right\rangle \) היא תת-חבורה ציקלית מסדר \( k \) (היא מכילה את כל האיברים מהצורה \( \frac{n}{k}i \) עבור \( 1\le i\le k \)), אז קיימת תת-חבורה מסדר \( k \) לכל \( k \) שמחלק את \( n \). עכשיו צריך להוכיח שהיא יחידה. בואו נחזור לרגע לדוגמה שלנו. אצלנו \( n=6 \) והסתכלתי, נאמר, על \( k=3 \). אמרתי: קיימת תת-חבורה מסדר 3 - זו שנוצרת על ידי \( \frac{n}{k}=\frac{6}{3}=2 \). ואכן, \( \left\{ 2,4,0\right\} \) היא תת-חבורה מסדר 3 ואנחנו שמחים. אבל עכשיו באה לה עוד חבורה \( H \) מסדר 3 ואנחנו חייבים להראות שהיא שווה ל-\( \left\{ 2,4,0\right\} \). מה נעשה? אני אגיד דבר כזה: נניח שהיוצר של \( H \) הוא \( b \). אנחנו יודעים שהסדר של \( b \) הוא \( \frac{6}{\text{gcd}\left(6,b\right)} \) מצד אחד, ומצד שני אנחנו יודעים שהסדר של \( b \) חייב להיות שווה 3 כי זה הגודל של \( H \). קיבלנו ש-\( \frac{6}{\text{gcd}\left(6,b\right)}=3 \) כלומר \( \text{gcd}\left(6,b\right)=2 \). זה בפרט אומר ש-\( b \) מתחלק על ידי 2, כלומר הוא שייך לחבורה הציקלית ש-\( 2 \) יוצר. קיבלנו ש-\( b \) הוא איבר בחבורה מסדר 3 (החבורה ש-2 יוצר) ומצד שני הוא עצמו מסדר 3, ולכן גם הוא יוצר את החבורה הזו.

הטיעון הכללי הוא אותו הדבר, רק עם אותיות במקום 6 ו-3. נתחיל מחדש: יהא \( k \) כלשהו שמחלק את \( n \). נסמן \( d=\frac{n}{k} \). תהא כעת תת-חבורה \( H \) כלשהי מסדר \( k \); בואו נוכיח ש-\( \left\langle d\right\rangle =H \). לשם כך, ניקח יוצר של \( H \) (כזכור, ראינו ש-\( H \) בהכרח ציקלית) ונסמן אותו ב-\( b \). כעת, \( k=\frac{n}{\text{gcd}\left(b,n\right)} \) מצד אחד, ומצד שני \( k=\frac{n}{d} \). קיבלנו \( \frac{n}{d}=\frac{n}{\text{gcd}\left(b,n\right)} \), כלומר \( d=\text{gcd}\left(b,n\right) \) ובפרט \( d \) מחלק את \( b \), כלומר \( b\in\left\langle d\right\rangle \) וסיימנו מהשיקול שכבר אמרתי.

סיימנו את ההוכחה הזו, ואפשר עכשיו ללכת רחוק עוד יותר. ראינו שסדר תת-החבורה שנוצרת על ידי \( a \) הוא \( \frac{n}{\text{gcd}\left(a,n\right)} \). זה אומר ש-\( a \) הוא יוצר של \( \mathbb{Z}_{n} \) אם ורק אם \( \text{gcd}\left(a,n\right)=1 \), כלומר אם \( a \) זר ל-\( n \) (אין להם מחלקים משותפים גדולים מ-1). כעת, יש סימון מיוחד לפונקציה שעבור מספר טבעי \( n \) מחזירה את מספר הטבעיים שקטנים ממנו וזרים לו - \( \varphi\left(n\right) \) - פונקציית אוילר. מה שראינו כרגע הוא של-\( \mathbb{Z}_{n} \) יש בדיוק \( \varphi\left(n\right) \) יוצרים. עכשיו בואו נשחק משחק: ל-\( \mathbb{Z}_{n} \) יש תת-חבורה אחת בדיוק מסדר \( k \) לכל \( k|n \) (זה הסימון של “\( k \) מחלק את \( n \)”). תת החבורה הזו היא בתכ’לס אותו הדבר כמו \( \mathbb{Z}_{k} \) ולכן יש לה \( \varphi\left(k\right) \) יוצרים. כל איבר של \( \mathbb{Z}_{n} \) הוא יוצר של תת-חבורה כלשהי של \( \mathbb{Z}_{n} \), ולכן קיבלנו שיטה מוזרה לספור את כל \( n \) האיברים ב-\( \mathbb{Z}_{n} \): סופרים את כל היוצרים של כל תת-חבורה אפשרית. זה נותן לנו את הנוסחה הבאה, שאפילו אני שלא אוהב נוסחאות במיוחד חושב שהיא מאוד יפה: \( \sum_{k|n}\varphi\left(k\right)=n \).

עכשיו אנחנו מוכנים לפאנץ’ האחרון של הפוסט הזה, סוג של משפט מיון ראשון עבור חבורות סופיות כלליות שמתבסס על תתי-החבורות שלהן. ניקח חבורה \( G \) מסדר \( n \). אני טוען שאם יש ל-\( G \) לכל היותר תת-חבורה אחת מסדר \( k \) לכל \( k \) שמחלק את \( n \) (כלומר, לכל \( k \) כזה יש לה תת-חבורה אחת או שאין לה בכלל) אז \( G \) ציקלית. ההוכחה היא פשוטה מאוד מבחינה רעיונית - שיקולי ספירה. אני אראה שחייב להיות איבר מסדר \( n \) כי יש בחבורה “יותר מדי איברים” מכדי שיהיו רק איברים מסדרים נמוכים. הפורמליזם גם כן לא מסובך אבל צריך לעקוב אחריו טיפה בזהירות.

ניקח \( G \) סופית כלשהי. בואו נסמן ב-\( a_{k} \) את מספר האיברים מסדר \( k \) ב-\( G \), וב-\( u_{k} \) את מספר תתי-החבורות הציקליות של \( G \) מסדר \( k \). לכל תת-חבורה כזו יש בדיוק \( \varphi\left(k\right) \) יוצרים, כלומר כל תת-חבורה כזו “מכסה” בדיוק \( \varphi\left(k\right) \) מבין \( a_{k} \) האיברים מסדר \( k \). לכן קיבלנו את השוויון \( a_{k}=\varphi\left(k\right)u_{k} \).

נסמן \( \left|G\right|=n \) (הסדר של \( G \) הוא \( n \)). כעת, \( \sum_{k|n}a_{k}=n \) בבירור שכן כל איבר ב-\( G \) הוא מסדר כלשהו שמחלק את \( n \) (זה מסתמך על משפט לגראנז’ שטרם הוכחתי). עכשיו אפשר להכניס לתמונה את ההנחה שלנו ש-\( u_{k}\le1 \) לכל \( k \) ולקבל:

\( n=\sum_{k|n}a_{k}=\sum_{k|n}\varphi\left(k\right)u_{k}\le\sum_{k|n}\varphi\left(k\right)=n \)

כאשר השוויון האחרון הוא מה שהוכחנו קודם. מכיוון שהתחלנו וסיימנו עם אותו המספר, כל המעברים שביצענו הם שוויון ובפרט אי-השוויון \( \sum_{k|n}\varphi\left(k\right)u_{k}\le\sum_{k|n}\varphi\left(k\right) \) הופך לשוויון \( \sum_{k|n}\varphi\left(k\right)u_{k}=\sum_{k|n}\varphi\left(k\right) \). במשולב עם כך ש-\( 0\le u_{k}\le1 \) ושזה מספר טבעי נקבל שבהכרח \( u_{k}=1 \) לכל \( k|n \). כלומר, יש ל-\( G \) תת-חבורה ציקלית יחידה מסדר \( k \) לכל \( k|n \) ובפרט עבור \( k=n \). זה מסיים את ההוכחה הזו.

מילה אחת לסיום. הרושם שעשוי להיווצר מהמשפט האחרון הוא שבכל חבורה סופית \( G \) עם \( \left|G\right|=n \), בהכרח לכל \( k \) שמחלק את \( n \) חייבת להיות תת-חבורה מסדר \( k \). אם זה היה נכון, זה היה סוג של הופכי למשפט לגראנז’ (משפט לגראנז’: “הסדר של תת-חבורה מחלק את סדר החבורה”. ההופכי: “לכל מספר שמחלק את סדר החבורה יש תת-חבורה שזה הסדר שלה). אבל זה לא נכון. ייתכן שעבור \( k \)-ים מסויימים לא תהיינה תת-חבורות מסדר \( k \); זה לא סותר את המשפט שלנו כי ה”מחיר” יהיה קיום של יותר מתת-חבורה אחת עבור סדרים אחרים שמחלקים את \( n \). אבל לא הכל אבוד: ראשית, עבור חבורה אבלית המשפט ההפוך כן נכון; ושנית, גם בחבורה כללית, לכל \( k \) ראשוני שמחלק את \( n \) קיימת תת-חבורה מסדר \( k \) - זה נקרא משפט קושי ונראה אותו שוב בהמשך.

שימו לב כמה רחוק הגענו בפוסט הזה עם הניתוחים שלנו, ואפשר היה להמשיך עם זה כל היום - עוד לא גירדנו את קצה הקרחון. כל זה נולד ממספר מאוד מצומצם של אקסיומות פשוטות. זו עדות מסויימת לכוח של השיטה האקסיומטית “לתפוס” עולמות מורכבים באמצעות תכונות בסיס פשוטות מאוד לכאורה. זה גם מה שהולך לקרות מכאן והלאה.