שיחה:89-214 סמסטר א' תשעב/תקצירים: הבדלים בין גרסאות בדף

גרסה אחרונה מ־18:03, 1 בפברואר 2012

הנחיות

ראשית, קיראו את ההנחיות בעמוד הראשי. דף זה מיועד לשאלות בנוגע לתרגילים - כולל קושיות ותהיות מתמטיות, וגם סוגיות טכניות (לפחות עד שנגְלה את אלה לדף אחר). אנא אל תפתחו כותרות ראשיות שלא לצורך. עוזי ו. 19:28, 7 באוקטובר 2010 (IST)

שעור ראשון

אני מבקש להבהיר את נושא המחלק המשותף המקסימלי, שהשתבש קמעה במהלך השעור.

נניח ש-a,b הם שני מספרים (שלמים). הגדרנו שני מושגים *דומים אך שונים*:

d הוא מחלק משותף מקסימלי אם המחלקים שלו הם בדיוק המחלקים המשותפים ל-a ול-b (בניסוח אחר, [math]\displaystyle{ \ x |d \leftrightarrow d|a,b }[/math]).
d הוא מחלק משותף גדול ביותר אם הוא הגדול ביותר (לגבי יחס הסדר הרגיל) בין כל המחלקים המשותפים (סימנו ב-D את קבוצת המחלקים המשותפים, כך ש-[math]\displaystyle{ \ d = \max D }[/math]).

ההגדרה הראשונה אינה תלויה בסימן (כלומר, אם d מקיים אותה, גם d- מקיים אותה). בהגדרה השניה d תמיד חיובי.

אם מספר חיובי מקיים את ההגדרה הראשונה, אז הוא בוודאי מקיים את ההגדרה השניה (משום שכל מחלק משותף של a ו-b מחלק אותו). ההגדרה הראשונה "נקיה" יותר, אבל לשניה יש יתרון ברור: קל מאד להוכיח שהמחלק המשותף הגדול ביותר תמיד קיים (אלא אם a=b=0). ובמברק: "מקסימלי הוא תמיד גדול-ביותר; הצרה היא שלא ברור שיש מקסימלי".

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

משפט. תמיד אפשר להציג את המחלק המשותף הגדול ביותר של a,b כצירוף שלם שלהם. (הוכחנו בכתה באמצעות השוואה בין קבוצת הצירופים השלמים החיוביים לבין קבוצת המחלקים המשותפים).

מסקנה (שלא ראינו בכתה). המחלק המשותף המקסימלי תמיד קיים.

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

סיכום. מספר חיובי הוא מחלק משותף מקסימלי של a ו-b אם ורק אם הוא מחלק משותף גדול ביותר שלהם. את המחלק המשותף המשותף הזה, מסמנים [math]\displaystyle{ \ d = (a,b) }[/math]. עוזי ו. 17:06, 1 בנובמבר 2011 (IST)

בניית שדה מסדר q

בעיה. נניח ש- [math]\displaystyle{ \ q = p^n }[/math] היא חזקה של ראשוני p. בנה שדה בן q אברים.

הערה 1. הפתרון התאורטי שהוצג בשעור פשוט להפליא: בחר שדה המפצל את הפולינום [math]\displaystyle{ \ x^q-x }[/math] מעל השדה [math]\displaystyle{ \ \mathbb{Z}_p }[/math]; אוסף השורשים של הפולינום בשדה זה הוא שדה מסדר q. עם זאת, בניית שדה מפצל באופן מפורש דורשת עבודה רבה, ורצוי להכיר גם בניות מפורשות יותר.

הערה 2. הראינו בכתה שאם f פולינום אי-פריק ממעלה n מעל [math]\displaystyle{ \ \mathbb{Z}_p }[/math], אז "חוג המנה" [math]\displaystyle{ \ \mathbb{Z}_p[x]/\mathbb{Z}_p[x]f(x) }[/math], הוא שדה מסדר q. האברים של חוג המנה הזה הם הקוסטים של כל הפולינומים ממעלה קטנה מ-n. כלומר, צירופים ליניאריים של [math]\displaystyle{ \ \bar{1}, \bar{x}, \bar{x}^2, \dots, \bar{x}^{n-1} }[/math], כאשר [math]\displaystyle{ \ \bar{x} }[/math] הוא סימון מקוצר לקוסט [math]\displaystyle{ \ x+\mathbb{Z}_p[x]f(x) }[/math]. בין הקוסטים האלה יש פעולות של חיבור וכפל מודולו f, המבוצעות על-ידי חיבור וכפל הנציגים, ומעבר לשארית בחלוקה ל-f במקרה הצורך. זוהי, אם כך, בניה מפורשת להפליא: ברגע שנדע מהו הפולינום f, נוכל לכתוב את לוח החיבור והכפל של השדה מסדר q בקלות רבה.

הערה 3. אמרנו (ולא הוכחנו) שיש שדה יחיד מכל סדר אפשרי q. מכאן שאם f,g שניהם פולינומים אי-פריקים ממעלה n מעל השדה מסדר p, אז השדות [math]\displaystyle{ \ \mathbb{Z}_p[x]/\mathbb{Z}_p[x]f(x) }[/math] ו- [math]\displaystyle{ \ \mathbb{Z}_p[x]/\mathbb{Z}_p[x]g(x) }[/math] איזומורפיים (כלומר, יש התאמה חד-חד-ערכית ועל ביניהם, השומרת על החיבור והכפל). שימו לב שהעתקה זו *אינה* מעבירה את הקוסט של x אל הקוסט של x.

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

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

דוגמא. נמצא את כל הפולינומים האי-פריקים ממעלה 3 מעל השדה בגודל 2. יש רק שני פולינומים ממעלה 1, ארבעה ממעלה 2, ושמונה ממעלה 3. לאחר שמוחקים מרשימת שמונה הפולינומים ממעלה 3 את ארבע הכפולות של x ואת ארבע הכפולות של x+1, נותרים בדיוק שניים (מדוע): [math]\displaystyle{ \ x^3+x+1, x^3+x^2+1 }[/math]. לכן [math]\displaystyle{ \ \mathbb{Z}_2[x]/\mathbb{Z}_2[x](x^3+x+1) }[/math] הוא שדה מסדר 8. (כדי לבדוק שהבנתם את השדה, חשבו למשל את כל החזקות של x).

@@ שורה 13: / שורה 13: @@
 ההגדרה הראשונה אינה תלויה בסימן (כלומר, אם d מקיים אותה, גם d- מקיים אותה). בהגדרה השניה d תמיד חיובי.
-אם מספר חיובי מקיים את ההגדרה הראשונה, אז הוא בוודאי מקיים את ההגדרה השניה (משום שכל מחלק משותף של a ו-b מחלק אותו). ההגדרה הראשונה "נקיה" יותר, אבל לשניה יש יתרון ברור: קל מאד להוכיח שהמחלק המשותף הגדול ביותר תמיד קיים (אלא אם a=b=0).
+אם מספר חיובי מקיים את ההגדרה הראשונה, אז הוא בוודאי מקיים את ההגדרה השניה (משום שכל מחלק משותף של a ו-b מחלק אותו). ההגדרה הראשונה "נקיה" יותר, אבל לשניה יש יתרון ברור: קל מאד להוכיח שהמחלק המשותף הגדול ביותר תמיד קיים (אלא אם a=b=0). ובמברק: "מקסימלי הוא תמיד גדול-ביותר; הצרה היא שלא ברור שיש מקסימלי".
 בשעור הצגתי את ההגדרה הראשונה, ועצרתי באמצע ההוכחה שהמחלק המשותף המקסימלי קיים. ומסיבה טובה: זו טענה שלא ניתן להוכיח בלי המשפט על צירופים שלמים. הרי המשפט והוכחת קיום המחלק המשותף המקסימלי.
@@ שורה 24: / שורה 24: @@
 '''סיכום'''. מספר חיובי הוא מחלק משותף מקסימלי של a ו-b אם ורק אם הוא מחלק משותף גדול ביותר שלהם. את המחלק המשותף המשותף הזה, מסמנים <math>\ d = (a,b)</math>. [[משתמש:עוזי ו.|עוזי ו.]] 17:06, 1 בנובמבר 2011 (IST)
+== בניית שדה מסדר q ==
+* '''בעיה'''. נניח ש- <math>\ q = p^n</math> היא חזקה של ראשוני p. בנה שדה בן q אברים.
+'''הערה 1'''. הפתרון התאורטי שהוצג בשעור פשוט להפליא: בחר שדה המפצל את הפולינום <math>\ x^q-x</math> מעל השדה <math>\ \mathbb{Z}_p</math>; אוסף השורשים של הפולינום בשדה זה הוא שדה מסדר q. עם זאת, בניית שדה מפצל באופן מפורש דורשת עבודה רבה, ורצוי להכיר גם בניות מפורשות יותר.
+'''הערה 2'''. הראינו בכתה שאם f פולינום אי-פריק ממעלה n מעל <math>\ \mathbb{Z}_p</math>, אז "חוג המנה" <math>\ \mathbb{Z}_p[x]/\mathbb{Z}_p[x]f(x)</math>, הוא שדה מסדר q. האברים של חוג המנה הזה הם הקוסטים של כל הפולינומים ממעלה קטנה מ-n. כלומר, צירופים ליניאריים של <math>\ \bar{1}, \bar{x}, \bar{x}^2, \dots, \bar{x}^{n-1}</math>, כאשר <math>\ \bar{x}</math> הוא סימון מקוצר לקוסט <math>\ x+\mathbb{Z}_p[x]f(x)</math>. בין הקוסטים האלה יש פעולות של חיבור וכפל מודולו f, המבוצעות על-ידי חיבור וכפל הנציגים, ומעבר לשארית בחלוקה ל-f במקרה הצורך. זוהי, אם כך, בניה מפורשת להפליא: ברגע שנדע מהו הפולינום f, נוכל לכתוב את לוח החיבור והכפל של השדה מסדר q בקלות רבה.
+'''הערה 3'''. אמרנו (ולא הוכחנו) שיש שדה יחיד מכל סדר אפשרי q. מכאן שאם f,g שניהם פולינומים אי-פריקים ממעלה n מעל השדה מסדר p, אז השדות <math>\ \mathbb{Z}_p[x]/\mathbb{Z}_p[x]f(x)</math> ו- <math>\ \mathbb{Z}_p[x]/\mathbb{Z}_p[x]g(x)</math> איזומורפיים (כלומר, יש התאמה חד-חד-ערכית ועל ביניהם, השומרת על החיבור והכפל). שימו לב שהעתקה זו *אינה* מעבירה את הקוסט של x אל הקוסט של x.
+'''למה''' (שלא הוכחנו): מעל כל שדה סופי, קיים פולינום אי-פריק מכל מעלה.
+הלמה אינה *מספקת* פולינום כזה, אבל היא מבטיחה שהוא קיים - וכך יוצאים למסע החיפושים בלב קל ובוטח.
+'''פתרון'''. כדי למצוא שדה מסדר q, כל שעלינו לעשות בעקבות הערה 2 (והלמה) הוא למצוא פולינום אי-פריק ממעלה n מעל השדה מסדר p. אפשר למצוא פולינום כזה בדרכים שונות. למשל, וריאציה על "הנפה של ארטוסתנס" - לאחר שעורכים רשימה של כל הפולינומים ממעלה עד n, פוסלים בזה אחר זה את כל הכפולות של הפולינומים מן הרשימה. פולינום שלא נמחק, חזקה עליו שיהיה אי-פריק. הלמה מבטיחה שתהליך זה יושלם בהצלחה.
+'''דוגמא'''. נמצא את כל הפולינומים האי-פריקים ממעלה 3 מעל השדה בגודל 2. יש רק שני פולינומים ממעלה 1, ארבעה ממעלה 2, ושמונה ממעלה 3. לאחר שמוחקים מרשימת שמונה הפולינומים ממעלה 3 את ארבע הכפולות של x ואת ארבע הכפולות של x+1, נותרים בדיוק שניים (מדוע): <math>\ x^3+x+1, x^3+x^2+1</math>. לכן <math>\ \mathbb{Z}_2[x]/\mathbb{Z}_2[x](x^3+x+1)</math> הוא שדה מסדר 8. (כדי לבדוק שהבנתם את השדה, חשבו למשל את כל החזקות של x).