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

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

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

מקורו של המשפט בספר מהמאה השלישית של המתמטיקאי הסיני סן-צו, ומכאן שמו.

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

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

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}.

[עריכה] הוכחה

נגדיר \ 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}. בנוסף \ 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.

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

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

יהי \ R חוג עם יחידה. נניח שהאידאלים \ I_1,\dots,I_k הם 'מקסימליים הדדית', כלומר \ I_i+I_k = 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) הוא חוג קומוטטיבי ראשוני למחצה.