שדות סופיים

בקצרה: שדה סופי הוא שדה עם מספר סופי של איברים. הדוגמה המרכזית שנלמדת בקורס היא קבוצת השאריות [math]\displaystyle{ \mathbb{Z}_n=\{0,1,\dots,n-1\} }[/math] עם חיבור וכפל מודולו n. מתברר ש[math]\displaystyle{ \mathbb{Z}_n }[/math] היא שדה אם ורק אם n הוא מספר ראשוני - עבור n שאינו ראשוני קיימים בה איברים שונים מאפס שמכפלתם אפס, בסתירה לתכונה שמתקיימת בכל שדה.

לאחר שהגדרנו שדה באופן אקסיומטי (קבוצה עם חיבור וכפל שמקיימים סגירות, קומוטטיביות, אסוציאטיביות, איברים נייטרליים, נגדיים, הופכיים ופילוג - ראו שדה), עולה השאלה האם קיימים שדות "סופיים", כלומר עם מספר סופי של איברים, ולא רק השדות האינסופיים [math]\displaystyle{ \mathbb{Q},\mathbb{R},\mathbb{C} }[/math]. בפרק זה בונים משפחה טבעית של מועמדים - קבוצות השאריות מודולו n - ובודקים מתי הן אכן מקיימות את אקסיומות השדה. המבנים הללו ישמשו בהמשך הקורס כדוגמאות לשדות שמעליהם אפשר להגדיר מרחבים וקטוריים ומטריצות בדיוק כמו מעל [math]\displaystyle{ \mathbb{R} }[/math].

הגדרה

יהי [math]\displaystyle{ n\in\mathbb{N} }[/math]. קבוצת השאריות מודולו n היא הקבוצה

[math]\displaystyle{ \mathbb{Z}_n=\{0,1,2,\dots,n-1\} }[/math]

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

מגדירים על [math]\displaystyle{ \mathbb{Z}_n }[/math] שתי פעולות, חיבור מודולו n וכפל מודולו n:

[math]\displaystyle{ a+b \pmod{n} := }[/math] שארית החלוקה של [math]\displaystyle{ a+b }[/math] (החיבור הרגיל) ב-n.

[math]\displaystyle{ a\cdot b \pmod{n} := }[/math] שארית החלוקה של [math]\displaystyle{ a\cdot b }[/math] (הכפל הרגיל) ב-n.

כלומר: מבצעים את הפעולה הרגילה על המספרים הטבעיים, ולוקחים את שארית החלוקה ב-n. באופן זה התוצאה תמיד חוזרת להיות איבר של [math]\displaystyle{ \mathbb{Z}_n }[/math] (סגירות).

משפטים ותכונות

(תכונה כללית בכל שדה) יהי שדה [math]\displaystyle{ \mathbb{F} }[/math], אזי לכל [math]\displaystyle{ a,b\in\mathbb{F} }[/math] מתקיים כי [math]\displaystyle{ a\cdot b=0_{\mathbb{F}} }[/math] אם ורק אם [math]\displaystyle{ a=0_{\mathbb{F}} }[/math] או [math]\displaystyle{ b=0_{\mathbb{F}} }[/math] (אין "מחלקי אפס" בשדה). הוכחה בהרצאה (ראו שדה).

משפט: אם n אינו ראשוני, אז [math]\displaystyle{ \mathbb{Z}_n }[/math] (עם החיבור והכפל מודולו n) אינה שדה.

רעיון ההוכחה: אם [math]\displaystyle{ n>1 }[/math] אינו ראשוני אפשר לכתוב [math]\displaystyle{ n=a\cdot b }[/math] כאשר [math]\displaystyle{ 1<a,b<n }[/math] (ועבור [math]\displaystyle{ n=1 }[/math] הקבוצה [math]\displaystyle{ \mathbb{Z}_1=\{0\} }[/math] אינה שדה, כי בשדה [math]\displaystyle{ 0\neq1 }[/math]), כך ש-[math]\displaystyle{ a,b\neq 0 }[/math] ב-[math]\displaystyle{ \mathbb{Z}_n }[/math]. אבל [math]\displaystyle{ a\cdot b=n }[/math], ושארית החלוקה של n ב-n היא 0, כלומר [math]\displaystyle{ a\cdot b=0 }[/math] ב-[math]\displaystyle{ \mathbb{Z}_n }[/math] למרות ש[math]\displaystyle{ a\neq0 }[/math] וגם [math]\displaystyle{ b\neq0 }[/math]. זו סתירה לתכונה הכללית שהוכחה לעיל עבור שדות (מכפלת שני איברים שונים מאפס לא יכולה להיות אפס בשדה), ולכן [math]\displaystyle{ \mathbb{Z}_n }[/math] אינה שדה.

משפט: אם p ראשוני, אז [math]\displaystyle{ \mathbb{Z}_p }[/math] (עם החיבור והכפל מודולו p) כן מקיימת את כל תכונות השדה.

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

שיטה / איך מחשבים

חיבור/כפל מודולו n: מבצעים את הפעולה הרגילה על שני המספרים, ואז מחלקים ב-n ולוקחים את השארית.
נגדי של איבר: הנגדי של [math]\displaystyle{ a\in\mathbb{Z}_n }[/math] (עבור [math]\displaystyle{ a\neq0 }[/math]) הוא [math]\displaystyle{ n-a }[/math], כי [math]\displaystyle{ a+(n-a)=n\equiv 0\pmod n }[/math].
הופכי של איבר (כאשר [math]\displaystyle{ \mathbb{Z}_n }[/math] שדה, כלומר n ראשוני): כדי למצוא את ההופכי של [math]\displaystyle{ a\neq0 }[/math], בודקים בזה אחר זה (שכן הקבוצה סופית) את [math]\displaystyle{ a\cdot 1,\ a\cdot 2,\ \dots,\ a\cdot (n-1) }[/math] מודולו n, עד שמתקבל 1. האיבר שנתן 1 הוא ההופכי [math]\displaystyle{ a^{-1} }[/math].
בדיקה ש-[math]\displaystyle{ \mathbb{Z}_n }[/math] אינה שדה: מספיק למצוא זוג [math]\displaystyle{ a,b\neq0 }[/math] עם [math]\displaystyle{ a\cdot b\equiv 0\pmod n }[/math] (מחלקי אפס) - זה קורה תמיד כאשר n אינו ראשוני, לפי המשפט לעיל.

דוגמאות

דוגמה 1 - חיבור וכפל ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math]:

נחשב [math]\displaystyle{ 3\cdot4 }[/math] ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math]: קודם כפל רגיל - [math]\displaystyle{ 3\cdot4=12 }[/math], ואז שארית החלוקה ב-5 - מתקבל 2. כלומר [math]\displaystyle{ 3\cdot4\equiv2\pmod5 }[/math].

נחשב גם [math]\displaystyle{ 3+4 }[/math] ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math]: [math]\displaystyle{ 3+4=7 }[/math], ושארית החלוקה ב-5 היא גם כן 2, כלומר [math]\displaystyle{ 3+4\equiv2\pmod5 }[/math]. (זהו צירוף מקרים של הדוגמה הספציפית הזו, ולא כלל כללי - החיבור והכפל הם פעולות שונות).

דוגמה 2 - נגדיים ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math]:

נחשב [math]\displaystyle{ 2+3 }[/math]: במספרים רגילים זה 5, ושארית החלוקה שלו ב-5 היא 0. כלומר [math]\displaystyle{ 2+3\equiv0\pmod5 }[/math], ולכן 2 ו-3 הם נגדיים זה של זה ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math]: [math]\displaystyle{ -2=3 }[/math] וגם [math]\displaystyle{ -3=2 }[/math].

דוגמה 3 - מדוע [math]\displaystyle{ \mathbb{Z}_{12} }[/math] אינה שדה:

נבדוק את 3 ו-4 ב-[math]\displaystyle{ \mathbb{Z}_{12} }[/math]. במספרים רגילים [math]\displaystyle{ 3\cdot4=12 }[/math], ושארית החלוקה ב-12 היא 0. כלומר [math]\displaystyle{ 3\cdot4\equiv0\pmod{12} }[/math], למרות ש-[math]\displaystyle{ 3\neq0 }[/math] וגם [math]\displaystyle{ 4\neq0 }[/math]. בכל שדה מכפלה של שני איברים שונים מאפס לא יכולה להיות אפס - ולכן [math]\displaystyle{ \mathbb{Z}_{12} }[/math] אינה שדה. (אכן, [math]\displaystyle{ 12=3\cdot4 }[/math] אינו ראשוני, בהתאם למשפט לעיל).

דוגמה 4 - מציאת הופכי ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math]:

נמצא את ההופכי של 3 ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math] (5 ראשוני, אז אמור להיות הופכי). בודקים: [math]\displaystyle{ 3\cdot1=3 }[/math], [math]\displaystyle{ 3\cdot2=6\equiv1\pmod5 }[/math] - מצאנו! לכן [math]\displaystyle{ 3^{-1}=2 }[/math] ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math], ואפשר לוודא: [math]\displaystyle{ 3\cdot2=6\equiv1\pmod5 }[/math].

שאלות תרגול

שאלה 1: חשבו ב-[math]\displaystyle{ \mathbb{Z}_7 }[/math] את [math]\displaystyle{ 5+6 }[/math] ואת [math]\displaystyle{ 5\cdot6 }[/math].

פתרון: [math]\displaystyle{ 5+6=11 }[/math], שארית החלוקה ב-7 היא 4, כלומר [math]\displaystyle{ 5+6\equiv4\pmod7 }[/math]. [math]\displaystyle{ 5\cdot6=30 }[/math], ו-[math]\displaystyle{ 30=4\cdot7+2 }[/math], כלומר [math]\displaystyle{ 5\cdot6\equiv2\pmod7 }[/math].

שאלה 2: האם [math]\displaystyle{ \mathbb{Z}_9 }[/math] שדה? אם לא, הציגו שני איברים שונים מאפס שמכפלתם אפס.

פתרון: 9 אינו ראשוני ([math]\displaystyle{ 9=3\cdot3 }[/math]), ולכן לפי המשפט [math]\displaystyle{ \mathbb{Z}_9 }[/math] אינה שדה. אכן, [math]\displaystyle{ 3\cdot3=9\equiv0\pmod9 }[/math] למרות ש-[math]\displaystyle{ 3\neq0 }[/math], כלומר 3 הוא מחלק אפס של עצמו ב-[math]\displaystyle{ \mathbb{Z}_9 }[/math].

שאלה 3: ב-[math]\displaystyle{ \mathbb{Z}_{11} }[/math] (11 ראשוני): מצאו את הנגדי ואת ההופכי של 4.

פתרון: הנגדי: [math]\displaystyle{ -4=11-4=7 }[/math], ואכן [math]\displaystyle{ 4+7=11\equiv0\pmod{11} }[/math]. ההופכי: בודקים [math]\displaystyle{ 4\cdot1=4,\ 4\cdot2=8,\ 4\cdot3=12\equiv1\pmod{11} }[/math] - נמצא! לכן [math]\displaystyle{ 4^{-1}=3 }[/math] ב-[math]\displaystyle{ \mathbb{Z}_{11} }[/math].

שאלה 4: הראו של-[math]\displaystyle{ \mathbb{Z}_6 }[/math] יש מחלקי אפס, ולכן היא אינה שדה.

פתרון: ניקח [math]\displaystyle{ 2,3\in\mathbb{Z}_6 }[/math], שניהם שונים מאפס. [math]\displaystyle{ 2\cdot3=6\equiv0\pmod6 }[/math]. מכיוון שבשדה מכפלת שני איברים שונים מאפס לא יכולה להיות אפס, [math]\displaystyle{ \mathbb{Z}_6 }[/math] אינה שדה (בהתאם לכך ש-[math]\displaystyle{ 6=2\cdot3 }[/math] אינו ראשוני).

שאלה 5: ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math], מצאו את ההופכי של כל אחד מהאיברים [math]\displaystyle{ 1,2,3,4 }[/math].

פתרון: [math]\displaystyle{ 1^{-1}=1 }[/math] (כי [math]\displaystyle{ 1\cdot1=1 }[/math]). [math]\displaystyle{ 2^{-1}=3 }[/math] (כי [math]\displaystyle{ 2\cdot3=6\equiv1\pmod5 }[/math]). [math]\displaystyle{ 3^{-1}=2 }[/math] (מדוגמה 4 לעיל). [math]\displaystyle{ 4^{-1}=4 }[/math] (כי [math]\displaystyle{ 4\cdot4=16\equiv1\pmod5 }[/math]).

טעויות נפוצות

לשכוח לצמצם את התוצאה חזרה לתחום [math]\displaystyle{ \{0,1,\dots,n-1\} }[/math] - למשל לכתוב שהתוצאה היא 12 בתוך [math]\displaystyle{ \mathbb{Z}_5 }[/math] במקום לחלק ב-5 ולקחת שארית.
לחשוב בטעות ש-[math]\displaystyle{ \mathbb{Z}_n }[/math] היא שדה עבור כל n, ולנסות "לחלק" באיבר שונה מאפס גם כש-n אינו ראשוני (למשל לצמצם גורם משותף כמו בשדות הרגילים) - כש-n אינו ראשוני מותר לחלק רק באיברים הזרים ל-n (למשל אי אפשר לחלק ב-2 ב-[math]\displaystyle{ \mathbb{Z}_6 }[/math]).
לבלבל בין נגדי ([math]\displaystyle{ -a=n-a }[/math], קיים תמיד) לבין הופכי ([math]\displaystyle{ a^{-1} }[/math], קיים לכל [math]\displaystyle{ a\neq0 }[/math] רק כש-n ראשוני; כש-n פריק יש הופכי רק לאיברים הזרים ל-n, למשל [math]\displaystyle{ 5\cdot5\equiv1\pmod6 }[/math] אבל ל-2 אין הופכי ב-[math]\displaystyle{ \mathbb{Z}_6 }[/math]).
להניח שאם בדוגמה מסוימת [math]\displaystyle{ a+b }[/math] ו-[math]\displaystyle{ a\cdot b }[/math] יצאו שווים (כמו 3,4 ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math]), זהו כלל כללי - זהו רק צירוף מקרים חד-פעמי.
לשכוח שכדי להראות ש-[math]\displaystyle{ \mathbb{Z}_n }[/math] אינה שדה מספיק דוגמה נגדית אחת (זוג מחלקי אפס), אבל כדי להראות שהיא כן שדה יש לבדוק/להוכיח זאת עבור כל האיברים, לא רק להראות דוגמה אחת שעובדת.

שאלות ממבחנים

מבחן מועד א' קיץ תשעג עם פתרונות, שאלה 4 — מבחן (הערכים האפשריים ל-det A כאשר A^{-1}=A^2, מעל R, מעל C ומעל Z7)
מבחן מועד א' קיץ תשעג עם פתרונות, שאלה 7 — מבחן (נכון/לא נכון: קיימת מערכת הומוגנית מעל שדה כלשהו עם בדיוק 6 פתרונות)
בוחן קיץ תשע"ג, שאלה 1 — מבחן (מספר הפתרונות A למשוואת המטריצות [[1,2],[2,4]]A=[[2,2,3],[4,4,6]] מעל השדה הסופי Z7)
בוחן 1 חורף תשע"ג, שאלה 1 (כולל בונוס) — מבחן · פתרון (מציאת ערכי הפרמטר a שעבורם למערכת פתרון יחיד/אין פתרון/אינסוף פתרונות מעל R, ובבונוס פתרון מעל Z2)
מבחן מועד א' קיץ תשע"ב, שאלה חלק ב' - שאלה 2 — מבחן (מערכת משוואות עם פרמטר a מעל השדה הסופי Z5 ומספר ערכי a עבורם יש בדיוק 5 פתרונות)
מבחן מועד א' קיץ תשע"ב, שאלה חלק ב' - שאלה 8 — מבחן (מספר ההעתקות הלינאריות המקיימות תנאים נתונים על תמונות וקטורים תלויים לינארית מעל Zp, כתלות ב-p)
מועד ב' חורף תשעב, שאלה 3א — מבחן · פתרון (ספירת מספר ההעתקות הלינאריות T:F^n→F^n מעל שדה סופי F=Z_p (p ראשוני))
מבחן דמה 1 קיץ תשעא, שאלה 5א — מבחן (מספר הפתרונות של Ax=b מעל ℤ₃ עבור מטריצה עם פרמטר a, לכל ערך של a)
מועד א' קיץ תשעא, שאלה 5ב — מבחן · פתרון (פתרון משוואה פולינומיאלית מדרגה רביעית מעל השדה הסופי Z7 על ידי פירוק לגורמים)
מועד א' חורף תשעא + פתרון, שאלה שאלה 3ב — מבחן (ספירת תתי-המרחבים W המשלימים לסכום ישר עם U (dimU=1) במרחב ממימד 2 מעל Z2)
בוחן דמה קיץ תשע"א, שאלה 2ב — מבחן (מספר הפתרונות למערכת Ax=b מעל Z3 עבור כל ערכי הפרמטרים a,t)
בוחן קיץ תשע"א + פתרון, שאלה 4 — מבחן (פתרון מערכת משוואות ליניארית עם פרמטר a מעל השדה Z5, וקביעת מספר הפתרונות (אין/יחיד/אינסוף) לפי ערכי a)
פתרון מועד א' קיץ תשע, שאלה 4 — מבחן (מסקנות הכרחיות ממערכת הומוגנית Ax=0 מעל ℤ₅ עם פתרון לא טריוויאלי (קיום/יחידות/אינסוף פתרונות ל-Ax=b, ודרגת A))
פתרון מועד ב' קיץ תשע, שאלה 8 — מבחן (טענות נכון/לא נכון על העתקות לינאריות בין מרחבים מעל שדות סופיים, המוגדרות ע"י תמונות וקטורים נתונים)

הרשימה המלאה, לפי מבחן ולפי נושא: אלגברה לינארית 1/אינדקס שאלות.

סרטונים

הגדרת קבוצת השאריות [math]\displaystyle{ \mathbb{Z}_n }[/math] וחיבור/כפל מודולו n, דוגמאות חישוב ב-[math]\displaystyle{ \mathbb{Z}_5 }[/math], והוכחה (באמצעות דוגמה ב-[math]\displaystyle{ \mathbb{Z}_{12} }[/math]) שאם n אינו ראשוני אז [math]\displaystyle{ \mathbb{Z}_n }[/math] אינה שדה - לעומת הטענה (ללא הוכחה בסרטון זה) שעבור p ראשוני, [math]\displaystyle{ \mathbb{Z}_p }[/math] כן שדה.

להרחבה

שדה סופי - קיום ויחידות של שדה סופי מכל סדר [math]\displaystyle{ p^n }[/math] (ברמת הקורס מבנים אלגבריים)