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

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

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

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

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

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

1. \( a+b\equiv_{n}x+y \)
2. \( a\cdot b\equiv_{n}x\cdot y \)

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

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

\( x\equiv_{11}1 \)

\( x\equiv_{5}1 \)

\( x\equiv_{9}1 \)

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

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

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

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

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

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

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

\( x\equiv_{11}a+b+c+d\equiv_{11}1+0+0+0\equiv_{11}1 \)

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

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

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

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

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

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

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

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

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

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

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

\( x\equiv_{4}3 \)

\( x\equiv_{8}6 \)

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

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

\( x\equiv_{6}3 \)

\( x\equiv_{15}7 \)

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

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

\( x\equiv_{m_{1}}a_{1} \)

\( \vdots \)

\( x\equiv_{m_{k}}a_{k} \)

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

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

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

\( \delta_{ij}=\begin{cases}1 & i=j\\0 & i\ne j\end{cases} \)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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