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

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

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

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

נניח ש- $\ 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}\cdots 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\neq i$ ) הם 0. תוצאות אלה בונות בסיס למרחב הפתרונות, והפתרון המבוקש הוא צירוף-ליניארי של איברי-בסיס עם המקדמים-החופשיים במשוואות-המודולריות.

נגדיר $\ n_{i}=m/m_{i}$ ואז מתקיים ש $\ n_{i},m_{i}$ זרים (מאחר ש-m_i זר לכל גורם במכפלה המרכיבה את n_i. אם הם לא היו זרים היה מספר ראשוני המחלק את שניהם, ובפרט את אחד הגורמים במכפלה, ואז היה מתקבל מספר ראשוני המחלק הן את m_i והן m_j אחר, בסתירה להנחה). כיוון שהם זרים, קיימים r_i ו s_i עבורם:

\ 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}}}$ כי m_j מחלק את n_i.

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

\ 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$ ומאחר שכל ה-m_i זרים נובע שגם $\ m|x-y$ ומכאן ששני הפתרונות שקולים מודולו m.

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

דוגמה

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

$x\equiv 2{\pmod {3}}$
$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}=2e_{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}\cdots 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}\cdots 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}$ . בפרט, אם R קומוטטיבי והאידיאלים $\ I_{1},\dots ,I_{k}$ כולם אידיאלים מקסימליים ושונים זה מזה, אז $\ R/(I_{1}\cap \dots \cap I_{k})$ הוא מכפלה ישרה של שדות.