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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

המשפט עבור משוואות מודולריות[עריכת קוד מקור | עריכה]

נניח ש-  \ m_1, m_2,\dots ,m_k הם מספרים טבעיים זרים בזוגות (כלומר, המחלק המשותף המקסימלי של כל שניים מהם הוא 1). אז בהינתן מספרים שלמים כלשהם  \ a_1, a_2,\dots ,a_k , (כאשר  \ a_i נמצא בקבוצת השאריות מודולו  \ m_i ) יש למערכת המשוואות (קונגרואנציות)

x \equiv a_i \pmod{m_i} \quad\mathrm{for}\; i = 1, \cdots, k.

פתרון, ויתר על כן, כל שני פתרונות הם שקולים מודולו  \ m=m_1\cdot m_2\cdots m_k (כלומר, הפתרון יחיד מודולו m).

בניסוח אחר, מופשט יותר, המשפט קובע שהחוג \ \mathbb{Z}/m_1\dots m_k\mathbb{Z} איזומורפי לסכום הישר של החוגים \ \mathbb{Z}/m_1\mathbb{Z} \oplus \dots \oplus \mathbb{Z}/m_k \mathbb{Z}.

הוכחה[עריכת קוד מקור | עריכה]

רעיון ההוכחה הוא למצוא בסיס כך שמודולו m_i מקבלים 1 ומודולו m_j (כאשר j \ne i) מקבלים 0. כך בונים בסיס למרחב הפתרונות, והפתרון המבוקש הוא צירוף לינארי של איברי בסיס עם המקדמים החופשיים במשוואות המודולריות.

נגדיר \ n_i = m / m_i ואז מתקיים ש \ n_i , m_i זרים (מאחר ו-mi זר לכל גורם במכפלה המרכיבה את ni. אם הם לא היו זרים היה מספר ראשוני המחלק את שניהם, ובפרט את אחד הגורמים במכפלה, ואז היינו מקבלים ראשוני המחלק הן את mi והן mj אחר, בסתירה להנחה). מכיוון שהם זרים, קיימים ri ו si כך ש

\ r_i m_i + s_i n_i = 1 או \ s_i n_i \equiv 1 \pmod{m_i}.

כעת נגדיר \ e_i = n_i s_i ואז \ e_i \equiv 1 \pmod{m_i}. בנוסף, לכל j ששונה מ - i, \ e_i \equiv 0 \pmod{m_j} כי mj מחלק את ni.

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

\ n_i s_i = e_i \equiv \delta_{ij} \pmod{m_j}

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

\ x = \sum_{i=1}^{k}{ a_i e_i}

שכן \ \pmod{m_j} x = \sum_i {a_i e_i} \equiv \sum_i {a_i \delta_{ij}} \equiv a_j כנדרש.

לסיום, יהי y פתרון אחר, אזי לכל i מתקיים ש \ m_i | x-y ומאחר שכל ה-mi זרים נובע שגם \ m | x-y ומכאן ששני הפתרונות שקולים מודולו m.

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

דוגמה[עריכת קוד מקור | עריכה]

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

  1. x \equiv 2 \pmod 3
  2. x \equiv 1 \pmod 5

כאן m_1 = 3 \ , \ m_2 = 5 ו-n_1 = 5 \ , \ n_2 = 3.

נשים לב ש-

n_1 s_1 = 5 \times 2 = 10 \equiv 1 \pmod 3

ו-

n_2 s_2 = 3 \times 2 = 6 \equiv 1 \pmod 5

ולכן e_1 = 10 \ , e_2 = 6. מצאנו את הבסיס ולכן הפתרון הוא

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 ) ו- 11 \equiv 1 \ ( \bmod 5 ).

מסקנה: האיזומורפיזם בין החוגים[עריכת קוד מקור | עריכה]

מסקנה של המשפט היא ש-\ \mathbb{Z}/m_1\dots m_k\mathbb{Z} \cong \mathbb{Z}/m_1\mathbb{Z} \oplus \dots \oplus \mathbb{Z}/m_k \mathbb{Z} .

יהי x \in \mathbb{Z}/m_1\dots m_k\mathbb{Z} , אפשר לשכן אותו ב-\mathbb{Z}/m_1\mathbb{Z} \oplus \dots \oplus \mathbb{Z}/m_k \mathbb{Z} על ידי

 x \mapsto \left( x \ \mathrm{ mod } \ m_1 ,..., x \ \mathrm{mod} \ m_k \right)

ובכיוון ההפוך, יהי  \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\dots m_k\mathbb{Z} כך שמתקיים \forall j = 1,...,k : x \equiv a_j \pmod{m_j}, ולכן נתאים

\left( a_1 , ..., a_k \right) \mapsto x

כאשר x הוא זה שמתקבל ממשפט השאריות הסיני והוא יחיד עד כדי מודולו m = m_1 \cdot ... \cdot m_k.

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

המשפט בתורת החוגים[עריכת קוד מקור | עריכה]

יהי \ R חוג עם יחידה. נניח שהאידאלים \ I_1,\dots,I_k הם 'זרים בזוגות' (או 'מקסימליים הדדית'), כלומר \ I_i+I_j = R לכל \ i\neq j. אז חוג המנה \ R/(I_1 \cap \dots \cap I_k) איזומורפי, לפי ההטלה הטבעית, לסכום הישר של החוגים \ R/I_1 \oplus \dots \oplus R/I_k. ההטלה הטבעית היא חח"ע אם ורק אם חיתוך האידאלים ריק (חיתוך האידאלים הוא גרעין ההטלה), והיא על אם ורק אם האידאלים זרים בזוגות.

זהו הנוסח הכללי של המשפט. יישומו בתורת המספרים מתייחס לחוג השלמים.

המשפט חל, לדוגמה, כאשר האידאלים \ I_1,\dots,I_k כולם אידאלים מקסימליים שונים זה מזה. במקרה זה חוגי המנה \ R/I_i הם שדות, ואז \ R/(I_1 \cap \dots \cap I_k) הוא חוג קומוטטיבי ראשוני למחצה.

קישורים חיצוניים[עריכת קוד מקור | עריכה]