תחומים אוקלידיים ותחומים ראשיים

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

• היה צריך להוכיח שלכל איבר בחוג שאיננו אפס או הפיך קיים פירוק לגורמים אי-פריקים.
• היה צריך להוכיח שהפירוק הזה הוא יחיד.

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

קיום פירוק לגורמים בתחום ראשי

כזכור, איבר לא הפיך \( a\in R \) הוא אי-פריק אם לא קיימים \( b,c \) שהם עצמם לא הפיכים כך ש-\( a=bc \). זה אומר שאם \( a \) כן פריק, אז בפרט קיים \( b \) לא הפיך שמחלק אותו. ואם אותו \( b \) גם הוא פריק אז קיים \( c \) שמפרק אותו, וכן הלאה. אינטואיטיבית אנחנו מצפים שהתהליך הזה שבו אנחנו לוקחים איבר, מוצאים גורם פריק שלו, ומוצאים גורם פריק של הגורם ההוא וכן הלאה - התהליך הזה צריך להסתיים מתישהו.

פורמלית, בואו ניקח \( a\in R \) לא הפיך. אם \( a \) אי-פריק, סיימנו. אחרת יש \( a_{1},a_{2}\in R \) שהם לא הפיכים כך ש-\( a=a_{1}a_{2} \). אם שניהם אי-פריקים, סיימנו. אחרת, נרצה להראות שקיים פירוק לאי-פריקים של כל אחד מהם. נניח ש-\( a_{1} \) הוא פריק בעצמו, אז אפשר לכתוב \( a_{1}=a_{11}a_{12} \) ולהמשיך באותו האופן. בסופו של דבר יקרה אחד משניים: או שנגיע לפירוק מלא לאי-פריקים, או שנקבל שרשרת שאסמן את איבריה ב-\( b_{0},b_{1},b_{2},b_{3},\dots \) של איברים שכולם פריקים ומתקיים \( b_{1}|b_{0} \) ו-\( b_{2}|b_{1} \) וכן הלאה. יותר קל לנסח את זה בלשון אידאלים: \( \left\langle b_{0}\right\rangle \subset\left\langle b_{1}\right\rangle \subset\left\langle b_{2}\right\rangle \subset\dots \) כשההכלה כאן היא הכלה ממש. עכשיו מגיע התעלול: נגדיר \( I=\bigcup_{i=0}^{\infty}\left\langle b_{i}\right\rangle \). קל לראות שהקבוצה הזו היא אידאל,ישירות על פי ההגדרה; ומכיוון שאנחנו בתחום ראשי אז קיים \( b\in I \) כך ש-\( I=\left\langle b\right\rangle \). מצד שני, מכיוון ש-\( I \) הוא בסך הכל איחוד של קבוצות, קיים \( \left\langle b_{n}\right\rangle \) כך ש-\( b\in\left\langle b_{n}\right\rangle \), כלומר \( I\subseteq\left\langle b_{n}\right\rangle \). קיבלנו סתירה: \( I\subseteq\left\langle b_{n}\right\rangle \subset\left\langle b_{n+1}\right\rangle \subseteq I \) - ה”הכלה ממש” לא יכולה להתקיים. זה מסיים את ההוכחה.

אם המצב כל כך פשוט, למה ההוכחה הזו “בעייתית”? ובכן, זה תלוי למה אתם קוראים בעייתי. יש בהוכחה הזו שימוש באקסיומת הבחירה, שאין בה משהו פסול לכשעצמו, אבל בהחלט אפשר לתהות אם ומתי אפשר להסתדר גם בלעדיה. אתם רואים את השימוש הזה? כרגיל בעניינים הללו, זה מתרחש במקום שבו אני מנפנף בידיים בזריזות ועושה משהו שנראה לכולנו טבעי. במקרה הנוכחי, ההנחה שהסדרה \( b_{0},b_{1},b_{2},b_{3},\dots \) קיימת בכלל. הרי לא הוכחתי ממש את קיומה; הצגתי תהליך שבהינתן \( b_{n} \) יודע לייצר את \( b_{n+1} \). זה בפני עצמו טוב ויפה אבל זה לא מבטיח שאני אוכל לייצר את האובייקט המלא \( b_{0},b_{1},b_{2},\dots \) בעזרת התהליך הזה. אם אתם עדיין לא משוכנעים, בסדר גמור; זה הרי לא פוסט על אקסיומת הבחירה והדקויות שלה.

מחלק משותף מקסימלי

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

הזכרתי את “יסודות” של אוקלידס בפוסט הקודם, כי שם נמצאת ההוכחה המוקדמת ביותר למשפט היסודי של האריתמטיקה; זה נמצא בספר 7, שהוא הראשון שעוסק בתורת המספרים. הספר הזה נפתח עם יישום כפול של מה שנקרא כיום האלגוריתם האוקלידי והוא ככל הנראה המושג החשוב ביותר בתורת המספרים האלמנטרית. יש לי כבר פוסט בנושא, אבל מן הסתם נדבר על זה מחדש. הרעיון מאחורי האלגוריתם האוקלידי הוא לתת שיטה למציאת מחלק משותף מקסימלי של זוג מספרים. מה זה מחלק משותף מקסימלי? אם \( a,b \) הם שני מספרים טבעיים, אז המחלק המשותף המקסימלי שלהם, שמסומן \( \text{gcd}\left(a,b\right) \) הוא מספר טבעי \( d \) שמחלק את שניהם, והוא הגדול ביותר מבין כל המספרים שמחלקים את שניהם. למשל, \( \text{gcd}\left(12,8\right)=4 \).

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

בהגדרה הכללית, \( d \) הוא מחלק משותף מקסימלי של \( a,b \) אם \( d|a \) וגם \( d|b \), ובנוסף לכך אם יש איבר כלשהו \( e \) שגם הוא מחלק משותף של \( a,b \), כלומר מקיים \( e|a \) וגם \( e|b \) אז בהכרח \( e|d \). במילים: \( d \) הוא מחלק משותף מקסימלי של \( a,b \) אם הוא מתחלק בכל מחלק משותף של \( a,b \). תחת ההגדרה הזו, מחלק משותף מקסימלי הוא לא יחיד: ל-12 ול-8 מהדוגמא הקודמת יש עכשיו את המחלקים המשותפים המקסימליים \( 4 \) וגם \( -4 \). לא קשה לראות מההגדרה שכל שני מחלקים משותפים מקסימליים חייבים לחלק זה את זה, ומכך נובע חיש קל שהם ידידים, כלומר זהים עד כדי כפל באיבר הפיך, כך שזה לא מקרי שבדוגמא שלנו קיבלנו את אותו מספר עד כדי סימן. זו הסיבה שבגללה למרות שאין מחלק משותף מקסימלי יחיד עדיין הסימון \( \text{gcd}\left(a,b\right) \) הוא כמעט מוגדר היטב ועדיין משתמשים בו.

יתרון אחד של ההגדרה באמצעות חלוקה היא שהיא מאפשרת לנו לעבור לדבר על אידאלים. בפוסט הקודם ראינו את היתרון שבגישה הזו - היא איפשרה לנו להוכיח בקלות שאי-פריק בתחום ראשי הוא ראשוני. במקרה שלנו, \( d \) הוא מחלק משותף מקסימלי של \( a,b \) אם \( a,b\in\left\langle d\right\rangle \), ובנוסף לכך אם \( a,b\in\left\langle e\right\rangle \) אז גם \( d\in\left\langle e\right\rangle \), כלומר \( \left\langle d\right\rangle \subseteq\left\langle e\right\rangle \). כלומר, המחלק המשותף הגדול ביותר דווקא יוצר את האידאל הקטן ביותר שמכיל את \( a,b \).

ובכן, שתי שאלות על היצור הזה:

• האם בהינתן \( a,b \) כלשהם שאינם אפס, בהכרח קיים להם מחלק משותף מקסימלי?
• בהינתן שקיים כזה, האם יש לנו דרך למצוא אותו?

אם אנחנו בתחום פריקות יחידה, אז התשובה לשתי השאלות היא חיובית. בואו נניח ש-\( R \) הוא תחום פריקות יחידה ו-\( a,b\in R \) הם איברים שונים מאפס כלשהם (אם אחד מהם הוא אפס אז אפס הוא מחלק משותף מקסימלי שלהם). נסתכל על הפירוק לגורמים היחיד שלהם (זכרו ש”יחיד” זה עד כי החלפה של איברים במכפלה בידידים שלהם, כלומר כפל שלהם בהפיך):

\( a=r_{1}r_{2}\cdots r_{k} \)

\( b=s_{1}s_{2}\dots s_{t} \)

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

\( 60=2\cdot2\cdot3\cdot5 \)

\( 126=2\cdot3\cdot3\cdot7 \)

אז אכתוב:

\( 60=2^{2}\cdot3^{1}\cdot5^{1}\cdot7^{0} \)

\( 126=2^{1}\cdot3^{2}\cdot5^{0}\cdot7^{1} \)

ובאופן כללי:

\( a=p_{1}^{a_{1}}\cdots p_{n}^{a_{n}} \)

\( b=p_{1}^{b_{1}}\cdots p_{n}^{b_{n}} \)

וכעת מחלק משותף מקסימלי לשני אלו נתון על ידי

\( \text{gcd}\left(a,b\right)=p_{1}^{\min\left\{ a_{1},b_{1}\right\} }p_{2}^{\min\left\{ a_{2},b_{2}\right\} }\cdots p_{n}^{\min\left\{ a_{n},b_{n}\right\} } \)

ובדוגמא שלנו:

\( \text{gcd}\left(60,126\right)=2^{\min\left\{ 2,1\right\} }\cdot3^{\min\left\{ 1,2\right\} }\cdot5^{\min\left\{ 1,0\right\} }\cdot7^{\min\left\{ 0,1\right\} }=2^{1}\cdot3^{1}\cdot5^{0}\cdot7^{0}=6 \)

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

עד כמה זו אבחנה מדהימה? ובכן, האלגוריתם האוקלידי הוא אבן יסוד ברוב האלגוריתמים היעילים בתורת המספרים; מצד שני, עד היום אין לנו אלגוריתם יעיל לפירוק לגורמים. בלי האלגוריתם האוקלידי, תורת המספרים האלגוריתמית כפי שאנחנו מכירים אותה לא הייתה מתקיימת. למרות שאם אני רוצה להיות הגון היסטורית, עיקר השימושיות האלגוריתמית של האלגוריתם האוקלידי היא בהרבה שלו, שמאפשרת לנו למצוא \( x,y \) כך ש-שווה ל-\( \text{gcd}\left(a,b\right)=ax+by \) .

איך עושים את הקסם הזה? ובכן, התשובה טמונה במשהו שאנחנו יודעים לעשות עם מספרים שלמים עוד מבית הספר היסודי: חלוקה עם שארית. אם \( a,b \) הם מספרים שלמים אז קיימים \( q,r \) כך ש-\( a=qb+r \): \( q \) הוא המנה של חלוקת \( a \) ב-\( b \) ואילו \( r \) הוא השארית. כדי שזה יהיה מעניין, אנחנו רוצים על פי רוב שהשארית תהיה קטנה ככל הניתן, כלומר \( 0\le r<\left|b\right| \) (כלומר, \( 13=2\cdot5+3 \) הוא הדרך ה”נכונה” לחלק את 13 ב-5 עם שארית, ולא, למשל, \( 13=1\cdot5+8 \)).

לא קשה לראות שאם \( a=qb+r \) אז \( \text{gcd}\left(a,b\right)=\text{gcd}\left(b,r\right) \), והאבחנה הזו היא המפתח לאלגוריתם האוקלידי: פשוט מחלקים את \( a \) ב-\( b \). אם השארית היא 0, אז \( \text{gcd}\left(a,b\right)=b \), ואחרת ממשיכים רקורסיבית למצוא את \( \text{gcd}\left(b,r\right) \). בפוסט שלי על הנושא יש את הפירוט המלא, כולל קוד. לעת עתה בואו נתמקד בסיבה שבגללה האלגוריתם עובד ואיך אפשר להכליל את זה. האלגוריתם עובד בדיוק בגלל התכונה הזו שהשארית “יותר קטנה” ממה שמחלקים בו, מה שמבטיח שהאלגוריתם יעצור בסופו של דבר, ואפילו די מהר. לכן, אם אנחנו רוצים להשתמש בו בחוגים כלליים, אנחנו צריכים מושג של “חלוקה עם שארית” ומושג של “גודל” שיאפשר לנו לקבוע שהשארית קטנה יותר ממה שמחלקים בו.

תחומים אוקלידיים

בפוסט הקודם ראינו את המושג של נורמה. כמקודם, אם \( R \) הוא חוג, אז נורמה תהיה פונקציה \( N:R\to\mathbb{N} \). בפוסט הקודם דרשתי משהו בסגנון \( N\left(a\right)N\left(b\right)=N\left(ab\right) \), אבל כרגע אני עדיין לא אעשה שום דבר כזה. הדרישה היחידה שלי מהנורמה היא זו: שלכל \( a,b\in R \) כך ש-\( b\ne0 \) יהיו קיימים (ולאו דווקא יחידים) \( q,r\in R \) כך ש-\( a=qb+r \) ו-\( N\left(r\right)<N\left(b\right) \) או ש-\( r=0 \) (למה אני דורש במפורש את האפשרות \( r=0 \)? כי ההגדרה שלי לא פוסלת את האפשרות של איברים שונים מאפס עם נורמה 0).

אם בחוג שלנו יש דבר כזה, מיידית קיבלנו את קיום האלגוריתם האוקלידי, והחוג נקרא תחום אוקלידי. בואו ונראה את זה. ראשית, אני רוצה להוכיח שאם \( R \) הוא תחום אוקלידי אז הוא בפרט תחום ראשי, כלומר שכל אידאל נוצר על ידי איבר יחיד. ניקח אידאל \( I\ne\left\{ 0\right\} \) שכזה. לכל איבר בו יש נורמה; בואו ניקח איבר שונה מ-\( 0 \) שהנורמה שלו היא מינימלית (אולי יש כמה כאלו, אז נבחר אחד באופן שרירותי). הקיום של מינימום כזה מובטח מכך שהטווח של הנורמה הוא \( \mathbb{N} \), וזו קבוצה סדורה היטב (כלומר, לכל תת-קבוצה שלה יש איבר מינימלי). נסמן את האיבר הזה ב-\( d \). ברור ש-\( \left\langle d\right\rangle \subseteq I \), אבל צריך להוכיח את הכיוון השני - להראות ש-\( I\subseteq\left\langle d\right\rangle \) שזו דרך אחרת לומר שלכל \( a\in I \) מתקיים ש-\( d|a \).

ובכן, מכיוון שאנחנו בתחום אוקלידי, אפשר לחלק את \( a \) ב-\( d \) ולקבל \( a=qd+r \) עם \( N\left(r\right)<N\left(d\right) \). על ידי העברת אגף נקבל ש-\( r=a-qd\in I \) (כי \( d\in I \) ולכן \( qd\in I \) ולכן גם \( a-qd\in I \) - אלו תכונות הסגירות הרגילות של אידאלים). מצד שני, הנורמה של \( r \) קטנה ממש מזו של \( d \), והרי בחרנו את \( d \) להיות האיבר בעל הנורמה המינימלית מבין כל האיברים השונים מאפס ב-\( I \), ולכן בהכרח \( r=0 \), כלומר \( a=dq \) ולכן \( a\in\left\langle d\right\rangle \). הופס, זה היה קל עד להפתיע.

טריק “העברת האגף” הזה שבו מחלקים \( a \) ב-\( b \), מקבלים \( a=qb+r \) ואז מעבירים אגף ומקבלים \( r=a-qb \) הוא גם מה שמראה שאם \( d \) הוא מחלק משותף של \( a,b \) אז הוא מחלק גם את \( r \) (פשוט מאוד: הוא מחלק את אגף ימין של \( r=a-qb \) ולכן את אגף שמאל) ומכאן כבר קל להראות שאם \( d \) הוא המחלק המשותף המקסימלי של \( a,b \) אז כך גם עבור \( b,r \), והאלגוריתם האוקלידי עובד.

מכיוון שהראיתי שכל תחום אוקלידי הוא תחום ראשי, אז יחד עם מה שהראיתי בפוסט הקודם ראינו שבכל תחום אוקלידי אם קיים פירוק לגורמים אז הוא יחיד. עכשיו אני רוצה להראות שאכן קיים פירוק לגורמים. כזכור, בפוסט הקודם הראיתי שאם יש לנו על החוג נורמה כפלית, כלומר כזו שמקיימת \( N\left(a\right)N\left(b\right)=N\left(ab\right) \), זה מספיק כדי להוכיח בקלות קיום של פירוק לגורמים.

רק מה, בתחום אוקלידי אמנם יש נורמה, אבל שום דבר לא מבטיח שהיא כפלית שכזו. למרבה המזל, אם יש לנו תחום אוקלידי, תמיד אפשר לתקן את הנורמה שלו כך שבנוסף לתכונת החלוקה הנחמדה שלה היא תיתן לנו את מה שצריך בשביל להוכיח פירוק יחיד. לשם כך בואו נקל טיפה על הדרישות שלנו: אני אראה שמספיק לי שתתקיים התכונה \( N\left(a\right)\le N\left(ab\right) \) לכל \( b\ne0 \) כדי להשיג את כל הטוב של הפוסט הקודם. איך נבנה נורמה כזו?

התעלול הוא פשוט: נניח ש-\( N:R\to\mathbb{N} \) היא נורמה אוקלידית על \( R \). כלומר, לכל \( a,b\in R \) כך ש-\( b\ne0 \) קיימים \( q,r \) כך ש-\( a=bq+r \) ו-\( N\left(r\right)<N\left(b\right) \) או ש-\( r=0 \). עכשיו בואו ניקח פטיש ונרביץ ממש ממש חזק ל-\( N \) עד שתתעקם לצורה שאנחנו צריכים. לנורמה החדשה שלנו נקרא \( \overline{N} \).

קודם כל, שום דבר לא מונע מאיתנו להגדיר \( \overline{N}\left(0\right)=0 \), אז שיהיה (הרי השימוש היחיד שלנו בנורמה הוא בבדיקה \( N\left(r\right)<N\left(b\right) \) שלא אמורה בכלל להתבצע אם \( r \) או \( b \) הם 0; לפעמים בספרות פשוט אומרים מראש שהנורמה לא מוגדרת עבור 0).

עכשיו, אנחנו רוצים להגדיר את \( \overline{N}\left(a\right) \) עבור \( a\ne0 \) כלשהו. מצד אחד, אנחנו רוצים שזה יתבצע בעזרת \( N \), כי אין לנו שום דבר אחר להיאחז בו; מצד שני, אנחנו חייבים שיתקיים \( \overline{N}\left(a\right)\le\overline{N}\left(ab\right) \) לכל \( b\ne0 \) אפשרי. אז בואו נגדיר את \( \overline{N}\left(a\right) \) להיות הדבר הכי גדול שאפשר, במסגרת המגבלה הזו: \( \overline{N}\left(a\right)\triangleq\min_{b\ne0}N\left(ab\right) \). מכיוון שגם \( b=1 \) נכלל בהגדרה הזו, אנחנו מקבלים \( \overline{N}\left(a\right)\le N\left(a\right) \), כלומר הנורמה החדשה שלנו יכולה רק להיות קטנה או שווה לישנה, ולכן מה שאנחנו עושים כאן הוא לטפל באיברים שהנורמה שלהם הייתה “מנופחת יותר מדי”.

אנחנו צריכים קודם כל לוודא שאכן מתקיימת התכונה שלשמה התכנסנו: \( \overline{N}\left(a\right)\le\overline{N}\left(ab\right) \) לכל \( b\ne0 \). הרעיון מאוד פשוט: \( \overline{N}\left(ab\right)=N\left(ab\cdot c\right) \) עבור \( c \) כלשהו (ה-\( c \) שעבורו מתקבל מינימום על פני כל הערכים \( N\left(ab\cdot c\right) \)). מאסוציאטיביות הכפל של החוג נקבל שהערך הזה שווה ל-\( N\left(a\cdot bc\right) \). כלומר, זה ערך מהערכים שהופיעו בחישוב של \( \overline{N}\left(a\right) \) (כי \( bc\ne0 \), שהרי אנחנו בתחום שלמות). ולכן \( \overline{N}\left(a\right)\le N\left(a\cdot bc\right)=\overline{N}\left(ab\right) \).

מסקנה אחת שאפשר להסיק ממה שכבר עשינו היא ש-\( \overline{N}\left(1\right)\le\overline{N}\left(1\cdot b\right)=\overline{N}\left(b\right) \) לכל \( b\ne0 \) בחוג. שימו לב שזה לא אומר ש-\( \overline{N}\left(1\right)=1 \); רק שזה הערך המינימלי ש-\( \overline{N} \) יכולה לקבל בכלל על קלט שאיננו אפס.

עכשיו צריך להראות שלא הרסנו את הנורמה שלנו בתהליך היצירה שלה - שעדיין, לכל \( a,b \) קיימים \( q,r \) כך ש-\( a=bq+r \) ו-\( \overline{N}\left(r\right)<\overline{N}\left(b\right) \) או ש-\( r=0 \). מה החשש? שאולי בתהליך היצירה של \( \overline{N} \) היה \( b \) שהקטנו פלאים את גודל הנורמה שלו ביחס לזו של שאר האיברים בחוג, ופתאום מי שיכלו לשמש בתור “שאריות” בחלוקה ב-\( b \) כבר לא טובות לתפקיד. זו בעיה אמיתית שצריך להתמודד איתה, והנה הדרך לעשות את זה: קודם כל, \( \overline{N}\left(b\right)=N\left(bc\right) \) עבור \( c\in R \) שונה מאפס כלשהו. כעת, אפשר לחלק את \( a \) ב-\( bc \) על פי הנורמה \( N \), ולקבל ש-\( a=\left(bc\right)q+r \) כך ש-\( N\left(r\right)<N\left(bc\right) \) או ש-\( r=0 \). מהדברים שכבר ראינו נסיק שאם \( r\ne0 \) אז \( \overline{N}\left(r\right)\le N\left(r\right)<N\left(bc\right)=\overline{N}\left(b\right) \), כך שיחד עם המשוואה \( a=b\left(cq\right)+r \) קיבלנו בדיוק את מה שרצינו.

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

דוגמאות לתחומים אוקלידיים

הדוגמא הראשונה היא כמובן \( \mathbb{Z} \) עם הנורמה שהיא ערך מוחלט, אבל יש דוגמא אחרת שהיא חשובה לא פחות: פולינומים מעל שדה. אני אכתוב פוסט ייעודי על פולינומים ודומיהם בהמשך, אז בינתיים אסתפק בלהזכיר שפולינום מעל חוג \( R \) הוא יצור שנראה ככה: \( p\left(x\right)=a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0} \) כאשר \( a_{0},\dots,a_{n}\in R \), \( a_{n}\ne0 \) אלא אם \( n=0 \) (כלומר, האיבר של החזקה הגבוהה ביותר של הפולינום איננו מיותר) ו-\( n \) הוא מספר טבעי כלשהו שנקרא הדרגה של הפולינום ומסומן בתור \( \deg\left(p\right) \) . למשל, \( p\left(x\right)=5x^{2}+\pi x+-\frac{7}{2} \) הוא פולינום מעל החוג \( \mathbb{R} \) עם \( \deg\left(p\right)=2 \).

כאשר \( R \) הוא שדה, כמו מה שנדבר עליו עכשיו, יותר נפוץ לסמן אותו באות \( F \), ואת חוג הפולינומים מעל \( F \) ב-\( F\left[x\right] \). למה חשוב לי לדבר על שדות? תכף נראה. כזכור, שדה הוא חוג קומוטטיבי שבו לכל איבר יש הפיך; ההפיכות הזו היא התכונה החשובה ביותר כאן.

מה שיפה בפולינומים הוא שיש להם חלוקה-עם-שארית כמו שיש למספרים השלמים. בשביל לדבר על זה צריך להגיד מה תהיה הנורמה שלהם; הדרגה של הפולינום נותנת לנו נורמה באופן טבעי. פשוט מגדירים \( N\left(p\right)=\deg\left(p\right) \). הנורמה הזו היא לא כפלית, אבל שימו לב מה כן קורה: מתקיים \( \deg\left(ab\right)=\deg\left(a\right)+\deg\left(b\right) \) אלא אם אחד מהפולינומים הוא 0 (ולכן לפעמים מגדירים \( \deg\left(0\right)=-\infty \), כדי שהשוויון הזה “ימשיך להתקיים”). האם זה מזכיר לכם משהו? זה מה שקורה בחזקות: \( 2^{a+b}=2^{a}\cdot2^{b} \). בשל כך, אם רוצים לקבל נורמה כפלית אפשר להגדיר \( N\left(p\right)=2^{\deg\left(p\right)} \) ואז מקבלים ש-

\( N\left(ab\right)=2^{\deg\left(ab\right)}=2^{\deg\left(a\right)+\deg\left(b\right)}=2^{\deg\left(a\right)}2^{\deg\left(b\right)}=N\left(a\right)N\left(b\right) \)

אבל אני לא אזדקק לזה כאן אז נדבוק בנורמה שהיא פשוט הדרגה של הפולינום ונראה איך יחד איתה אנחנו מקבלים תחום אוקלידי. אני אדגים על מקרה קונקרטי פשוט. נסתכל בחוג \( \mathbb{R}\left[x\right] \) על הפולינומים \( a\left(x\right)=x^{3}+2x^{2}+7 \) ו-\( b\left(x\right)=x+3 \). אני רוצה למצוא \( q\left(x\right),r\left(x\right) \) כך ש-\( a\left(x\right)=b\left(x\right)q\left(x\right)+r\left(x\right) \) ו-\( \deg\left(r\right)<\deg\left(b\right) \). קודם כל אני רוצה “להיפטר” מהאיבר \( x^{3} \) של \( a\left(x\right) \). אז אני לוקח את כל \( b\left(x\right) \), רואה שהאיבר המוביל שלו הוא \( x \), וכופל את הכל ב-\( -x^{2} \). עכשיו אני מקבל \( -x^{3}-3x^{2} \), וזה פולינום שכאשר אני מחבר אותו ל-\( a\left(x\right) \) אני מוחק לגמרי את האיבר בחזקה שלישית של \( a \) ונשאר עם:

\( a\left(x\right)-x^{2}b\left(x\right)=-x^{2}+7 \)

עכשיו אני רוצה להיפטר מה-\( -x^{2} \) של התוצאה. אז אני כופל שוב את \( b\left(x\right) \) במשהו מתאים, הפעם ב-\( x \), ומקבל:

\( a\left(x\right)-x^{2}b\left(x\right)+xb\left(x\right)=\left(-x^{2}+7\right)+\left(x^{2}+3x\right)=3x+7 \)

ועכשיו - להיפטר מה-\( 3x \) על ידי כפל ב-\( -3 \)!

\( a-x^{2}b+xb-3b=\left(3x+7\right)-\left(3x+9\right)=-2 \)

עכשיו אפשר להוציא גורם משותף באגף שמאל - מוציאים את \( b \) החוצה מכל המכפלות שבהן הוא משתתף, ומקבלים:

\( a\left(x\right)-b\left(x\right)\left(x^{2}-x+3\right)=-2 \)

או במילים אחרות

\( a\left(x\right)=b\left(x\right)\left(x^{2}-3x+3\right)-2 \)

קיבלנו \( q\left(x\right)=x^{2}-3x+3 \) ו-\( r\left(x\right)=-2 \), ואכן \( \deg\left(r\right)=0<1=\deg\left(b\right) \).

את התעלול הזה שבו מחסרים שוב ושוב “משהו כפול \( b \)” מ-\( a \) ומוחקים כל חזקה שגדולה או שווה לזו של המקדם המוביל של \( b \) אפשר לעשות תמיד, אבל רק מכיוון שאנחנו מעל שדה. למשל, אם \( a\left(x\right)=x^{2}+1 \) ו-\( b\left(x\right)=2x \) נהיה חייבים לכפול את \( b \) ב-\( -\frac{1}{2} \) כדי לנטרל את החזקה \( x^{2} \) של \( a \); אם היינו מעל \( \mathbb{Z} \) לא היינו מסוגלים לעשות משהו כזה וכל האוקלידיות הייתה הולכת לנו לאיבוד.

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

עוד דוגמא לחוג אוקלידי הוא השלמים הגאוסיים, \( \mathbb{Z}\left[i\right] \). אני לא הולך להוכיח את זה כאן כי כבר הוכחתי את זה בפוסט הקודם שלי בנושא, ואם לצטט את עצמי - “ההוכחה הזו מגעילה”. מה שכדאי לקחת מההוכחה הזו הוא שקשה להוכיח שחוגים הם אוקלידיים, ואפילו די אד-הוקי; ממש לא כל חוג חביב הוא אוקלידי. בפרט, אם לוקחים את השדה \( \mathbb{Q}\left(\sqrt{-d}\right) \) ומסתכלים על חוג השלמים שלו (שיהיה לרוב \( \mathbb{Z}\left[\sqrt{-d}\right] \) אבל לא תמיד, ואני מעדיף לא להיכנס עכשיו לפרטים) אז מקבלים חוג שהוא תחום פריקות יחידה רק במקרים הבאים: \( d=1,2,3,7,11,19,43,67,163 \). בכל יתר המקרים אין פריקות יחידה, ובפרט החוג לא יהיה אוקלידי. כך שתחומים אוקלידיים הם דבר נפוץ הרבה פחות מאשר נראה (לפחות לי) במבט ראשון.

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