חוג אוקלידי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

הגדרה[עריכת קוד מקור | עריכה]

תחום שלמות D הוא חוג אוקלידי, אם קיימת פונקציה המחזירה מספרים טבעיים, \ d : D-\{0\}\rightarrow \mathbb{N}, המקיימת את הדרישה \ d(a)\leq d(ab) לכל a ו- b, וכן:

  • לכל \ a\in D ולכל \ 0\neq b \in D, קיימים \ q, r\in D כך ש- \ a=qb+r, כאשר \ r=0 או \ d(r)<d(b).

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

הדרישה \ d(a)\leq d(ab) איננה הכרחית, מכיוון שבהינתן פונקציה d המקיימת את הדרישה השנייה בלבד, אפשר להגדיר פונקציה חדשה \ \delta(x)=\min_{y\in D - \{0\}}d(xy), והיא תקיים את שתי הדרישות גם יחד.

כדי שהפונקציה תהיה מוגדרת גם באיבר האפס של D, יש הקובעים \ d(0)=0 (כאשר מובן שדרגתם של כל האיברים האחרים היא 1 לפחות).

דוגמאות[עריכת קוד מקור | עריכה]

תכונות של חוג אוקלידי[עריכת קוד מקור | עריכה]

הפונקציה האוקלידית d מאפשרת לזהות את האברים ההפיכים של החוג (u הוא איבר הפיך אם קיים v כך שמכפלתם uv=1). ראשית, הדרגה של 1 היא הדרגה הקטנה ביותר האפשרית (שהרי \ d(1)\leq d(1b)=d(b) לכל b). מתברר שהאברים ההפיכים בחוג הם בדיוק אלה שדרגתם שווה לדרגה של 1.

הוכחה

אם uv=1, אז \ d(1)=d(uv)\geq d(u)\geq d(1) ומכאן השוויון. מאידך, אם \ d(u) היא הדרגה הקטנה ביותר האפשרית, חילוק 1 ב- u מראה שלא יכולה להיות שארית; מכאן ש- u מחלק את 1, ואם כך u הפיך.

משפט. כל חוג אוקלידי D הוא ראשי (כלומר, כל אידאל שלו הוא מן הצורה \ Da=\{ba: b\in D\}). הוכחה. אם I אידאל שאינו אפס, אז קיים בו איבר a שדרגתו הקטנה ביותר מבין כל אברי I (כמובן, a אינו האיבר היחיד בעל תכונה זו). מיד נובע ש- \ Da\subseteq I. נניח שקיים ב- I איבר, למשל c, שאיננו מתחלק ב- a; חילוק עם שארית יתן \ c=qa+r כאשר \ d(r)<d(a). אולם \ r=c-qa\in I הוא איבר של האידאל, וזה סותר את בחירת a כאיבר בעל דרגה מינימלית שם.
מחלק משותף גדול ביותר: ניקח שני איברים a,b בתחום האוקלידי, (a),(b) הם האידאליים שהם יוצרים. החיתוך שלהם הוא כמובן אידאל, ומשום שתחום אוקלידי הוא תחום ראשי, הוא אידאל ראשי, ולכן יש לו יוצר. היוצר הזה הוא מחלק המשותף הגדול ביותר. עם זאת, הוא איננו בהכרח המחלק המשותף היחיד, ייתכנו עוד כאלו, אבל אם x,y שניים כאלו, אז קיים u הפיך כך ש- x=uy, כלומר, הם נבדלים רק במכפלה בהפיך.

אוקלידיות בתורת המספרים האלגברית[עריכת קוד מקור | עריכה]

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

בין השדות הריבועיים \ \mathbb{Q}[\sqrt{D}], כאשר D מספר שלם חיובי, חוג השלמים הוא אוקלידי ביחס לנורמה רק עבור \ D=2,3,5,6,7,11,13,17,19,21,29,33,37,41,57,73. הדרישה שהחוג יהיה אוקלידי דווקא ביחס לנורמה הכפלית חזקה יותר מאוקלידיות סתם, והדוגמה הבולטת ביותר לכך היא החוג \ \mathbb{Z}[\sqrt{14}], שאינו אוקלידי ביחס לפונקציית הנורמה, וב-2004 הוברר שהוא אוקלידי [1] (ביחס לפונקציה אחרת, מסובכת בהרבה). עדיין לא ידוע מיון שלם של החוגים האוקלידיים ממשפחה זו.

את חוגי השלמים של שדות מספרים אפשר לסדר לפי הדרגה של חבורת היחידות שלהם, שהיא סופית על-פי משפט היחידות של דיריכלה. חבורת יחידות סופית, בעלת דרגה 0, יש רק לחוגי השלמים של השדות הריבועיים \ \mathbb{Q}[\sqrt{D}], כאשר D מספר שלם שלילי. במקרה זה ידוע שיש תשעה חוגי שלמים ראשיים: \ D=-1,-2,-3,-7,-11,-19,-43,-67,-163, שמהם רק חמשת הראשונים הם אוקלידיים (הראשון ברשימה הוא חוג השלמים של גאוס), וכל אלה אוקלידיים על-פי הנורמה[1].

על-פי ההשערה, בכל מקרה אחר (כלומר, כאשר חבורת היחידות מדרגה חיובית), החוג אוקלידי כל אימת שהוא ראשי. השערה זו נובעת מהשערת רימן המוכללת[2], והיא נכונה גם ללא הנחה חזקה זו כאשר דרגת החבורה 4 לפחות[3].

קריטריונים לאוקלידיות[עריכת קוד מקור | עריכה]

את התוצאה שהוזכרה לעיל על חוגי השלמים בשדות ריבועיים מרוכבים הוכיח Motzkin[4] בעזרת הקריטריון הבא. מגדירים בחוג R קבוצות \ R_n, כאשר \ R_0=\{0\}, ואילו \ R_n היא קבוצת כל האיברים a, שעבורם לכל מחלקה בחוג המנה \ R/Ra יש נציג מן הקבוצה \ R_{n-1}. בפרט, \ R_1-\{0\} היא קבוצת האברים ההפיכים של החוג. לפי Motzkin, חוג הוא אוקלידי אם ורק אם כל איבר שלו שייך לאחת הקבוצות בסדרה זו.

בדיקת האוקלידיות כאשר d פונקציה כפלית היא קלה יותר, ואף מספקת במקרים מסוימים אלגוריתם לחישוב השארית. תחום שלמות R הוא אוקלידי ביחס לפונקציה כפלית d אם ורק אם שדה השברים F של R מכוסה כולו על ידי ה"כדורים" \ B(a)=\{x\in F| d(x-a)<1\} שמרכזיהם בנקודות ה"שלמות" \ a\in R. מקריטריון זה נובע שאם R אוקלידי ביחס לפונקציה כפלית, אז כל תת-חוג \ R \subseteq R' \subseteq F גם הוא אוקלידי.

מקורות[עריכת קוד מקור | עריכה]

  1. ^ ‏M. Harper,  \mathbb{Z}[\sqrt{14}] is Euclidean, Canad. J. Math. 56(1), 55-70, (2004).
  2. ^ ‏P.J. Weinberger, On Euclidean rings of algebraic integers, Analytic Number Theory, pp. 321-332, Amer. Math. Soc, 1973.
  3. ^ ‏M. Harper and M. Ram Murty, Euclidean Rings of Algebraic Integers, Canad. J. Math. 56(1), 71-76, (2004).
  4. ^ ‏T.S. Motzkin, The Euclidean Algorithm, Bull. Amer. Math. Soc. 55, 1142-1146 (1949).