27/6/2020
משפט השאריות הסיני אומר שלמערכת המשוואות:
\[\begin{eqnarray} &x\equiv{}a_1\mod{n_1}\\ &x\equiv{}a_2\mod{n_2}\\ &\vdots{}\\ &x\equiv{}a_k\mod{n_k} \end{eqnarray}\] קיים פתרון יחיד מודולו \(n\). כאשר \(n\) הוא מכפלת כל \(n=n_1\cdot{}n_2\cdot{}\dots{}\cdot{}n_k\) והמספרים \(n_1,n_2,\dots{}n_k\) זרים בזוגות.
רגע, מה?
בשביל להבין בואו נסתכל על מקרה פשוט יותר - שתי משוואות (במקום \(k\)) ומספרים ראשוניים שונים \(p\) ו-\(q\) עבור \(n_1\) ו-\(n_2\) (כי מובן שהם זרים אחד לשני - זרים דרך אגב, זה אומר שהמחלק המשותף הגדול ביותר שלהם הוא 1). \[\begin{eqnarray} &x\equiv{}a_1\mod{p}\\ &x\equiv{}a_2\mod{q} \end{eqnarray}\] למעשה כשאתם מחפשים פתרון לשתי משוואות כאלה, אתם מחפשים \(x\) שהשארית שלו בחלוקה ב-\(p\) היא \(a_1\) ושארית החלוקה שלו ב-\(q\) היא \(a_2\). זה צריך להיות אותו \(x\) לשתי המשוואות! המשפט, פשוט אומר שכל עוד הבטחנו ש-\(p\) ו-\(q\) זרים אחד לשני, אז בטוח יהיה לנו פתרון וגם הפתרון הזה יהיה יחיד עד כדי מודולו \(n=p\cdot{}q\).
הכי טוב עם דוגמה. נבחר שני ראשוניים, 3 ו-5 ונסתכל על מערכת המשוואות:
\[\begin{split} &x\equiv{}2\mod{3}\\ &x\equiv{}4\mod{5}\\ \end{split}\]שימו לב שזה לא כזה מסובך למצוא \(x_1\) שמקיים את המשוואה הראשונה, פשוט בוחרים \(x_1=2\) שזה מאוד ישיר אבל מן הסתם זה לא הפתרון שיקיים גם את המשוואה השנייה כי -
\[x_1=2\not\equiv{}4\mod{5}\]מסתבר שזה לא כזה פשוט אה? טוב זה בעצם כן.. כי יש לנו את משפט השאריות הסיני, אבל כדי שזה באמת יהיה פשוט נצטרך להבין איך הוא עובד קודם, ואז למה הוא עובד. אז בגדול במקרה שלנו, אם נחזור למערכת בת שתי המשוואות שרשמנו, לפי המשפט - קודם כל יש לה פתרון, שזה פשוט אומר שקיים \(x\) שכאשר מחלקים אותו ב-3 השארית היא 2 ובחלוקה ב-5 השארית תהיה 4. בנוסף המשפט אומר שהפתרון הזה הוא יחיד עד כדי שקילות מודולו \(n=15\) (כי 15 הוא המכפלה של שני המספרים 3 ו-5 של שתי המשוואות). זה אומר בעצם, שהפתרון שנקבל יהיה בין 0 ל-14 אבל גם שיהיה רק מספר אחד בין 0 ל-14 שיספק את שתי המשוואות.
למה שלא יהיה פתרון?
אז מסתבר שזה לא כזה ברור, יש דוגמה שמראה את זה בצורה פשוטה אבל יותר מאוחר אנחנו נראה שברגע שיש לנו מספרים זרים במודולו של המשוואות אנחנו יוכלים להבטיח שנקבל פתרון. דוגמה נגדית פשוטה:
\[\begin{eqnarray} &x\equiv{}1\mod{2}\\ &x\equiv{}2\mod{4}\\ \end{eqnarray}\]המספרים ששקולים ל-1 מודולו 2 הם כל המספרים האי־זוגיים וכל המספרים ששקולים ל-2 מודולו 4 הם זוגיים, אז בחיים לא נמצא \(x\) שיהיה שקול לשניהם בשני המודולו? מבינים למה? אם לא תסתכלו על קבוצת כל המספרים החיוביים ששקולים ל-1 מודולו 2 ול-2 מודולו 4:
\[ \begin{eqnarray} &1\mod{2}=\{1,3,5,7,9,\dots{}\}\\ &2\mod{4}=\{2,6,10,14,18,\dots{}\}\\ \end{eqnarray} \]שוב, כל האי־זוגיים וכל המספרים שאם נחלק ב-4 השארית תהיה 2. שמים לב שאין אף מספר חופף? זה יעבוד גם אם נבדוק את זה לכיוון של המספרים השליליים. נסו את זה..
אז מה הפתרון?
אממ.. 14
לא מאמינים? תראו -
נחמד שכתבתי שזה נכון פשוט ככה, אבל בואו נראה שזה באמת מתאים, ואיך הגעתי לזה בכלל? הרי המספר הזה לא נחת מהחלל, ואנחנו צריכים שתהיה לנו שיטה טובה לחשב אותו גם אם מערכת המשוואות תהיה מרובת משוואות ועם מספרים גדולים, לא חוכמה לחשב עם מספרים קטנים כמו 3,5,2,4..
אז נגיע גם לזה, אבל שנייה לפי זה נראה שאכן 14 מקיים את המשוואת. כשמחלקים את 14 ב-3 מקבלים 4, אבל מה שמעניין אותנו זה השארית, שהיא 2 ולפי ההגדרה של מודלו מתקיים לנו -
\[14\equiv{}2 \mod{3}\] באופן דומה גם לגבי 14 כשמחלקים ב-5, הכפולה הכי קרובה אליו היא 10, ואם נסתכל על השארית שהיא 4: \[14\equiv{}4\mod{5}\]תראו רגע משהו יפה
אני רגע ממקם אותנו מחדש, אנחנו מנסים למצוא מספר כלשהו, שבמודולו 3 יתן שארית 2 ובמודולו 5 יתן שארית 4. וגם אמרנו שמה שמשנה לנו זה שזה יהיה מספר כלשהו בין 0 ל-14, כי ככה הוא יהיה יחיד מודולו 15. אז סידרתי את המספרים מ-1 עד 14 בצד שמאל ככה שבכל שורה יש אותה שארית מודולו 3, כלומר, השורה הראשונה היא עם שארית 0, השורה השנייה עם שארית 1 וכו׳. בצד שמאל, סידור דומה רק שסידרתי את המספרים מודולו 5.
מה אפשר לראות פה?
שימו לב שלכל אחד מהמספרים שהם שארית כלשהי מודולו 5 (כלומר שורה כלשהי בצד ימין), נניח שארית 4. נוכל לבחור מספר שיהיה איזה שארית שנרצה מודולו 3. כלומר, שאם אנחנו מחפשים מספר שיהיה שקול ל-4 מודולו 5, נוכל לבחור את 4 כמובן, שהוא 1 מודולו 3, או את 9 שהוא 0 מודולו 3 או את 14 שיהיה 2 מודולו 3. אבל תראו שזה עובד לכל מספר, גם אם היינו רוצים מספר כלשהו שהוא 2 מודולו 5 וגם 1 מודולו 3. רואים ש-7 עונה על זה? זה אומר ש-7 הוא הפתרון היחיד שמקיים - \[\begin{eqnarray} &x\equiv{}1\mod{3}\\ &x\equiv{}2\mod{5}\\ \end{eqnarray}\] מצליחים לראות את זה? ויזואלית זה אומר שהמספרים שמרכיבים שורה אחת בצד אחד נפרשים על כל השורות בצד השני. וזה עובד בשני הכיוונים -
אז כשאני מחפש \(x\) שהוא שארית כלשהי מודולו 3 ושארית כלשהי מודולו 5 אני בסך הכל צריך לצייר טבלאות, להסתכל בשורה שמייצגת את השארית שאני מחפש ואז למצוא בשורה הזאת מספר שנמצא גם בשורה שאני מחפש מודולו 5.
באופן כללי יותר..
מה אני עושה אם אני צריך לחפש שאריות מודולו 1009 ומודולו 503? (הם שניהם ראשוניים לכן זרים אחד לשני). אז יש משוואה יחסית פשוטה להשיג את הפתרון בצורה ישירה, כשמדברים על מערכת המשוואות \[\begin{eqnarray} &x\equiv{}a\mod{p}\\ &x\equiv{}b\mod{q}\\ \end{eqnarray}\] כדי למצוא את הפתרון קודם נצטרך לחשב את המספרים ההופכיים של \(p\) ו-\(q\) מודולו אחד של השני. מה זאת אומרת? למצוא מספר \(t\) שכשמכפילים אותו ב- \(p\) ומחשבים שארית מודולו \(q\) מקבלים 1 (ולהיפך, מספר \(k\) שכאשר מכפילים אותו ב- \(q\) ומחשבים שארית מודולו \(p\) מקבלים 1). בינתיים תאמינו לי שקיימים כאלה (הסיבה שהם קיימים היא שהמספרים במודולו זרים, בגלל זה דרשנו את זה), יש דרך מאוד פשוטה לחשב את ההופכיים האלה עם אלגוריתם של אוקלידס למציאת המחלק המשותף הגדול ביותר. במקרה שמצאנו את ההופכיים, הפתרון יהיה: \[ x=p\cdot{}t\cdot{}b+q\cdot{}k\cdot{}a\mod{p\cdot{}q} \] זה מסתדר דיי יפה, תראו, אם נחשב את המספר הזה במודולו \(p\) המחובר השמאלי יתבטל, כי הוא מתחלק ב-\(p\) ובמחובר הימני ישאר לנו 1 מהמכפלה של \(q\) בהופכי שלו ואז כשנכפיל את 1 ב-\(a\) נקבל את \(a\) שהוא התוצאה שרצינו מודולו \(p\). זה ממש אותו דבר עם \(q\). וזה יעבוד לנו בכל מספר ששקול לדבר הזה מודולו \(p\cdot{}q\) כי כל מכפלה של שני המספרים האלה תתחלק בשניהם.
אפשר גם לשים הכל ביחד
אפשר בעצם לסדר את שתי הטבלאות האלה בצורה קצת אחרת ולקבל עוד הבנה איך דברים עובדים כאן. עכשיו סידרתי את כל המספרים בין 0 ל-14 ככה שכל עמודה היא שארית מודולו 3 וכל שורה שארית מודולו 5. אז נניח המספר בעמודה האמצעית והשורה הרביעית הוא 13 כי הוא שארית 1 במודולו 3 ושארית 3 במודולו 5 (האינדקסים של העמודות מתחילים מ-0).
תראו איזה יופי זה מסתדר לנו. יש פה שני דברים יפים, אחד, שיש לנו בכל עמודה וכל שורה תוצאה, זאת אומרת שכל שארית שנחפש מודולו 3 ושארית (אחרת) שנחפש מודולו 5, תהיה לנו התוצאה של שתי הבקשות האלה בשורה ה-\(a+1\) והעמודה ה-\(b+1\) (הפלוס אחד פה שוב בגלל שהאינדקסים מתחילים מ-1 והשאריות ב-0 אבל זה לא מהותי בכלל). הדבר השני היפה שאפשר לראות, זה שבכל תא בטבלה הזאת יש ערך אחד בדיוק. וזה אומר את הטענה השנייה של המשפט, שלא יכול להיות יותר מפתרון אחד. נכון? אם מצאנו את 7 כפתרון של המשוואות שלנו, הוא יהיה שארית 1 מודולו 3 ושארית 2 מודולו 5, לכן הוא אף פעם לא ייתן לנו פתרון בשארית אחרת שנחפש.
עכשיו נסתכל על זה במספרים אחרים כדי לראות שזה לא כזה טריוויאלי -
2 ו-4 לא זרים, אז הכל נהרס לנו כי כל מיני מספרים נופלים לנו באותה משבצת. 2 ו-6 שניהם שארית 0 מודולו 2 ושארית 2 מודולו 6. שזה היה יכול לעזור לנו אם זה לא היה בא על חשבון שאריות אחרות שהיינו רוצים לקבל נניח שארית 1 מודולו 2 ושארית 0 מודולו 6. אפשר לראות למעלה (ואפשר גם לעבור מספר מספר) ולגלות שאין מספר שכאשר נחלק אותו ב-2 נקבל שארית 1 וכאשר נחלק אותו ב-6 נקבל שארית 0. זה גם דיי הגיוני, מטיעון דומה לטיעון הזוגיים והאי־זוגיים שעשינו מקודם.
בכל הדוגמאות הויזואליות שיש למעלה, מה שנחמד זה שאפשר למצוא הרבה תבניות לאופן שבו המספרים ממלאים אותן. נסו לראות אם אתם מצליחים למצוא את הסדר שבו המספרים מסודרים ואיזה חוקיות יש לו.
אם לא הצלחתם למצוא משהו, הנה דוגמה עם מספרים יותר גדולים שאולי תהיה יותר קלה -
ncG1vNJzZmilkaC2r7PBq5iipl6vf3l61p6ZZ5ufp7Jvw8inm6ivo2O7psCOqaasrKNksKm1zZ6qnmWimrqitc2dnKtlpJ2ysL7EpmWhrJ2h