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

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

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

המשפט עבור משוואות מודולריות

נניח ש- $\ m_{1},m_{2},\dots ,m_{k}$ הם מספרים טבעיים זרים בזוגות (כלומר, המחלק המשותף המקסימלי של כל שניים מהם הוא 1). אז בהינתן מספרים שלמים כלשהם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_1, a_2,\dots ,a_k } , (כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_i } נמצא בקבוצת השאריות מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_i } ) יש למערכת המשוואות (קונגרואנציות)

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \equiv a_i \pmod{m_i} \quad\mathrm{for}\; i = 1, \cdots, k.}

פתרון, ויתר על כן, כל שני פתרונות הם שקולים מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m=m_1\cdot m_2\cdots m_k } (כלומר, הפתרון יחיד מודולו m).

בניסוח אחר, מופשט יותר, המשפט קובע שהחוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mathbb{Z}/(m_1 \cdots m_k)\mathbb{Z}} איזומורפי לסכום הישר של החוגים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mathbb{Z}/m_1\mathbb{Z} \oplus \dots \oplus \mathbb{Z}/m_k \mathbb{Z}} .

הוכחה

רעיון ההוכחה הוא למצוא בסיס בו מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_i} הם 1 ומודולו $m_{j}$ (כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j \ne i} ) הם 0. תוצאות אלה בונות בסיס למרחב הפתרונות, והפתרון המבוקש הוא צירוף-ליניארי של איברי-בסיס עם המקדמים-החופשיים במשוואות-המודולריות.

נגדיר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n_i = m / m_i} ואז מתקיים ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n_i , m_i} זרים (מאחר ש-m_i זר לכל גורם במכפלה המרכיבה את n_i. אם הם לא היו זרים היה מספר ראשוני המחלק את שניהם, ובפרט את אחד הגורמים במכפלה, ואז היה מתקבל מספר ראשוני המחלק הן את m_i והן m_j אחר, בסתירה להנחה). כיוון שהם זרים, קיימים r_i ו s_i עבורם:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r_i m_i + s_i n_i = 1} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_i n_i \equiv 1 \pmod{m_i}} .

כעת נגדיר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e_i = n_i s_i} ואז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e_i \equiv 1 \pmod{m_i}} . בנוסף, לכל j ששונה מ - i, $\ e_{i}\equiv 0{\pmod {m_{j}}}$ כי m_j מחלק את n_i.

בנינו בסיס למערכת המשוואות. נסכם בעזרת הדלתא של קרונקר:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n_i s_i = e_i \equiv \delta_{ij} \pmod{m_j}}

באמצעותו קל לבנות את הפתרון, שהוא:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x = \sum_{i=1}^{k}{ a_i e_i}}

שכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \pmod{m_j} x = \sum_i {a_i e_i} \equiv \sum_i {a_i \delta_{ij}} \equiv a_j } כנדרש.

לסיום, יהי y פתרון אחר, אזי לכל i מתקיים ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_i | x-y } ומאחר שכל ה-m_i זרים נובע שגם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m | x-y} ומכאן ששני הפתרונות שקולים מודולו m.

בכך הסתיימה ההוכחה, שמציגה גם אלגוריתם מהיר לפתרון מערכת קונגרואנציות. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \blacksquare}

דוגמה

נפתור את מערכת המשוואות הבאה:

1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \equiv 2 \pmod 3}
2. $x\equiv 1{\pmod {5}}$

כאן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_1 = 3 \ , \ m_2 = 5} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_1 = 5 \ , \ n_2 = 3} .

נשים לב ש-

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_1 s_1 = 5 \times 2 = 10 \equiv 1 \pmod 3}

ו-

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_2 s_2 = 3 \times 2 = 6 \equiv 1 \pmod 5}

ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_1 = 10 \ , e_2 = 6} . מצאנו את הבסיס ולכן הפתרון הוא

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \equiv a_1 e_1 + a_2 e_2 = 2 e_1 + e_2 =2 \times 10 + 6 \times 1 = 26 \equiv 11 \pmod {15}} .

נוודא שזה אכן פתרון, ואכן: $11\equiv 2\ ({\bmod {3}})$ ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 11 \equiv 1 \ ( \bmod 5 )} .

מסקנה: האיזומורפיזם בין החוגים

מסקנה של המשפט היא ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mathbb{Z}/(m_1\cdots m_k)\mathbb{Z} \cong \mathbb{Z}/m_1\mathbb{Z} \oplus \dots \oplus \mathbb{Z}/m_k \mathbb{Z} } .

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \mathbb{Z}/m_1\dots m_k\mathbb{Z} } , אפשר לשכן אותו ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}/m_1\mathbb{Z} \oplus \dots \oplus \mathbb{Z}/m_k \mathbb{Z}} על ידי

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \mapsto \left( x \ \mathrm{ mod } \ m_1 ,..., x \ \mathrm{mod} \ m_k \right)}

ובכיוון ההפוך, יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( a_1 , ... , a_k \right) \in \mathbb{Z}/m_1\mathbb{Z} \oplus \dots \oplus \mathbb{Z}/m_k \mathbb{Z}} . לפי משפט השאריות הסיני קיים $x\in \mathbb {Z} /(m_{1}\cdots m_{k})\mathbb {Z}$ כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall j = 1,...,k : x \equiv a_j \pmod{m_j}} , ולכן נתאים

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( a_1 , ..., a_k \right) \mapsto x}

כאשר x הוא זה שמתקבל ממשפט השאריות הסיני והוא יחיד עד כדי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = m_1 \cdot ... \cdot m_k} .

שתי ההתאמות הללו הן הומומורפיזמים הופכיים אחד של השני ולכן מגדירות איזומורפיזם בין שני החוגים.

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

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R} חוג עם יחידה (לאו דווקא קומוטטיבי). נניח שהאידיאלים $\ I_{1},\dots ,I_{k}$ הם זרים בזוגות (או "מקסימליים הדדית"), כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ I_i+I_j = R} לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i\neq j} . אז חוג המנה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R/(I_1 \cap \dots \cap I_k)} איזומורפי, לפי ההטלה הטבעית, לסכום הישר של החוגים $\ R/I_{1}\oplus \dots \oplus R/I_{k}$. בפרט, אם R קומוטטיבי והאידיאלים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ I_1,\dots,I_k} כולם אידיאלים מקסימליים ושונים זה מזה, אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R/(I_1 \cap \dots \cap I_k)} הוא מכפלה ישרה של שדות.

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

• משפט השאריות הסיני באתר howMath
• גדי אלכסנדרוביץ', משפט השאריות הסיני, באתר "לא מדויק", 12 בספטמבר 2012
• משפט השאריות הסיני, באתר אנציקלופדיה למתמטיקה (באנגלית)
• משפט השאריות הסיני, באתר MathWorld (באנגלית)
• משפט השאריות הסיני, באתר אנציקלופדיה בריטניקה (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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