חוג אוקלידי

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

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

הגדרה

תחום שלמות ${\displaystyle D}$ הוא חוג אוקלידי, אם קיימת פונקציה המחזירה מספרים שלמים אי-שליליים, ${\displaystyle d\colon D\setminus \{0\}\rightarrow \mathbb {N} \cup \{0\}}$ (המכונה לעיתים פונקציית דרגה), המקיימת את שתי הדרישות הבאות:

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

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

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

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

דוגמאות

• חוג המספרים השלמים ${\displaystyle \mathbb {Z} }$ הוא חוג אוקלידי, כאשר הפונקציה ${\displaystyle d(x)=|x|}$ מחזירה את הערך המוחלט של כל מספר שלם.
• חוג השלמים של גאוס ${\displaystyle \mathbb {Z} [i]=\mathbb {Z} +\mathbb {Z} {\sqrt {-1}}}$, כאשר פונקציית הדרגה ${\displaystyle d}$ היא הנורמה ${\displaystyle d(x+iy)=x^{2}+y^{2}}$.
• חוג הפולינומים בעלי מקדמים בשדה, כאשר ${\displaystyle d}$ היא פונקציית המעלה המקובלת: ${\displaystyle d(a_{0}+\dots +a_{n}x^{n})=n}$ בהנחה שהמקדם המוביל ${\displaystyle a_{n}\neq 0}$.

תכונות של חוג אוקלידי

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

משפט: כל חוג אוקלידי ${\displaystyle D}$ הוא ראשי (כלומר, כל אידיאל שלו הוא מן הצורה ${\displaystyle Da=\{ba:b\in D\}}$).

הוכחה: אם ${\displaystyle I}$ אידיאל שאינו אפס, אז קיים בו איבר ${\displaystyle a}$ שדרגתו הקטנה ביותר מבין כל אברי ${\displaystyle I}$ (כמובן, ${\displaystyle a}$ אינו בהכרח האיבר היחיד בעל תכונה זו). מכאן נובע ש- ${\displaystyle Da\subseteq I}$. נניח שקיים ב-${\displaystyle I}$ איבר, למשל ${\displaystyle c}$, שאינו מתחלק ב-${\displaystyle a}$; חילוק עם שארית יתן ${\displaystyle c=qa+r}$ כאשר ${\displaystyle d(r)<d(a)}$. אולם ${\displaystyle r=c-qa\in I}$ הוא איבר של האידיאל, וזוהי סתירה לבחירת ${\displaystyle a}$ כאיבר בעל דרגה מינימלית ב- ${\displaystyle I}$.

מחלק משותף גדול ביותר: יהיו ${\displaystyle a,b}$ שני איברים בתחום אוקלידי ויהיו ${\displaystyle (a),(b)}$ האידיאלים שאיברים אלה יוצרים. הסכום של שני האידיאלים, ${\displaystyle (a,b)}$, הוא כמובן אידיאל ומשום שתחום אוקלידי הוא תחום ראשי אז ${\displaystyle (a,b)}$ הוא אידיאל ראשי ולכן יש לו יוצר. היוצר הזה הוא מחלק משותף גדול ביותר. עם זאת הוא אינו בהכרח המחלק המשותף היחיד, כלומר יכולים להיות מחלקים משותפים נוספים. אם ${\displaystyle x,y}$ הם שני מחלקים משותפים אז קיים איבר הפיך ${\displaystyle u}$ כך ש-${\displaystyle x=uy}$, כלומר המחלקים המשותפים נבדלים רק בכפל באיבר הפיך.

אוקלידיות בתורת המספרים האלגברית

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

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

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

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

קריטריונים לאוקלידיות

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

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

קישורים חיצוניים

• חוג אוקלידי, באתר MathWorld (באנגלית)