האלגוריתם האוקלידי וחוגים אוקלידיים

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

“אלגוריתם” הוא פשוט תהליך בעל תיאור מדויק ופשוט (טוב, לא בהכרח פשוט, אבל סופי). הרעיון באלגוריתם הוא לפשט חישובים מסובכים על ידי תיאור שלהם כסדרה של חישובים פשוטים, וזה גם בדיוק מה שהאלגוריתם האוקלידי עושה. המטרה שלו לא נשמעת גרנדיוזית כל כך ממבט ראשון - בהינתן שני מספרים טבעיים \( a,b \), אנחנו רוצים למצוא את המחלק המשותף המקסימלי של שניהם, שמסומן \( \mbox{gcd}\left(a,b\right) \) ובקיצור \( \left(a,b\right) \). המחלק המשותף המקסימלי הוא בדיוק מה שהוא נשמע שהוא - המספר הגדול ביותר שמחלק גם את \( a \) וגם את \( b \). כך למשל \( \left(30,20\right)=10 \) ו-\( \left(7,22\right)=1 \).

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

בשביל מה זה טוב? הדוגמה הקלאסית ביותר, שכבר הוזכרה בבלוג, היא זו של אריתמטיקה מודולרית. באריתמטיקה מודולו \( n \) אנחנו מבצעים פעולות חשבון רגילות על מספרים טבעיים אבל אחרי כל פעולה אנחנו מחלקים ב-\( n \) ולוקחים את השארית. למה? טוב, זה סיפור שלם, אבל די אם נאמר שמערכת ההצפנה RSA פועלת בעולם שאלו חוקי החשבון שלו. בעולם הזה צריך גם לחלק, ולחלק ב-\( a \) פירושו בעצם לכפול במספר אחר, \( a^{-1} \), שמקיים את התכונה ש-\( aa^{-1}=1 \) (עם כלל הכפל-ואז-חילוק-ב-\( n \)-ולקיחת-שארית). כדי למצוא את \( a^{-1} \) מפעילים את האלגוריתם האוקלידי על \( a,n \) כדי למצוא \( ax+ny=1 \) ואז \( x \) הוא \( a^{-1} \) המבוקש (זה דורש שיתקיים \( \left(a,n\right)=1 \) אחרת כלל לא ניתן לחלק ב-\( a \) מודולו \( n \)).

בקיצור, סמכו עלי, זה טוב.

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

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

אם כן, איך האלגוריתם פועל? כפי שאמרתי, אלגוריתם פירושו פירוק פעולת חישוב מסובכת לפעולות יותר פשוטות. כאן הפעולה הפשוטה יותר היא כזו שלומדים בבית הספר היסודי - חילוק עם שארית. לא אכנס הפעם לדיון על איך עושים את זה בפועל (למרות שזו שאלה מרתקת בפני עצמה - כשהיינו ילדים ולמדנו את זה לא ממש עצרנו - לפחות לא אני - ושאלנו את עצמנו למה זה עובד) אלא רק אגיד מה נובע מזה: בהינתן מספרים טבעיים \( a,b \) אנחנו יודעים למצוא מספרים טבעיים \( q,r \) כך ש-\( a=bq+r \). ל-\( q \) קוראים המנה של \( a \) חלקי \( b \) ול-\( r \) קוראים השארית. התכונה הכי הכי הכי הכי חשובה כאן, שלפעמים אנחנו בקושי נותנים עליה את הדעת, היא הגודל של השארית: מובטח לנו שיתקיים \( 0\le r<b \), כלומר השארית תמיד קטנה מהמספר שבו מחלקים. על הפרט הזה קם ונופל הפוסט כולו.

עכשיו אפשר להציג את האלגוריתם האוקלידי. האבחנה המרכזית היא שאם \( a=bq+r \) אז \( \left(a,b\right)=\left(b,r\right) \). למה? כי אם מישהו מחלק את \( a,b \) הוא יחלק גם את \( a-bq \), כלומר את \( r \); ואם מישהו מחלק את \( b,r \) אז הוא מחלק גם את \( bq+r \), כלומר את \( a \). בפרט, \( \left(a,b\right) \) מחלק גם את \( r \) ולכן \( \left(a,b\right)\le\left(b,r\right) \) (כי \( \left(a,b\right) \) מחלק את \( b,r \) ולכן קטן או שווה מהמקסימלי שמחלק אותם שהוא \( \left(b,r\right) \)) ובאופן דומה \( \left(b,r\right)\le\left(a,b\right) \).

זה מעניק לנו את האלגוריתם האוקלידי הפשוט, על המספרים \( a\ge b \):

  1. אם \( b=0 \) החזר את \( a \).
  2. חשב את \( a=bq+r \).
  3. הצב \( a\leftarrow b,b\leftarrow r \).
  4. חזור אל 1.

אני אישית חושב שלראות קוד אמיתי אפילו יותר ברור כאן, אז הנה קוד בשפת רובי, שמשתמש ברקורסיה:

def gcd(a,b)
  return a if b == 0
  return gcd(b, a % b)
end

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

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

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

\( \left(a,b\right)=\left(b,r\right)=bx+\left(a-qb\right)y=ay+\left(x-qy\right)b \)

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

def extended_gcd(a,b)
  return [a,1,0] if b == 0
  q = a / b
  r = a % b
  gcd, x, y = extended_gcd(b,r)
  return [gcd, y, x-q*y]
end

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

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

כדי שלא נרחיק לכת יותר מדי, אנחנו מגבילים מראש את הדיון לדברים ש”בבסיסם הם כמו המספרים השלמים”. מה זה אומר? פורמלית, חוגים קומוטטיביים עם יחידה שהם תחומי שלמות; לא פורמלית, קבוצות של “איברים” (עוד מעט יהיו דוגמאות) שמוגדרות עליהן פעולות חיבור וכפל שמתנהגות כמו במספרים השלמים (כללי הקיבוץ, החילוף והפילוג). קבוצות כאלו נקראות “חוגים”. בנוסף, דורשים שבחוג שלנו יהיה קיים איבר נייטרלי לכפל (כמו 1 במספרים הטבעיים) ועוד תכונה חשובה וכבר לא מובנת מאליה - אי אפשר לכפול שני איברים שונים מאפס ולקבל אפס. זה נכון במספרים השלמים, אבל בחוג השלמים מודולו 6 זה כבר לא כך: 3 כפול 2 שווה 0 (כי השארית שמתקבלת כשמחלקים את 3 כפול 2 ב-6 היא 0). לאיבר שונה מאפס שאפשר לכפול אותו במישהו אחר ששונה מאפס ולקבל אפס קוראים “מחלק אפס”. פורמלית כל מספר מחלק את אפס, כי \( a\cdot0=0 \) תמיד; זה נהיה מעניין רק כשיש \( b\ne0 \) כך ש-\( a\cdot b=0 \) התופעה הזו גורמת לדברים מוזרים: אנחנו רגילים לכך שאם \( ax=ay \) עבור \( a\ne0 \) אז \( x=y \); אבל אם \( a \) הוא מחלק אפס אז זה כבר לא יהיה נכון. למשל, אנחנו יודעים שאם \( a \) הוא מחלק אפס אז \( a\cdot b=a\cdot0=0 \) עבור \( b\ne0 \) כלשהו. ואם נחזור לדוגמה של השלמים מודולו 6, הרי ש-\( 2\cdot4=2\cdot1 \), למשל.

לעומת זאת, אם אנחנו דורשים במפורש שלא יהיו מחלקי אפס בחוג שלנו נובע מכך שאכן אם \( ax=ay \) אז \( x=y \) לכל \( a\ne0 \), כי על ידי העברת אגפים וחוק הפילוג מקבלים \( a\left(x-y\right)=0 \) ומכיוון ש-\( a\ne0 \) בהכרח \( x-y=0 \), כלומר \( x=y \). כלומר, החשבון מתנהג פחות או יותר כפי שאנחנו מצפים שיתנהג. לחוגים שבהם מתקיימת התכונה הזו קוראים “תחומי שלמות” (לרוב דורשים במפורש שהם גם יהיו קומוטטיביים ועם יחידה אבל נעזוב את זה). אם כן, ההכללה שאציג תניח מראש שבחוגים שאנחנו מדברים עליהם מתקיימות התכונות הללו.

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

המרכיב הנוסף שחסר לנו כדי להתחיל להריץ את האלגוריתם האוקלידי גם על החוגים הללו הוא חילוק עם שארית. אם \( \alpha,\beta \) הם שלמים גאוסיים, היינו רוצים לומר שאפשר לכתוב \( \alpha=\beta\cdot\gamma+\rho \) (האותיות היווניות מטרתן להבהיר שמדובר על שלמים גאוסיים ולא על מספרים “רגילים”) כך ש-\( \rho \) “קטן מ-\( \beta \)”. אבל זה מעלה את השאלה - קטן באיזה מובן? איך מודדים?

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

ראשית, אם ה”גודל” יכול להיות מספר רציונלי כלשהו, לא קשה לראות שאפשר לבנות סדרה יורדת אינסופית של גדלים שאף פעם לא מגיעה לאפס: \( 1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\dots \). כדי למנוע עיוותים כאלו אנחנו רוצים שהגדלים שלנו יהיו בעלי סדר טוב, או כדי לחסוך כאב ראש - אנחנו רוצים ש”גודל” יהיה תמיד מספר טבעי (חיובי או אפס).

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

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

השם המפורש במתמטיקה ל”גודל” המדובר הוא נורמה. זה שם מבלבל כי המילה “נורמה” מופיעה בהרבה הקשרים במתמטיקה, אבל בפוסט הזה אדבר רק על ההקשר הזה כך שלא יהיה חשש לבלבול. בהגדרה הפשוטה שלנו, אנו דורשים רק שהנורמה של איבר \( a \) של החוג, שאסמן כ-\( N\left(a\right) \), תהיה מספר שלם אי שלילי ותו לא; הדרישה הנוספת היחידה שיש לי היא זו של חילוק עם שארית:

אם \( a,b \) איברים של החוג כך ש-\( b\ne0 \) אז קיימים \( q,r \) בחוג כך ש-\( a=bq+r \) ובנוסף, או ש-\( r=0 \), או ש-\( N\left(r\right)<N\left(b\right) \).

ההגדרה הזו עוקפת את ה”בעיה” בכך שיש איברים בעלי נורמה 0. אנחנו מרשים להם להתקיים, אבל אם הם מחלקים מישהו, מובטח שהשארית באותה חלוקה תהיה אפס. למה? כי אם \( N\left(b\right)=0 \) ו-\( a=bq+r \) ו-\( N\left(r\right)<N\left(b\right) \) או ש-\( r=0 \), בהכרח האופציה השניה חייבת להתקיים כי לא ייתכן ש-\( N\left(r\right)<0 \) שהרי הנורמה היא מספר אי שלילי. זה מבטיח לנו שהאלגוריתם האוקלידי ניתן להפעלה בחוג ושהוא מסתיים אחרי מספר צעדים סופי (כשצצה השארית 0).

לחוגים שבהם קיימת נורמה שעונה על הדרישות שהצגתי קוראים חוגים אוקלידיים. אם כן, \( \mathbb{Z} \) הוא חוג אוקלידי עם הנורמה \( N\left(a\right)=\left|a\right| \) - הערך המוחלט. אולי אתם שואלים את עצמכם איך מוכיחים פורמלית את העובדה הזו שידענו עוד מאז שהיינו ילדים - איך מוכיחים שיש חילוק עם שארית ב-\( \mathbb{Z} \)? ובכן, הנה הוכחה פשוטה באינדוקציה. נ

ניח שאנחנו רוצים לחלק את \( n \) ב-\( b \). נניח ש-\( b \) קבוע ונבצע אינדוקציה על \( n \). ראשית, עבור \( n=0,1,\dots,b-1 \) הטענה נובעת מייד: \( n=b\cdot0+n \), וזה חוקי כי \( 0\le n<b \). אם כן, זה הבסיס שלנו. צעד האינדוקציה הוא כדלהלן: בהינתן \( n \), ניתן להפעיל את הנחת האינדוקציה על \( n-b \) ולקבל ש-\( n-b=qb+r \), כך ש-\( 0\le r<b \); מכאן נובע ש-\( n=\left(q+1\right)b+r \). פשוט, לא?

נעבור כעת לחוגים \( \mathbb{Z}\left[i\right] \) ו-\( \mathbb{R}\left[x\right] \). שניהם אוקלידיים, אבל עם אילו נורמות? הנורמה ב-\( \mathbb{Z}\left[i\right] \) היא ההכללה הטבעית של הערך המוחלט עבור מספרים מרוכבים: \( N\left(a+bi\right)=a^{2}+b^{2} \). כאן עלול להתקבל הרושם השגוי לפיו הנורמה הזו מראה שכל חוג שלמים הוא אוקלידי עם הנורמה הזו, או שכל חוג שלמים אוקלידי, אוקלידי עם הנורמה הזו. זה לא נכון! זה עובד ב-\( \mathbb{Z}\left[i\right] \) כי יש לנו מזל וכי זה חוג נחמד במיוחד, לא כחלק מאיזה עקרון גורף.

עבור פולינומים, הנורמה פשוטה עוד יותר. \( N\left(p\left(x\right)\right) \) היא פשוט הדרגה של \( p\left(x\right) \), כלומר החזקה הגבוהה ביותר של \( x \) שמופיעה בו. כאן באופן טבעי צצים איברים מנורמה 0: כל פולינום קבוע (כלומר, מספר ממשי). למעשה, הדרגה של פולינום האפס לרוב אינה מוגדרת, או מוגדרת להיות אינסוף, או מינוס אינסוף, או אלף ואחד דברים הזויים שאינם אפס, כך שזו דוגמה טובה לחוג שבו אנחנו ממש רוצים להימנע מלדבר על “הנורמה של אפס” (למרות שאפשר גם להגדיר אותה להיות אפס וזה לא ישנה כלום).

כמובן, סתם להגיד את הנורמה זה לא רציני. צריך גם להוכיח שקיים חילוק עם שארית בחוגים שתיארתי, עם הנורמה שתיארתי. אין כאן ארוחות חינם - כל הוכחה שכזו היא אתגר בפני עצמו עם טריקים משל עצמה. עם נורמות מתאימות גם \( \mathbb{Z}\left[\sqrt{-2}\right],\mathbb{Z}\left[\sqrt{-3}\right],\mathbb{Z}\left[\sqrt{-7}\right],\mathbb{Z}\left[\sqrt{-11}\right] \) הם חוגים אוקלידיים, אבל למשל החוג \( \mathbb{Z}\left[\sqrt{-5}\right] \) אינו חוג אוקלידי! למעשה, יש רק מספר סופי של חוגים אוקלידיים מהצורה \( \mathbb{Z}\left[\sqrt{D}\right] \) עבור \( D \) שלם. אני אסיים את הפוסט עם הצגת ההוכחות ש-\( \mathbb{Z}\left[i\right] \) ו-\( \mathbb{R}\left[x\right] \) הם חוגים אוקלידיים, אבל לפני כן אני רוצה לדבר קצת על מה שנובע מכך.

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

מה שאני רוצה להראות עכשיו הוא שכל חוג אוקלידי הוא בפרט תחום ראשי. ההוכחה קלילה עד להפתיע. יהא \( I\subseteq R \) אידאל (\( I \) הוא האידאל, \( R \) הוא חוג אוקלידי כלשהו). אז קיים ב-\( I \) איבר בעל נורמה מינימלית, \( d \). למה קיים כזה? כי הנורמות הן מספרים שלמים אי שליליים ולכן קיים להן מינימום. כמובן, ייתכן שיש באידאל הרבה איברים מנורמה מינימלית, אז נבחר אחד באופן שרירותי. אני טוען שאותו \( d \) יוצר את האידאל. כיוון אחד הוא מובן מאליו: בשל תכונת הבליעה, \( dr\in I \) לכל \( r\in R \), כך שהאידאל ש-\( d \) יוצר מוכל ב-\( I \). אבל למה כל איבר ב-\( I \) מתחלק ב-\( d \)? ובכן, יש לנו חילוק עם שארית כי \( R \) אוקלידי - הבה ונשתמש בו: אם \( a\in I \) הוא איבר כלשהו של האידאל, אז \( a=qd+r \), כך ש-\( r=0 \) או ש-\( N\left(r\right)<N\left(d\right) \). כעת, \( a\in I \) וגם \( qd\in I \) (מבליעה) ולכן \( r=a-qd\in I \). אבל בחרנו את \( d \) להיות איבר מנורמה מינימלית ב-\( I \), אז לא ייתכן ש-\( r \) (שראינו ששיך ל-\( I \)) הוא בעל נורמה קטנה מ-\( d \); מכאן ש-\( r=0 \) ולכן \( d \) מחלק את \( a \).

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

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

ראשית כל, פולינום הוא יצור שחי חיים כפולים: \( p\left(x\right)=x^{3}+2x+17 \) הוא מצד אחד ביטוי פורמלי עם איקס וחזקות וסכומים; ומצד שני הוא פונקציה - אפשר “להציב” בו ערכים ולראות מה מקבלים. אם \( p\left(a\right)=0 \) עבור \( a \) כלשהו, \( a \) נקרא “שורש” של הפולינום (לא במשמעות של \( \sqrt{p\left(x\right)} \), חלילה; זה עוד שימוש כפול מבלבל באותה מילה). השורשים של הפולינום הם המפתח לפירוק לגורמים שלו: אם \( p\left(x\right) \) הוא פולינום ו-\( a \) שורש שלו, אז \( \left(x-a\right) \) מחלק את \( p\left(x\right) \). בואו נראה איך מוכיחים את הטענה הזו, שנובעת ישירות מכך שהפולינומים הם חוג אוקלידי.

חוג אוקלידי אומר שניתן לחלק עם שארית, אז בואו נעשה את זה: \( p\left(x\right)=\left(x-a\right)\cdot q\left(x\right)+r\left(x\right) \). כעת, \( r\left(x\right) \) הוא אפס או פולינום מדרגה נמוכה יותר מ-\( x-a \) ומכיוון ש-\( x-a \) הוא פולינום מדרגה 1, אז \( r\left(x\right) \) הוא פולינום קבוע ולכן הוא בעצם מספר ממשי \( r \). כעת, אם נציב \( x=a \) במשוואה שקיבלנו, נקבל: \( 0=p\left(a\right)=\left(a-a\right)q\left(a\right)+r=r \), כלומר השארית חייבת להיות אפס, וזה מסיים בזריזות את ההוכחה.

התוצאה הזו מלמדת אותנו שכל פולינום \( p\left(x\right) \) ניתן לפירוק יחיד מהצורה \( p\left(x\right)=a\left(x-a_{1}\right)\left(x-a_{2}\right)\cdots\left(x-a_{n}\right) \) (ה-\( a \) שמחוץ לסוגריים הוא מספר ממשי ששווה למקדם של החזקה הגבוהה ביותר ב-\( p\left(x\right) \); מנקודת מבט אלגברית זה איבר הפיך ולכן “לא רלוונטי” כמו שכפל ב-1 ובמינוס 1 לא רלוונטי בפירוק לגורמים ראשוניים ב-\( \mathbb{Z} \)). לרוע המזל, החיים לא בהכרח פשוטים עד כדי כך - אני מסתמך כאן במובלע על ההנחה שלכל פולינום קיים שורש (ואז אפשר לחלק באיקס פחות השורש, לקבל פולינום מנה \( q\left(x\right) \) קטן יותר, גם לו למצוא שורש וכן הלאה) אבל זה תלוי ב”עולם” שבו אנו חיים. כך למשל לפולינום \( x^{2}+1 \) אין שורשים ממשיים ולכן כאיבר של \( \mathbb{R}\left[x\right] \), הוא עצמו ראשוני וזהו הפירוק שלו לגורמים. לעומת זאת, מעל \( \mathbb{C}\left[x\right] \) הפירוק שלו לגורמים ראשוניים יהיה \( \left(x+i\right)\left(x-i\right) \). אחת התוצאות החשובות באלגברה היא שלכל פולינום קיים שדה שבו הוא מתפרק לגורמים ממעלה 1 - שדה הפיצול של הפולינום; אבל לא אכנס לכך כעת.

לסיום, בואו נבין למה פולינומים ושלמים גאוסיים הם חוגים אוקלידיים. נתחיל מפולינומים. יש לנו שני פולינומים \( a\left(x\right),b\left(x\right) \); אנחנו רוצים למצוא שני פולינומים \( q\left(x\right),r\left(x\right) \) כך ש-\( a\left(x\right)=b\left(x\right)q\left(x\right)+r\left(x\right) \) ודרגת \( r\left(x\right) \) קטנה מדרגת \( b\left(x\right) \) (או ש-\( r\left(x\right)=0 \)). מה עושים?

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

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

אם כן, יהיו \( \alpha=a+bi \) ו-\( \beta=c+di \) שני שלמים גאוסיים כך ש-\( \beta\ne0 \). מה שנעשה יהיה לחלק אותם בכוח, ואז לאסוף את השברים מהרצפה. כשאני אומר לחלק בכוח, הכוונה היא לכך שנחשב את \( \frac{\alpha}{\beta} \) באופן ישיר:

\( \frac{\alpha}{\beta}=\frac{a+bi}{c+di}=\frac{a+bi}{c+di}\frac{c-di}{c-di}=\frac{ac+bd}{c^{2}+d^{2}}+\frac{bc-ad}{c^{2}+d^{2}}i=t+si \)

כלומר, קיבלנו ש-\( \frac{\alpha}{\beta} \) הוא מהצורה \( t+si \) כאשר \( t,s \) הם מספרים רציונליים (לא בהכרח שלמים, אחרת היינו יכולים לסיים כאן). למרבה המזל, לכל רציונלי יש מספר שלם שקרוב אליו - לכל היותר במרחק \( \frac{1}{2} \) ממנו. אז בואו וניקח את \( p,q \) להיות השלמים המתאימים: \( \left|t-p\right|\le\frac{1}{2} \) ו-\( \left|s-q\right|\le\frac{1}{2} \). אם כן, השלם הגאוסי \( p+qi \) נראה כמו הימור טוב להיות המנה של \( \alpha \) ו-\( \beta \) שתותיר את השארית הכי קטנה שאפשר (מבחינת הנורמה). אם כן, נכתוב \( \alpha=\left(p+qi\right)\beta+\gamma \) ומה שעלינו לברר הוא ש-\( N\left(\gamma\right)<N\left(\beta\right) \).

למקרה שזה לא ברור - \( \gamma \) מוגדר על ידי הנוסחה \( \gamma=\alpha-\left(p+qi\right)\beta \), ולכן גם מובטח לנו שהוא שלם גאוסי. מה שלא ברור הוא איך לחשב את הנורמה שלו. כדי להקל על החישוב הזה נמצא \( \theta \) מרוכב (לא בהכרח שלם גאוסי בעצמו) כך שיתקיים \( \gamma=\theta\beta \). זה יקל עלינו שכן הנורמה שבה אנו משתמשים בשלמים הגאוסים וניתנת להגדרה עבור כל מספר מרוכב מקיימת תכונה נחמדה (שבאופן כללי לא נהוג במיוחד לדרוש, למרות שלפעמים עושים זאת) - היא כפלית. כלומר בפרט \( N\left(\gamma\right)=N\left(\theta\right)N\left(\beta\right) \) (הכפליות ניתנת להוכחה בקלות יחסית אם שמים לב לכך שהנורמה הזו מקיימת \( N\left(\alpha\right)=\alpha\cdot\overline{\alpha} \) - כפל בצמוד המרוכב).

טוב, אז מהו אותו \( \theta \) מסתורי? לא קשה למצוא אותו אם שמים לב לכך ש-\( \alpha=\left(t+si\right)\beta \), כלומר \( \gamma=\left(t+si\right)\beta-\left(p+qi\right)\beta=\left[\left(t-p\right)+\left(s-q\right)i\right]\beta \), כלומר \( \theta=\left(t-p\right)+\left(s-q\right)i \). נותר רק לחסום את גודל הנורמה של \( \theta \) ולהראות שהוא קטן מ-1: \( N\left(\theta\right)=\left(t-p\right)^{2}+\left(s-q\right)^{2}\le\left|\frac{1}{2}\right|^{2}+\left|\frac{1}{2}\right|^{2}\le\frac{1}{2}<1 \). זה מסיים את ההוכחה (וגם מסביר למה עניין ה”קרוב עד כדי חצי” היה חשוב לנו).

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


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com