אז מה זה שדה ואיך הוא יכול להיות סופי?

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

נתחיל מלהבין מה זה בכלל שדה. כבר בכיתות הנמוכות לומדים הילדים על ארבע פעולות החשבון - חיבור, חיסור, כפל וחילוק. איכשהו יוצא שחיבור וכפל הן פעולות נחמדות, וחיסור וחילוק לא. למה אני מתכוון? ובכן, חיבור מקיים שתי תכונות יפות: \( a+b=b+a \), שנקרא “חוק החילוף” (ובעברית קומוטטיביות), ו-\( \left(a+b\right)+c=a+\left(b+c\right) \) שנקרא “חוק הקיבוץ” (ובעברית אסוצאיטיביות). למי שהתכונות הללו נראות לו מובנות מאליהן, שימו לב שהן אינן נכונות עבור חיסור: \( 5-3\ne3-5 \) (לא קשה לראות שהתוצאה תמיד תהיה אותו המספר אבל עם סימן הפוך), ו-\( \left(5-3\right)-2\ne5-\left(3-2\right) \).

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

שימו לב שלמספרים 0 ו-1 יש תכונת “נייטרליות” ביחס לחיבור וכפל: \( a+0=a \) ו-\( a\cdot1=a \) לכל \( a \). זה מעניק לשני המספרים הללו מעמד מיוחד - “אדיש חיבורי” ו”אדיש כפלי”. כעת אפשר להשתמש בהם כדי להגדיר מושג נוסף - אם \( a+b=0 \) אז \( b \) נקרא “הופכי חיבורי” של \( a \) (או לפעמים “נגדי חיבורי”). אנחנו רגילים לתאר יצור כזה בתור \( -a \). באופן דומה, אם \( a\cdot b=1 \) אז \( b \) נקרא “הופכי כפלי” של \( a \), ולרוב מסמנים אותו בתור \( \frac{1}{a} \) או \( a^{-1} \) (אל תחשבו על \( a^{-1} \) בתור חזקה - זה סתם יסבך אתכם לעת עתה - אלא בתור סימון נוח).

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

האופן שבו כל המושגים שתיארתי עד כה משתלבים בא לידי ביטוי בהוכחה הנאה לכך של-0 פשוט לא יכול להיות הופכי כפלי. האבחנה הראשונה היא ש-\( 0+0=0 \) (כי \( 0 \) הוא אדיש חיבורי ולכן \( a+0=a \) תמיד, גם כאשר \( a=0 \) בעצמו). לכן לכל \( a \) מתקיים:

\( a\cdot0=a\cdot\left(0+0\right)=a\cdot0+a\cdot0 \)

כאן השתמשנו בחוק הפילוג. כעת, נחבר לשני האגפים את ההופכי החיבורי של \( a\cdot0 \) (“נפחית \( a\cdot0 \) משני האגפים”) ונקבל \( 0=a\cdot0 \). כלומר, כל דבר כפול 0 שווה אפס, ולכן אם \( a\cdot0=1 \) עבור \( a \) כלשהו, בהכרח \( 0=1 \) ואנחנו יודעים שזה לא כך. אז אין הופכי כפלי ל-0, ולכן גם לא ניתן לחלק באפס (על פי ההגדרה שלנו לחילוק).

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

ובכן, כל הטיעונים הללו טובים ונכונים; אני רק רוצה להמחיש שקיום היצור הזה, “חצי”, הוא לא מובן מאליו, ושהסימון \( \frac{1}{2} \) לכשעצמו עדיין לא מגדיר את המספר. אבל אפשר להגדיר את המספר באופן הכי פורמלי-מתמטי שאפשר, ובראשית ימי הבלוג אף עשיתי זאת. אוסף היצורים מהצורה \( \frac{a}{b} \), כאשר \( b\ne0 \) ו-\( a,b \) שניהם מספרים שלמים, נקרא “המספרים הרציונליים” (או “שברים”, כפי שלפעמים קוראים להם), ומסומנים ב-\( \mathbb{Q} \). המספרים הרציונליים הם קבוצה שבה:

1. מוגדרות פעולות חיבור וכפל (שלכל זוג איברים מהקבוצה מחזירות איבר מהקבוצה).
2. הפעולות הללו מקיימות קומוטטיביות, אסוציאטיביות ודיסטריביוטיביות.
3. קיימים אדיש חיבורי וכפלי ביחס לפעולות החיבור והכפל.
4. לכל איבר קיים הופכי חיבורי, ולכל איבר שונה מאפס קיים הופכי כפלי.

קבוצה שמקיימת את כל הכללים הללו נקראת שדה. מזל טוב - ברגע זה הכרתם את אחד מהאובייקטים החשובים במתמטיקה.

אולי חלקכם בוהים בי עכשיו במבט מוזר. מה הרעיון בלתת שם מפוצץ לשברים? הפואנטה היא שהמספרים הרציונליים רחוקים מלהיות הקבוצה היחידה שמקיימת את ארבעת הכללים שלעיל. ראשית כל ישנם המספרים הממשיים, \( \mathbb{R} \), שגם הם מוכרים לתלמידי תיכון למרות שההגדרה שלהם - ממש לא (כבר דנתי על כך בבלוג בעבר). גם המספרים המרוכבים \( \mathbb{C} \) מקיימים את התכונות הללו וגם הם שדה (אם כי כזה שנראה הזוי לחלוטין לתלמידי תיכון, וגם על זה דיברתי בעבר). ויש דוגמאות לשדות “גדולים יותר” מאשר \( \mathbb{C} \) - למשל, פונקציות רציונליות (פונקציות מהצורה \( \frac{p\left(x\right)}{q\left(x\right)} \) כאשר \( p,q \) הם פולינומים ו-\( q \) איננו פולינום האפס) הן שדה. ויש גם דוגמאות “ביניים”, למשל \( \mathbb{Q}\left(\sqrt{2}\right) \), הקבוצה של כל המספרים מהצורה \( a+b\sqrt{2} \), הם שדה (שימו לב שמכפלה של שני יצורים כאלו היא גם כן מהצורה הזו).

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

הקבוצה \( \mathbb{Z}_{7} \) כוללת את המספרים \( 0,1,2,3,4,5,6 \), ומוגדרות עליה פעולות חיבור וכפל “מודולו 7”. מה זה אומר? חיבור מודולו 7 פירושו שקודם כל מחברים את שני המספרים חיבור רגיל, ואם התוצאה גדולה מ-7, מפחיתים ממנה 7 עד שמקבלים תוצאה שהיא בין 0 ל-6 (או בניסוח אחר, מחלקים ב-7 ולוקחים את השארית). אותו הדבר עם כפל מודולו 7. כך למשל \( 4+4 \) ייתן לנו 1 בחיבור מודולו 7 שכזה; מכיוון שהמשוואה \( 4+4=1 \) נראית קצת מוזרה, כותבים \( 4+4\equiv_{7}1 \) כדי שיהיה ברור שהכוונה כאן היא לחיבור מודולו 7. בדומה, \( 4\cdot5\equiv_{7}6 \) בגלל ש-4 כפול 5 זה 20, וכשמחלקים את 20 ב-7 מקבלים שארית 6.

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

שימו לב שכבר אי אפשר לומר משהו בסגנון “ההופכי החיבורי של 3 הוא \( -3 \)” כי \( -3 \), המספר השלם מינוס 3, הוא חד משמעית לא איבר של \( \mathbb{Z}_{7} \); ל-3 חייב להיות קיים הופכי חיבורי בתוך הקבוצה. אבל הופכי חיבורי כזה קיים: \( 3+4\equiv_{7}0 \), כך ש-4 הוא ההופכי החיבורי מודולו 7 של 3. אפשר לסמן זאת גם כ-\( -3\equiv_{7}4 \). זו נקודה שאני רוצה להבהיר כבר עכשיו - אם לכולם ברור שכרגע אנחנו עוסקים בקבוצה \( \mathbb{Z}_{7} \), אז לכתוב \( -3 \) זה לגיטימי לגמרי בתור סימון אלטרנטיבי ל-4. זאת מכיוון ש-\( -3 \) אינו מציין את “המספר השלם מינוס שלוש” אלא את “ההופכי החיבורי של 3 בתוך \( \mathbb{Z}_{7} \)”. אני משער שחלקכם איבדתם אותי ברגע זה ממש; אם כן וקריאה חוזרת לא עוזרת, לא חשוב לבינתיים. מי שכן הבין וזה הפיל לו אסימון - ובכן, ברוכים הבאים למתמטיקה.

באופן כללי עבור מספר כלשהו ב-\( \mathbb{Z}_{7} \) די קל למצוא את ההופכי החיבורי שלו: ההופכי החיבורי של \( a \) הוא \( 7-a \) (למה?). למצוא הופכי כפלי, לעומת זאת, זה סיפור שונה לגמרי. ההופכי הכפלי של 3 הוא 5, כי \( 3\cdot5=15\equiv_{7}1 \), אבל איך ידעתי שזה דווקא 5 בלי לנסות את כל האפשרויות? זה נובע מתוצאה בסיסית וחשובה בתורת המספרים - האלגוריתם האוקלידי. כאן אני מתחיל לתאר תוצאות שלא אוכיח בשלמותן.

האלגוריתם האוקלידי (המורחב) אומר שבהינתן שני מספרים \( a,n \) שהמספר הגדול ביותר שמחלק את שניהם הוא \( d \) קיימים \( x,y \) שלמים כך ש-\( ax+ny=d \), ולא רק שקיימים, גם קל למצוא אותם (אך לא אציג כרגע את השיטה - רק אציין שקל מאוד לתכנת אותה; עניין של שלוש שורות קוד קצרות). בפרט, אם המספר הגדול ביותר שמחלק את שניהם הוא 1 אז קיימים \( x,y \) כך ש-\( ax+ny=1 \), ואם מסתכלים על המשוואה הזו מודולו \( n \) מקבלים \( ax\equiv_{n}1 \) (כי \( ny\equiv_{n}0 \) שהרי \( ny \) מתחלק ב-\( n \) ללא שארית). בקיצור, מציאת הופכי מתבססת על האלגוריתם האוקלידי המורחב (אבל בינינו? כדי למצוא את ההופכי של 3 מודולו 7 פשוט בדקתי כמה אפשרויות עד שנפלתי על 5).

זה שאנחנו יודעים למצוא הופכיים חיבורי וכפלי זה חשוב מאוד - זה אומר שאנחנו יודעים גם לחסר ולחלק מודולו 7. כדי לחלק ב-3 כופלים בהופכי של 3, כלומר ב-5. במילים אחרות, \( \frac{2}{3} \) ב-\( \mathbb{Z}_{7} \) זה \( 2\cdot5 \) מודולו 7, כלומר 3. רגע, מה? אם מחלקים את 2 ב-3 מקבלים… 3? זה נראה קצת מוזר, אבל שימו לב שאם כופלים את 3 בעצמו מקבלים 2 מודולו 7, כך שאותו הגיון של חילוק שאנחנו מכירים ממספרים “רגילים” (אם \( \frac{a}{b}=c \) זה אומר ש-\( a=b\cdot c \)) נשמר גם כאן; והרי באמירה “אם מחלקים את 9 ב-3 מקבלים 3” לא נראית לנו מוזרה, מה שמוזר בכלל העניין הוא שב-\( \mathbb{Z}_{7} \) אפשר לחלק את 2 ב-3 ועוד לקבל משהו גדול מ-2. אמרתי לכם ששדות סופיים מתנהגים שונה.

בואו נעבור להכללה. אתם בוודאי מנחשים שהמספר 7 בכל הדיון הזה הוא לא קדוש ואפשר לחזור על אותו התעלול גם עבור מספרים אחרים, אבל חיש קל מתברר שאמנם 7 לא קדוש אבל בכל זאת יש קבוצה מאוד מסויימת של מספרים שהיא כן קדושה: המספרים הראשוניים; מספרים שמתחלקים רק ב-1 ובעצמם. הטענה היא כזו: \( \mathbb{Z}_{n} \), קבוצת המספרים מ-0 ועוד \( n-1 \) עם פעולות חיבור וכפל מודולו \( n \), היא שדה אך ורק אם \( n \) ראשוני. עבור \( n \) שאינו ראשוני מה שמשתבש הוא קיום הופכי כפלי: קיימים מספרים שונים מאפס שאין להם הופכי כפלי. למשל, ב-\( \mathbb{Z}_{8} \), לא קיים ל-2 הופכי כפלי. מדוע? כי נניח ש-\( a\cdot2\equiv_{8}1 \), אז בואו נכפול את שני אגפי המשוואה ב-4. נקבל \( a\cdot8\equiv_{8}4 \), אבל אגף שמאל שווה ל-0 מודולו 8, כך שקיבלנו \( 0\equiv_{8}4 \) וזה ודאי לא נכון. תעלול דומה אפשר לעשות לכל \( n \) שאינו ראשוני. אם לעומת זאת \( n \) ראשוני אז המספר הגדול ביותר שמחלק אותו ואת \( a \) לכל \( a \) שהוא בין 1 ו-\( n-1 \) יהיה 1, ואז האלגוריתם האוקלידי יפעל עליהם וינפיק \( x \) כך ש-\( ax\equiv_{n}1 \). לכן \( \mathbb{Z}_{n} \) יהיה שדה (עוד צריך לבדוק ששאר התכונות מתקיימות). נהוג להשתמש באות \( p \) (מלשון Prime) כדי לתאר מספרים ראשוניים, ולכן בדרך כלל מסמנים את השדות הללו ב-\( \mathbb{Z}_{p} \). כפי שודאי כבר שמתם לב, אלו הם שדות סופיים; ב-\( \mathbb{Z}_{p} \) ישנם בדיוק \( p \) איברים.

כעת אני רוצה להכניס מושג חדש לתמונה: מציין של שדה (Characteristic). אמרנו שבכל שדה צריכים להיות 0 ו-1 ופעולת חיבור, אז הנה שאלה שמערבת את כולם: מה המספר הקטן ביותר של פעמים שצריך לחבר את 1 לעצמו כדי לקבל 0?

השאלה נראית מטופשת במבט ראשון. הרי \( 1+1=2 \), ו-\( 1+1+1=3 \) וכן הלאה ובחיים לא נגיע לאפס! אבל מצד שני, ב-\( \mathbb{Z}_{7} \) אם נחבר את 1 לעצמו שבע פעמים, נקבל 0 על פי כללי החיבור של השדה, כך שהשאלה לא מופרכת כפי שהיא אולי נראית במבט ראשון. מה שנכון הוא שלפעמים התשובה עליה היא פשוט “לא משנה כמה נחבר את 1 לעצמו, לא נקבל 0”, כמו שקורה ברציונליים, בממשיים ובמרוכבים. במקרה כזה אומרים שהשדה הוא בעל מציין 0. למה לא אינסוף? עניין הגדרתי נטו, לדעתי, אבל אולי קצת יותר נכון מבחינה רעיונית כי ברציונליים, כשמחברים את 1 לעצמו, ואפילו נחבר אותו “אינסוף” פעמים מה שזה לא אומר, לא נתקרב בכלל ל-0. אם כן, שדה ממציין 0 הוא בהכרח אינסופי כי הוא כולל את כל המספרים הטבעיים בתוכו; ולמעשה, בגלל שהוא שדה, הוא כולל גם את ההופכיים החיבוריים והכפליים שלהם, וזה כבר \( \mathbb{Q} \). הרי לכם משפט יפה: כל שדה ממציין 0 כולל בתוכו עותק של \( \mathbb{Q} \). זה מצביע על החשיבות הגדולה של הרציונליים - הם ה”בסיס” לכל השדות ממציין 0.

כעת נניח שיש לשדה כלשהו מציין \( n \). אז אני טוען ש-\( n \) חייב להיות ראשוני, כי אם \( n=a\cdot b \) כאשר \( a,b \) טבעיים קטנים ממנו אך גדולים מאפס, כלומר הם בעצמם איברים של השדה אז בתוך השדה \( a\cdot b=0 \), ואם \( b \) שונה מאפס בעצמו אפשר לחלק בו ולקבל ש-\( a=0 \). שוויון כזה לאפס עבור מספר טבעי \( a \) הגדול מאפס מצביע על כך שהמציין לא יכול להיות \( n \), כי \( n \) גדול מדי - הנה, אם מחברים את 1 לעצמו \( a \) פעמים גם כן מקבלים 0.

יפה, אז הבה ונדבר על שדה סופי כלשהו. נקרא לו \( F \). אותו \( F \) חייב להיות בעל מציין שונה מאפס אחרת לא היה סופי; נניח שהמציין שלו הוא \( p \) (כאמור, \( p \) חייב להיות מספר ראשוני). מכיוון ש-\( F \) כולל את 0 ו-1 הוא כולל את כל המספרים \( 0,1,2,\dots,p-1 \), וכללי החיבור והכפל של המספרים הללו מתנהגים בדיוק כמו חיבור וכפל מודולו \( p \), כי על כל שני מספרים כאלו אפשר לחשוב פשוט בתור סכומים של 1. למשל:

\( 2\cdot2=\left(1+1\right)\cdot\left(1+1\right)=1\cdot1+1\cdot1+1\cdot1+1\cdot1=1+1+1+1 \)

המסקנה מכך (ואני יודע שקצת נפנפתי פה בידיים) היא ש-\( F \) מכיל בתוכו עותק של \( \mathbb{Z}_{p} \). כלומר, באותו אופן שבו \( \mathbb{Q} \) הוא שדה הבסיס של כל שדה ממציין 0, \( \mathbb{Z}_{p} \) הוא שדה הבסיס של כל שדה ממציין \( p \) (למעלה דיברתי על שדה סופי, אבל זה נכון גם לשדות אינסופיים ממציין \( p \) - יש כאלו - ודרשתי את הסופיות למעלה רק כדי להכריח את השדה להיות ממציין שונה מאפס).

יפה, אז התיידדנו קצת עם המושג הכללי של שדה, ראינו שקיימים שדות סופיים והבנו מקצת מהתכונות המוזרות שלהן. בפוסט הבא נטפל באתגר קצת יותר שאפתני - להבין איך נראים כל השדות הסופיים. הנה הקדימון: אנחנו הולכים לראות שלכל ראשוני \( p \) ולכל מספר טבעי \( n \) קיים שדה סופי עם בדיוק \( p^{n} \) איברים, ויש בדיוק שדה יחיד כזה, ואין שדות סופיים אחרים. זו, לטעמי, היא אחת מהתוצאות היפות ביותר במתמטיקה. טוב, במתמטיקה שהיא פשוטה מספיק כדי שאדע אותה.