משפט השאריות הסיני

בית הספר “הר סיני” החליט להתעלל בשכבת כיתה י’ שלו ולארגן מהם קבוצות למשחק כדור זה או אחר. ראשית לקח בית הספר את כלל תלמידי השכבה והחל לחלק אותם לקבוצות כדורגל (11 שחקנים בקבוצה) אבל לרוע המזל התברר שנותר תלמיד אחד בלי קבוצה. טוב, אז בית הספר מיהר לחלק אותם לקבוצות כדורסל (5 שחקנים בקבוצה), אבל שוב נותר בחוץ תלמיד אחד. טוב, אז בית הספר ניסה עכשיו לחלק אותם לקבוצות בייסבול (9 שחקנים בקבוצה), אבל שוב נשאר בחוץ בדיוק תלמיד אחד. ידוע שיש בשכבה לא יותר מ-1000 תלמידים, ומספר התלמידים הוא זוגי - כמה תלמידים יש בשכבה?

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

לפני שנגיע אליו, בואו ננסה לפתור את החידה בצורה נאיבית. לצורך העניין נסמן את מספר התלמידים בשכבה ב-$latex x$. כעת, אמרו לנו שכאשר מנסים לחלק את $latex x$ ב-11, נשארים עם שארית 1. במתמטיקה יש סימון קומפקטי שבא לתאר את התופעה הזו: $latex x\equiv1\left(\mbox{mod 11}\right)$, שיש לקרוא כ”$latex x$ שקול ל-1 מודולו 11”. באופן כללי, $latex a\equiv b\left(\mbox{mod }n\right)$ פירושו שהשארית שמקבלים כאשר מחלקים את $latex a$ ב-$latex n$ שווה לשארית שמקבלים כשמחלקים את $latex b$ ב-$latex n$ (למשל, $latex 13\equiv31\left(\mbox{mod 6}\right)$). אפשר לראות בלי יותר מדי עבודה שהטענה “$latex a$ ו-$latex b$ מחזירים אותה שארית בחלוקה ב-$latex n$” שקולה לטענה “$latex a-b$ מתחלק ב-$latex n$” ולרוב את התנאי השני קל יותר לבדוק (וזו גם ההגדרה היותר מקובלת של הסימון של שקילות מודולו).

אני עצל למדי ולכן במקום לכתוב $latex x\equiv1\left(\mbox{mod 11}\right)$ (מה שהוא, כאמור, הסימון הסטנדרטי) אכתוב $latex x\equiv_{11}1$ (שהוא פחות סטנדרטי אבל פה ושם משתמשים בו) ובאופן כללי אכתוב $latex a\equiv_{n}b$ ואסמוך עליכם שתבינו למה אני מתכוון.

תכונה חשובה ביותר של משוואות מודולריות, שאשתמש בה הרבה בהמשך, היא שחוקי החיבור והכפל מתקיימים עבורן. כלומר, אם $latex a\equiv_{n}x$ ו-$latex b\equiv_{n}y$ אז

  1. $latex a+b\equiv_{n}x+y$
  2. $latex a\cdot b\equiv_{n}x\cdot y$

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

כעת אפשר לנסח את החידה שלעיל בלשון קצת יותר מתמטית: מהו $latex 1\le x\le1000$ המקיים:

$latex x\equiv_{11}1$

$latex x\equiv_{5}1$

$latex x\equiv_{9}1$

$latex x\equiv_{2}0$ (זו בעצם הדרישה “מספר התלמידים זוגי” - שהכנסתי כדי למנוע את הפתרון המטופש של “בשכבה יש תלמיד אחד”).

וכמובן, איך למצוא אותו?

במילים אחרות, מבקשים מאיתנו לפתור מערכת משוואות מודולריות. למצוא $latex x$ שפותר את כל המשוואות “בו זמנית”, אם קיים כזה. איך עושים את זה?

הדרך הנאיבית היא זו: אם $latex x\equiv_{11}1$ זה אומר ש-$latex x$ יכול להיות אחד מבין המספרים הבאים: $latex 1,12,23,34,\dots$ - הבנתם את הרעיון, מתחילים מ-1 ובכל פעם מוסיפים 11. כעת, אם $latex x\equiv_{5}1$ הוא יכול להיות אחד מבין המספרים הבאים: $latex 1,6,11,16,\dots$ וכן הלאה. בסופו של דבר נקבל ארבע קבוצות של מספרים, אחת לכל משוואה; ואז כל מה שצריך לעשות יהיה לחפש איבר שמופיע בכולן בו זמנית. רק מה, חיפוש כזה הוא דבר לא יעיל במיוחד. אפילו מאוד לא יעיל, ואילו אנחנו רוצים פתרון שהוא מהיר. זה אולי לא נראה כך כרגע, אבל פתרון משוואות מודולריות שכאלו הוא הלחם והחמאה של תורת המספרים האלגוריתמית, במובן זה שצריך לפתור משוואות מודולריות לעתים קרובות כחלק מאלגוריתם מסובך יותר.

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

  1. $latex a\equiv_{11}1$ וכמו כן $latex a$ מתחלק ב-$latex 5,9,2$.
  2. $latex b\equiv_{5}1$ וכמו כן $latex b$ מתחלק ב-$latex 11,9,2$.
  3. $latex c\equiv_{9}1$ וכמו כן $latex c$ מתחלק ב-$latex 11,5,2$.
  4. $latex d\equiv_{2}0$ וכמו כן $latex d$ מתחלק ב-$latex 11,5,9$ (ההפרדה כאן בין 2 ושאר המספרים אולי נראית מלאכותית אבל יש לה מטרה).

אני טוען שאם מצאתי את המספרים הללו, כמעט סיימתי: אני אגדיר $latex x=a+b+c+d$ ואקבל מספר שמקיים את כל ארבעת המשוואות המודולריות שלעיל. למה? כי בואו נשאל את עצמו, למשל, מהו $latex x$ מודולו 11. על פי חוקי החשבון המודולרי:

$latex x\equiv_{11}a+b+c+d\equiv_{11}1+0+0+0\equiv_{11}1$

מה בעצם קרה כשלקחנו את המשוואה מודולו 11? הגורמים של $latex b,c,d$ התפוגגו ואינם עוד, כי כולם התחלקו ב-11. האיבר היחיד שלא התחלק ב-11 היה $latex a$, ועבורו ידענו ספציפית שהוא מחזיר 1 מודולו 11. באותו האופן נקבל את התוצאה שאנחנו רוצים גם כשניקח את $latex x$ מודולו $latex 5,9$ או 2.

האם סיימנו? לא בהכרח, כי ייתכן ש-$latex x$ יהיה גדול מ-1000. במקרה הזה פשוט נחלק אותו ב-$latex 11\cdot5\cdot9\cdot2=990$ וניקח את השארית (שתהיה מספר בין 1 ל-990). למה זה עובד? ובכן, כי אם $latex x\equiv_{990}y$, אז בפרט גם $latex x\equiv_{11}y$ וכך גם עבור $latex 5,9,2$. למה? באופן כללי, אם $latex x\equiv_{n}y$, ויש לנו מספר $latex k$ שמחלק את $latex n$, אז מכיוון ש-$latex n$ מחלק את $latex x-y$ גם $latex k$ מחלק את $latex x-y$ (חלוקה היא יחס טרנזיטיבי). למי שחייב לראות את זה בעיניים הנה הוכחה קונקרטית: אם $latex n$ מחלק את $latex x-y$ זה אומר ש-$latex x-y=\alpha\cdot n$. עבור $latex \alpha$ שלם כלשהו. אם $latex k$ מחלק את $latex n$ זה אומר ש-$latex n=k\beta$ עבור $latex \beta$ שלם כלשהו. על כן, $latex x-y=\alpha\cdot\beta\cdot k$ ולכן $latex k$ מחלק את $latex x-y$.

יפה, אם כן, סיימנו לפתור את החידה, פרט לכך שעדיין אין לנו מושג איך למצוא את $latex a,b,c,d$ המדוברים.

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

אני לוקח את 990 - המכפלה של ארבעת המספרים שמשתתפים במשוואות המודולריות בתור “מה שמחלקים בו” - מה שאקרא לו מעכשיו המודולוסים. אני רוצה למצוא את $latex a$ ש”עובד” עבור המודולוס 11; אני אתחיל בכך שאחלק את 990 ב-11 ואקבל 90. כעת, 90 ו-11 הם מספרים זרים, כלומר אין להם אף מחלק משותף; זה מבטיח שאפשר למצוא מספר $latex y$ בעל התכונה $latex 90\cdot y\equiv_{11}1$. איך מוצאים כזה? בהמשך. לעת עתה אגלה לכם שבמקרה שלנו, $latex y=6$. אם כן, מהו $latex 90\cdot y$? חישוב קצר מראה לנו שזהו $latex 540=49\cdot11+1$. אני טוען שאם כן, $latex a=540$ הוא המספר שאנחנו מחפשים. ראינו לפני רגע שהוא מקיים $latex 540\equiv_{11}1$. למה הוא מתחלק ב-$latex 5,9,2$? ובכן, כי הגדרנו אותו בתור מכפלה של 90 בעוד משהו, ו-90 הוא בדיוק המכפלה של $latex 5,9,2$ ולכן ברור שמתחלק בכולם.

באותו האופן נטפל גם ב-$latex b$: נתחיל מ-990, נחלק אותו ב-5, נקבל 198, נשים לב לכך ש-$latex 396=198\cdot2$ מחזיר שארית 1 בחלוקה ב-5, ולכן $latex b=396$ הוא המספר שאנחנו רוצים. גם $latex c$ מטופל באותו האופן: מתחילים מ-990, מחלקים ב-9, מקבלים 110, שמים לב לכך ש-$latex 550=110\cdot5$ מחזיר שארית 1 בחלוקה ב-9 ולכן $latex c=550$.

ומה עם $latex d$? כמקודם, 990 חלקי 2 זה 495, אבל הפעם אנחנו רוצים לא 1 מודולו 2 אלא 0. טוב, אז כאן אפשר “לרמות” ופשוט לבחור $latex d=0$. בהמשך נראה שזו לא באמת רמאות אלא מה שבכל מקרה אמורים לעשות.

בסך הכל נקבל $latex x=540+396+550+0=1486$. זה יצא גדול יותר מ-990, אז כאמור - מחלקים ב-990 ולוקחים את השארית, כלומר $latex x=496$ הוא הפתרון שאנחנו מחפשים. אתם מוזמנים לעשות את החישוב ולראות שזה עובד.

בואו נסבך קצת את החידה. נניח שהיינו רוצים שישאר לא ילד אחד מודולו 11, אלא בדיוק שבעה? איך הפתרון היה משתנה אז? ובכן, לא בהרבה: $latex b,c,d$ שלנו הם עדיין בסדר. רק צריך למצוא $latex a$ כך ש-$latex a\equiv_{11}7$ ועדיין מתחלק ב-2,9,5.

עכשיו, ראינו כבר ש-$latex 540\equiv_{11}1$. לכן, אם נכפול את שני האגפים ב-7, נקבל $latex 540\cdot7\equiv_{11}7$, וברור ש-$latex 540\cdot7$ מתחלק ב-$latex 5,9,2$ (כי 540 התחלק בהם). לכן $latex a=540\cdot7=3780$ הוא המספר שאנו רוצים. נקבל ש-$latex a+b+c+d=4726$, ואחרי חלוקה ב-990 והוצאת שארית נקבל 766 תלמידים בשכבה. אתם מוזמנים לבדוק שהמספר הזה עובד טוב.

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

$latex x\equiv_{4}3$

$latex x\equiv_{8}6$

למערכת הזו אין שום סיכוי שיהיה פתרון. למה? כי אם $latex x-6$ מתחלק ב-8, אז הוא בפרט מתחלק ב-4, כלומר $latex x\equiv_{4}6\equiv_{4}2$, אבל זה עומד בסתירה לכך ש-$latex x\equiv_{4}3$ - הרי איקס לא יכול להחזיר גם שארית 2 וגם שארית 3 בחלוקה ב-4!

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

$latex x\equiv_{6}3$

$latex x\equiv_{15}7$

כאן המודולוסים בוודאי לא מחלקים אחד את השני. מצד שני, 3 מחלק את שניהם! המשוואה הראשונה גוררת ש-$latex x\equiv_{3}0$ והשני גוררת ש-$latex x\equiv_{3}1$, ושוב קיבלנו סתירה. במילים אחרות, עלולה להיות לנו בעיה אם יש שני מודולוסים שיש מספר שמחלק את שניהם גם יחד. מספרים שלמים שהמספר הגדול ביורת שמחלק את שניהם גם יחד הוא 1 נקראים זרים; התקווה היא שאם כל המודולוסים הם זרים זה לזה (כלומר, לכל זוג מודולוסים, אין לו מחלק משותף שגדול מ-1) אז כל מערכת משוואות עם אותם מודולוסים תהיה פתירה. התקווה הזו התגשמה: בואו ננסח את משפט השאריות הסיני באופן מדויק.

אם כן, יהיו מספרים שלמים $latex m_{1},m_{2},\dots,m_{k}$ שכולם זרים בזוגות (לכל זוג $latex m_{i},m_{j}$, המחלק המשותף הגדול ביותר שלהם הוא 1). בנוסף, יהיו גם מספרים שלמים $latex a_{1},\dots,a_{k}$ כלשהם. נסמן $latex m=m_{1}m_{2}\cdots m_{k}$ (המכפלה של כל המודולסים). אז משפט השאריות הסיני אומר שלמערכת המשוואות הבאה:

$latex x\equiv_{m_{1}}a_{1}$

$latex \vdots$

$latex x\equiv_{m_{k}}a_{k}$

יש פתרון בתחום $latex 0\le x<m$ והפתרון הזה הוא יחיד בתחום הזה (ולכן קבוצת כל הפתרונות למשוואה היא הקבוצה $latex \left\{ x+tm\ |\ t\in\mathbb{Z}\right\} $, אבל זה פחות חשוב).

ההוכחה של המשפט הכללי דומה לפתרון של המקרה הפרטי. קודם כל נוכיח שבכלל יש פתרון, כי זה העיקר. לכל $latex i$, נגדיר $latex n_{i}=\frac{m}{m_{i}}$, כלומר המכפלה של כל המודולוסים חוץ מ-$latex m_{i}$. כעת, $latex m_{i}$ ו-$latex n_{i}$ הם זרים (כי $latex m_{i}$ זר לכל הגורמים של $latex n_{i}$). מכאן נובע (לזה אתייחס בהמשך) שקיים מספר $latex d_{i}$ כך ש-$latex n_{i}d_{i}\equiv_{m_{i}}1$. בואו לצורך נוחות בלבד נסמן $latex e_{i}=n_{i}d_{i}$. שימו לב ש-$latex e_{i}$ מקיים את התכונה הבאה:

$latex e_{i}\equiv_{m_{j}}\delta_{ij}$, כאשר $latex \delta_{ij}$ הוא הדלתא של קרונקר:

$latex \delta_{ij}=\begin{cases}1 & i=j\\0 & i\ne j\end{cases}$

כעת, נגדיר את הפתרון למערכת המשוואות: $latex x=a_{1}e_{1}+a_{2}e_{2}+\dots+a_{k}e_{k}$ (מודולו $latex m$). כדי לראות שזה הפתרון המבוקש נשים לב לכך ש-$latex x\equiv_{m_{i}}a_{1}\delta_{1i}+\dots+a_{k}\delta_{ik}=a_{i}$, כנדרש.

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

זה מוכיח שהפתרון קיים. בשביל יחידות, נניח ש-$latex x,y$ הם שני פתרונות למערכת המשוואות. אז לכל $latex i$ מתקיים $latex x-y\equiv_{m_{i}}a_{i}-a_{i}\equiv_{m_{i}}0$, כלומר $latex m_{i}$ מחלק את $latex x-y$ לכל $latex i$. עכשיו, אם מספרים זרים מחלקים מספר כלשהו, גם המכפלה של כולם מחלקת את אותו מספר, ולכן נקבל ש-$latex m$ מחלק את $latex x-y$, כלומר $latex x\equiv_{m}y$, וסיימנו את הוכחת המשפט.

מה שחסר לי עדיין הוא הטענה הבאה, שעזרה לי למצוא את ה-$latex d_{i}$-ים: אם $latex a,n$ הם מספרים זרים אז קיים $latex x$ כך ש-$latex ax\equiv_{n}1$. הסיבה שהמתנתי עם הטענה הזו היא שזוהי טענה בסיסית עוד יותר בתורת המספרים שמשתמשים גם בה בכל מקום אפשרי בערך, ומדברים עליה בהקשרים רחבים הרבה יותר ממשפט השאריות הסיני. בבסיסה, הטענה הזו נובעת ממה שמכונה האלגוריתם האוקלידי שהקדשתי לו פוסט כאן. האלגוריתם הזה מאפשר, בהינתן שני מספרים שלמים $latex a,b$ שהמחלק המשותף הגדול ביותר שלהם הוא $latex d$, למצוא שני מספרים שלמים $latex x,y$ כך ש-$latex ax+by=d$; במקרה שלנו, שבו $latex a,n$ הם זרים, נקבל שיש $latex x,y$ כך ש-$latex ax+ny=1$, וכשניקח את המשוואה הזו מודולו $latex n$ נקבל $latex ax\equiv_{n}1$. במילים אחרות, מציאת ה-$latex d_{i}$-ים המדוברת היא בסך הכל הפעלה של האלגוריתם האוקלידי (שהוא אלגוריתם מאוד מהיר).

שימו לב לעוד אבחנה מעניינת: ה-$latex e_{i}$-ים שצצו בהוכחת המשפט אינם תלויים ב-$latex a_{i}$-ים, אלא רק במודולוסים $latex m_{i}$. זה אומר שאפשר לחשב אותם פעם אחת ולשמור בצד, ומרגע זה ואיך אפשר לפתור ביעילות כל מערכת משוואות מודולו $latex m_{1},\dots,m_{k}$ (לכל בחירה של $latex a_{1},\dots,a_{k}$) בזמן קצר ביותר, בלי שיהיה צורך להפעיל שוב את האלגוריתם האוקלידי. (רק צריך לחשב את $latex a_{1}e_{1}+a_{2}e_{2}+\dots+a_{k}e_{k}$, כלומר לבצע פעולה אחת של מכפלה סקלרית - וזה ממש ממש מהיר).

אם לחזור לחידה שבתחילת הפוסט, עכשיו ברור מה עשיתי שם - ראשית חשבתי על משחקי שבהם מספרי השחקנים הם מספרים זרים זה לזה (11 ו-5 באו מאליהם; כדי שיהיה מעניין הכנסתי גם את 9 לעניין). הבעיה הייתה שהחידה עם המודולוסים הללו הייתה בעלת הפתרון הלא מעניין “1” ולכן הכנסתי גם את 2 לתמונה. מכיוון שהמכפלה של כל המודולוסים יצאה 990, אמרתי שאין בשכבה יותר מ-1,000 תלמידים, כי היה מובטח לי שיש פתרון שקטן מ-990.

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

נתחיל מהחוג $latex \mathbb{Z}_{n}$ - השלמים מ-0 עד $latex n-1$ עם חיבור וכפל מודולו $latex n$. זה בעצם המבנה האלגברי ש”עוטף” את החשבון המודולרי שדיברתי עליו קודם. את משפט השאריות הסיני אפשר לנסח מחדש בתור משפט על המבנה של $latex \mathbb{Z}_{n}$. אם $latex n=m_{1}\cdot m_{2}\cdots m_{k}$ כאשר כל ה-$latex m_{i}$-ים זרים זה לזה, אז משפט השאריות הסיני אומר ש-$latex \mathbb{Z}_{n}\cong\mathbb{Z}_{m_{1}}\times\dots\times\mathbb{Z}_{m_{k}}$, כלומר $latex \mathbb{Z}_{n}$ איזומורפי למכפלה הקרטזית של ה-$latex \mathbb{Z}_{m_{i}}$-ים. אם אתם לא מכירים את המושגים הללו, לצערי תתקשו להבין את הניסוח הזה, אבל אלו לא מושגים מורכבים עד כדי כך.

ההוכחה של המשפט היא קונסטרוקטיבית - אפשר להציג את האיזומורפיזם ישירות. באופן לא מפתיע, האיזומורפיזם הוא פשוט $latex a\mapsto\left(a_{1},\dots,a_{k}\right)$ כאשר $latex a_{i}=a\mbox{ mod }m_{i}$. לא קשה להראות שזה אכן הומומורפיזם; עיקר העבודה היא להראות שהוא חח”ע ועל, אבל זה בדיוק מה שמשפט השאריות הסיני נותן לנו: הוא אומר שלכל $latex \left(a_{1},\dots,a_{k}\right)$ אפשר למצוא $latex a$ שמתמפה אליו (זה הפתרון למערכת המשוואות המודולרית שמוגדרת עבור $latex \left(a_{1},\dots,a_{k}\right)$), והוא אומר לנו שהפתרון הזה הוא יחיד, כלומר שאם שני איברים מתמפים לאותו $latex \left(a_{1},\dots,a_{k}\right)$ הם חייבים להיות זהים. זה סוף הסיפור.

אבל אתם מכירים מתמטיקאים. אם הכללנו משהו וההכללה עובדת טוב, למה לא להכליל עוד? כרגע המשפט מנוסח רק על החוגים $latex \mathbb{Z}_{n}$, אבל למה לא לקחת את זה צעד אחד קדימה?

עד כה זירת המשחק שלנו הייתה $latex \mathbb{Z}$, המספרים השלמים. ההכללה הטבעית של $latex \mathbb{Z}$ היא חוג קומוטטיבי עם יחידה $latex R$. כעת, מה היחס בין $latex \mathbb{Z}_{n}$ ובין $latex \mathbb{Z}$? פשוט מאוד - $latex \mathbb{Z}_{n}$ הוא חוג מנה של $latex \mathbb{Z}$ שמתקבל על ידי חלוקה באידאל $latex n\mathbb{Z}=\left\{ na\ |\ a\in\mathbb{Z}\right\} $ (כלומר, $latex \mathbb{Z}_{n}=\mathbb{Z}/n\mathbb{Z}$). אם כן, יהיו $latex A_{1},\dots,A_{k}$ אידאלים ב-$latex R$ (תתי-חוגים שבולעים ביחס לפעולת הכפל, כלומר $latex ar\in A$ לכל $latex a\in A$ ו-$latex r\in R$), והאנלוגים של $latex \mathbb{Z}_{m_{i}}$ יהיו חוגי המנה $latex R/A_{i}$.

אנו נזקקים לאנלוג לתכונת ה-“ה-$latex m_{i}$-ים זרים בזוגות”. אין משמעות לאמירה כמו “ה-$latex A_{i}$-ים זרים בזוגות” כי “זר” דורש מושג של חלוקה שלא קיים באידאלים באופן כללי. לכן אולי כדאי לנסות ולהיזכר למה היה לנו צורך שה-$latex m_{i}$-ים יהיו זרים בזוגות ולהכליל את התכונה הזו לחוגים. הצורך היה כדי שנוכל להשתמש בטענה המתמטית ההיא על כך שאם $latex a,b$ זרים אז קיימים $latex x,y$ כך ש-$latex ax+by=1$. כשזה מנוסח בלשון ה-$latex \mathbb{Z}_{n}$-ים, זו בעצם הטענה שאם $latex a,b$ זרים אז $latex a\mathbb{Z}+b\mathbb{Z}=\mathbb{Z}$, כשחיבור אידאלים הוא במובן הטבעי המתבקש - איברי הסכום של האידאלים הם סכומים של איבר מהאידאל הראשון ואיבר מהאידאל השני.

את התכונה הזו נכליל: נאמר ששני אידאלים של $latex R$, $latex A,B$ הם קו-מקסימליים אם $latex A+B=R$ (אני לא בטוח אם יש שם טוב יותר בעברית; באנגלית comaximal הוא שם מצויין שכן “זרים בזוגות” הוא coprime, וב-$latex \mathbb{Z}$ אידאל ראשוני הוא בפרט אידאל מקסימלי).

עכשיו, איך $latex \mathbb{Z}_{n}$ קשור ל-$latex \mathbb{Z}_{m_{i}}$-ים במשפט המקורי? בכך ש-$latex n$ הוא המכפלה של כל ה-$latex m_{i}$-ים. צריך למצוא אנלוג גם לזה, ולמרבה המזל אחד כזה מגיע באופן טבעי (שלא יפתיע אף אחד שמכיר את האופן שבו אידאלים מכלילים, רעיונית, מספרים שלמים; דיברתי על זה בעבר בבלוג). המושג המתאים הוא מכפלה של אידאלים, שמוגדרת באופן שהוא אולי קצת קשה לעיכול ממבט ראשון: המכפלה $latex A_{1}A_{2}\cdots A_{k}$ מוגדרת בתור קבוצת כל הסכומים הסופיים של מכפלות מהצורה $latex a_{1}\cdots a_{k}$ כאשר $latex a_{i}\in A_{k}$. תרגיל טוב כדי לעכל את ההגדרה הזו היא להוכיח לעצמכם ש-$latex m_{1}\mathbb{Z}\cdots m_{k}\mathbb{Z}=n\mathbb{Z}$.

כעת אפשר לנסח את משפט השאריות הסיני בניסוח האלגברי הכללי שלו:

אם $latex R$ הוא חוג קומוטטיבי עם יחידה ו-$latex A_{1},\dots,A_{k}$ הם אידאלים ב-$latex R$ שהם קו-מקסימליים בזוגות, אז $latex R/A_{1}\cdots A_{k}\cong R/A_{1}\times\dots\times R/A_{k}$.

ההוכחה, שלא במפתיע, היא בעצם אותה הוכחה שכבר ראינו, פרט לכך שאפשר קצת לפשט אותה בגלל המסגרת הכללית של תורת החוגים, אבל גם צריך לעבוד טיפה כדי להוכיח דברים שעבור שלמים אני מניח כמעט כמובנים מאליהם. הדבר המרכזי שאני צריך לעשות הוא להוכיח שאם $latex A_{1},\dots,A_{k}$ הם קו-מקסימליים בזוגות, אז לכל $latex i$, $latex A_{i}$ ו-$latex \prod_{j\ne i}A_{j}$ (כלומר, האדיאל שהוא מכפלת כל האידאלים $latex A_{1},\dots,A_{k}$ פרט ל-$latex A_{i}$) הם קו-מקסימליים בזוגות. כדי להוכיח את זה מספיק להוכיח טענה פשוטה קצת יותר: אם $latex A,B,C$ הם אידאליים קו-מקסימליים בזוגות, אז $latex A$ ו-$latex BC$ קו-מקסימליים; אחרי שהוכחתי את זה אפשר להוכיח את הטענה הכללית באינדוקציה (בכל פעם $latex B$ יהיה מכפלה של כמה אידאלים ו-$latex C$ יהיה אידאל חדש שרוצים לצרף למכפלה).

מכיוון שאנחנו בחוג עם יחידה, די להראות שקיימים $latex a\in A$ ו-$latex b\in B$, $latex c\in C$ כך ש-$latex a+bc=1$ כדי להוכיח ש-$latex A$ ו-$latex BC$ הם קו-מקסימליים. מתוך ההנחה שלנו, אנחנו יודעים שמתקיים $latex a_{1}+b=1$ ו-$latex a_{2}+c=1$ עבור $latex a_{1},a_{2}\in A$ ו-$latex b\in B$, $latex c\in C$ כלשהם; נכפול אותם ונקבל $latex a_{1}a_{2}+a_{1}c+a_{2}b+bc=1$, וסכום שלושת האיברים הראשונים הוא איבר ב-$latex A$ (במילים אחרות, $latex a=a_{1}a_{2}+a_{1}c+a_{2}b$), כך שסיימנו.

כעת נעבור להוכחת משפט השאריות הסיני עצמו. מספיק להוכיח קיום של הומומורפיזם על $latex R\to R/A_{1}\times\dots\times R/A_{k}$ שהגרעין שלו הוא $latex A_{1}\cdots A_{k}$ והתוצאה תנבע ממשפט האיזומורפיזם הראשון לחוגים. ההומומורפיזם, שלא במפתיע, יהיה $latex r\mapsto\left(r+A_{1},\cdots,r+A_{k}\right)$. אם $latex r$ התמפה ל-$latex 0$, אז $latex r\in A_{i}$ לכל $latex i$, כלומר $latex r\in A_{1}\cap\cdots\cap A_{k}$, ומכאן קל לראות שהגרעין הוא $latex A_{1}\cap\cdots\cap A_{k}$ (ברור שכל איבר של $latex A_{1}\cap\cdots\cap A_{k}$ יתמפה לאפס).

כעת, $latex A_{1}\cap\cdots\cap A_{k}=A_{1}\cdots A_{k}$ במקרה הנוכחי, שבו כל זוג $latex A_{i}$-ים הם קו-מקסימליים; זה האנלוג של העובדה עבור מספרים שלמים ש-$latex \mbox{lcm}$ (כפולה משותפת מינימלית) של מספרים שלמים שווה למכפלה שלהם אם כולם זרים. בכיוון אחד, כל איבר של $latex A_{1}\cdots A_{k}$ בוודאי שייך לכל אחד מהאידאלים, בשל תכונת הבליעה שלהם (מי שמורכב ממכפלה של איבר ב-$latex A_{i}$ ועוד דברים על בטוח יהיה ב-$latex A_{i}$, וגם סכומים של איברים כאלו). בכיוון השני בואו ניקח איבר $latex c\in A_{1}\cap\cdots\cap A_{k}$ ונוכיח ש-$latex c\in A_{1}\cdots A_{k}$.

כעת, $latex A_{1}$ ו-$latex A_{2}A_{3}\cdots A_{k}$ הם קו-מקסימליים, כך שקיימים $latex a\in A_{1}$ ו-$latex b\in A_{2}A_{3}\cdots A_{k}$ כך ש-$latex 1=a+b$. נכפול את שני האגפים ב-$latex c$ ונקבל $latex c=ca+cb$. ברור לנו ש-$latex cb\in A_{1}\cdots A_{k}$ כי הוא מכפלה של איבר מ-$latex A_{1}$ ($latex c$) עם איבר מ-$latex A_{2}\cdots A_{k}$ ($latex b$), לכן נותר להוכיח ש-$latex ca\in A_{1}\cdots A_{k}$, ולצורך כך מספיק להראות ש-$latex c\in A_{2}\cdots A_{k}$, כלומר צמצמנו את הבעיה ממכפלה של $latex k$ איברים למכפלה של $latex k-1$ איברים וניתן להמשיך לעשות זאת עד אשר נגיע לאידאל בודד שעבורו הטענה טריוויאלית.

כל מה שנותר לעשות הוא להראות שההומומורפיזם שהגדרתי לעיל הוא באמת הומומורפיזם (אוותר על התענוג, זה לא קשה) ושהוא על. להוכיח שהוא על זה בדיוק, אבל בדיוק כמו במשפט ה”קלאסי”: לכל $latex A_{i}$, אנחנו יודעים שהוא קו-מקסימלי עם $latex B=\prod_{j\ne i}A_{j}$ (אני משתמש כאן ב-$latex B$ לצורכי נוחות בלבד). אז קיימים $latex x_{i}\in A_{i},e_{i}\in B$ כך ש-$latex x_{i}+e_{i}=1$, או בלשון קוסטים, $latex e_{i}+A_{i}=1+A_{i}$.

כעת, יהא וקטור $latex \left(a_{1}+A_{1},\dots,a_{k}+A_{k}\right)$ של קוסטים. נגדיר $latex r=a_{1}e_{1}+\dots+a_{k}e_{k}$. מהו $latex r+A_{i}$? ובכן, לכל $latex e_{j}$ עבור $latex j\ne i$ אנחנו יודעים ש-$latex e_{j}$ שייך למכפלה של אידאלים שכוללים את $latex A_{i}$ ולכן $latex e_{j}\in A_{i}$ ולכן $latex a_{j}e_{j}\in A_{i}$ והגורם הזה נבלע בתוך $latex A_{i}$ (האנלוג עבור $latex \mathbb{Z}_{m_{i}}$ היה התאפסות), ואילו עבור $latex e_{i}$ אנחנו יודעים ש-$latex e_{i}+A_{i}=1+A_{i}$ ולכן $latex a_{i}e_{i}+A_{i}=a_{i}+A_{i}$ - בדיוק מה שרצינו. זה מסיים את ההוכחה.

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


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

Buy Me a Coffee at ko-fi.com