כיצד להשתמש בשאריות כדי למצוא מספר?
לפעמים, אתה מתבקש להבין מספר על ידי ידיעת שאר החלקים כאשר הם מחולקים למספרים מסוימים.
לפעמים, אתה מתבקש להבין מספר על ידי ידיעת שאר החלקים כאשר הם מחולקים למספרים מסוימים. במאמר זה, תוכלו ללמוד כיצד להשתמש משפט השאריות הסיני כדי לפתור אלו סוגים של בעיות. וודא שאתה יודע מהי חשבון מודולרי לפני קריאת המאמר.
השאר אינו משתנה כאשר מספר מכפיל של המודול מתווסף למספר.
הערה: למרות שישנן דרכים רבות לקבוע את המשפט, מאמר זה יעבור על הצעדים שתוכלו לנקוט כדי להשתמש במשפט, ולא על הגדרתו הפורמלית.
חלק 1 מתוך 3: הורדת היסודות
- 1דע את המיומנות בה אתה משתמש. כאשר מחולקים שני מספרים, A {\ displaystyle A} ו- B (B ≠ 0) {\ displaystyle B (B \ neq 0)} , תקבל מנה Q {\ displaystyle Q} ושאר R {\ displaystyle R} . ניתן לכתוב זאת כ: A / B = Q {\ displaystyle A / B = Q} שארית R. {\ displaystyle R.} בחשבון מודולרי, אכפת לנו רק מהשאריות. לכן, תוכל להפוך את המשוואה שלך ל- AmodB≡R {\ displaystyle AmodB \ equiv R} . אנו קוראים ל- B {\ displaystyle B} למודולוס. לדוגמה, 13mod5 {\ displaystyle 13mod5} שואל אותנו "מהי השאר כאשר 13 {\ displaystyle 13} מחולק ב- 5 {\ displaystyle 5} ?" למרות שיש הרבה יותר שכדאי לדעת, הנה כמה מאפיינים חשובים.
- שני מספרים נחשבים חופפים כאשר הם משאירים את אותם שאריות. לדוגמה, 13 {\ displaystyle 13} ו- 18 {\ displaystyle 18} חופפים במערכת המודולו 5 {\ displaystyle 5} מכיוון שהם נותנים שארית של 3 {\ displaystyle 3} כשהם מחולקים ב 5 {\ displaystyle 5} .
- השאר אינו משתנה כאשר מספר מכפיל של המודול מתווסף למספר. לדוגמא, ניתן להוסיף 10 {\ displaystyle 10} , מכפיל של 5 {\ displaystyle 5} , ל- 13 {\ displaystyle 13} , ולהפוך אותו ל -23 {\ displaystyle 23} . שאר 10,6 {\ displaystyle 10,6} ו- 20,6 {\ displaystyle 20,6} שניהם 3 {\ displaystyle 3} .
- כאשר אתה מוסיף, מחסיר או מכפיל את שני הצדדים במספר שלם, המשוואה עדיין תישאר נכונה.
- 2שים לב ששיטה זו עשויה להימשך זמן רב יותר ממציאת התשובה על ידי ניחוש באמצעות סימון.
- כאשר אתה לוקח מבחן אמריקני או בהתמודדות עם מספרים קטנים, מנחש ובדיקה היא בדרך כלל הדרך הטובה יותר לפתור את הבעיה.
המספרים מייצגים כל אחד מהמספרים שבהם אתה מחלק את המספר המסתורי שלך.
חלק 2 מתוך 3: שימוש במשפט
- 1הפכו מילים לביטויים.
- שימו לב כאן שהמידע החשוב הוא על שאריות. תן n {\ displaystyle n} שווה למספר המסתורין שלך.
- בבעיה בסעיף לעיל, את הביטוי "נותן שארית של 3 {\ displaystyle 3} כאשר מחלקים אותם ל- 5 {\ displaystyle 5} " ניתן לכתוב כ n≡3mod5. {\ Displaystyle n \ equiv 3mod5.}
- את הביטוי "נותן שארית של 1 {\ displaystyle 1} כשהוא מחולק ב- 7 {\ displaystyle 7} " ניתן לכתוב כ n≡1mod7 {\ displaystyle n \ equiv 1mod7} .
- את הביטוי "נותן שארית של 7 {\ displaystyle 7} כאשר מחלקים אותם ל- 11 {\ displaystyle 11} " ניתן לכתוב כ n≡7mod11 {\ displaystyle n \ equiv 7mod11} .
- 2כתוב ביטוי כמו זה / ים שלמעלה.
- המספרים מייצגים כל אחד מהמספרים שבהם אתה מחלק את המספר המסתורי שלך.
- 3מלא כל ריק על ידי הצבת המוצר של כל מחלקי המספרים המסתוריים שלך, למעט המספר שכתוב מעל הריק. עיין בתמונה לעיל להבנה נוספת.
- זה נעשה מכיוון שהכפלת מספר כלשהו במודולוס הופכת אותו לחלוק במודולוס.
- במילים אחרות, כל עוד תעשה את הריק עם מודולו 5 {\ displaystyle 5} להיות תואם ל- 3mod5 {\ displaystyle 3mod5}, תקבל את התשובה הנכונה.
- 4התייחסו לכל ריק בנפרד.
- התמודד עם מודולו 5 {\ displaystyle 5} תחילה. שאל את עצמך, "איזה מספר ניתן להכפיל ל 77 {\ displaystyle 77} כך שהוא יהיה תואם ל- 3mod5 {\ displaystyle 3mod5}?" כתוב זאת כ- 77x≡3mod5 {\ displaystyle 77x \ equiv 3mod5} .
- שאל את עצמך, "איזה מספר ניתן להכפיל ל 55 {\ displaystyle 55} כך שהוא יהיה תואם את 1mod7?" כתוב זאת כ- 55x≡1mod7 {\ displaystyle 55x \ equiv 1mod7} .
- שאל את עצמך, "איזה מספר ניתן להכפיל ל- 35 {\ displaystyle 35} כך שהוא יהיה תואם ל- 7mod11 {\ displaystyle 7mod11}?" כתוב זאת כ- 35x≡7mod11 {\ displaystyle 35x \ equiv 7mod11} .
- 5לפתור את ההפכים במקום לפתור את המשוואות. כלומר, אתה מנסה לפתור מספרים שנותנים 1modN {\ displaystyle 1modN} .
- אתה פותר 77x≡1mod5 {\ displaystyle 77x \ equiv 1mod5} , 55x≡1mod7 {\ displaystyle 55x \ equiv 1mod7} ו- 35x≡1mod11 {\ displaystyle 35x \ equiv 1mod11} .
- ישנן מספר דרכים לפתור משוואות אלה. אתה יכול לנחש ולבדוק, או להשתמש באלגוריתם של אוקלידס. (שלבי האלגוריתם יוצגו בחלק הבא).
כאשר אתה מוסיף, מחסיר או מכפיל את שני הצדדים במספר שלם, המשוואה עדיין תישאר נכונה.
חלק 3 מתוך 3: פתרון המשוואות
- 1לפשט את המשוואות באמצעות מספרים חופפים. (עיין בחלק הראשון למידע נוסף.)
- ב- 77x≡1mod5 {\ displaystyle 77x \ equiv 1mod5} , ניתן להפוך 77 {\ displaystyle 77} ל -2.
- ב- 55x≡1mod7 {\ displaystyle 55x \ equiv 1mod7} , ניתן להפוך 55 {\ displaystyle 55} ל -6.
- ב- 35x≡1mod11 {\ displaystyle 35x \ equiv 1mod11} , 35 {\ displaystyle 35} ניתן להפוך ל -2.
- 2חלק את המודול במקדם והפוך את פעולת החלוקה לריבוי.
- מכיוון ש 2,5 = 2 {\ displaystyle 2,5 = 2} שארית 1 {\ displaystyle 1} , אתה יכול לכתוב את זה כ 5 = 2 (2) +1 {\ displaystyle 5 = 2 (2) +1} .
- מכיוון 1,17 = 1 {\ displaystyle 1,17 = 1} שארית 1 {\ displaystyle 1} , אתה יכול לכתוב זאת כ- 7 = 6 (1) +1 {\ displaystyle 7 = 6 (1) +1} .
- מכיוון ש- 10,5 = 5 {\ displaystyle 10,5 = 5} שארית 1 {\ displaystyle 1} , אתה יכול לכתוב את זה כ- 11 = 2 (5) +1 {\ displaystyle 11 = 2 (5) +1} .
- אם השאר אינו אחד, חזור על התהליך. לדוגמא, אם תתחיל עם modulo 7 {\ displaystyle 7} ו- divisor 5 {\ displaystyle 5} , יהיה לך 7 = 5 (1) +2 {\ displaystyle 7 = 5 (1) +2} . קח את המחלק ואת השאר לחזור על התהליך. לכן עכשיו יש לך 5 = 2 (2) +1 {\ displaystyle 5 = 2 (2) +1}
- אם אי אפשר להגיע לאחד, ההפוך אינו קיים.
- 3כתוב את המשוואות החדשות.
- תן לצד אחד של המשוואה להיות שווה ל- 1 {\ displaystyle 1} .
- עבור מודולו חמש, יש לך 1 = 5−2 (2) {\ displaystyle 1 = 5-2 (2)}
- עבור מודולו שבע, יש לך 1 = 7−6 (1) {\ displaystyle 1 = 7-6 (1)}
- עבור מודולו אחד עשר, יש לך 1 = 11−2 (5) {\ displaystyle 1 = 11-2 (5)}
- אם היית צריך לקחת יותר מצעד אחד כדי להגיע לאחד, אז אתה צריך לעשות זאת גם במספר שלבים. לדוגמא, באמצעות הדוגמה מהשלב הקודם, 1 = 5−2 (2) {\ displaystyle 1 = 5-2 (2)} . מכיוון ש- 7 = 5 (1) +2 {\ displaystyle 7 = 5 (1) +2} , אנו גם יודעים ש -2 = 7−5 (1) {\ displaystyle 2 = 7-5 (1)} . נוכל להחליף זאת למשוואה הראשונה כדי לקבל 1 = 5−2 (7−5 (1)) {\ displaystyle 1 = 5-2 (7-5 (1))} או 1 = 3 (5) −2 (7) {\ displaystyle 1 = 3 (5) -2 (7)}
- ודא שבסופו של דבר תהיה משוואה עם המחלק המקורי שלך והמודול.
- 4התייחס לכל משוואה כמו שאתה מתייחס למשוואות במערכת החשבון המודולרית.
- מכיוון שחמישה חופפת לאפס במודולו חמש, יש לך 1mod5≡0−2 (2) {\ displaystyle 1mod5 \ equiv 0-2 (2)} או 1 mod5≡ − 2 (2) {\ displaystyle 1mod5 \ equiv -2 (2)}
- מכיוון ששבעה חופפים לאפס במודולו שבע, יש לך 1mod7≡0−6 (1) {\ displaystyle 1mod7 \ equiv 0-6 (1)} או 1mod7≡ − 6 (1) {\ displaystyle 1mod7 \ equiv -6 (1)}
- מכיוון שאחת עשרה חופפת לאחת עשרה במודולו אחת עשרה, יש לך 1mod11≡0−2 (5) {\ displaystyle 1mod11 \ equiv 0-2 (5)} או 1mod11≡ − 2 (5) {\ displaystyle 1mod11 \ equiv -2 (5)}
- 5השווה את התוצאה למשוואה המקורית שהיית צריך לפתור. שימו לב לדמיון ביניהם. המקדמים הם התשובות!
- התשובה למשוואת מודולו חמש היא −2 {\ displaystyle -2} .
- התשובה למשוואת מודולו שבע היא -1 {\ displaystyle -1} .
- התשובה למשוואה אחת-עשרה של מודולו היא -5 {\ displaystyle -5} .
- שים לב שעכשיו יש לך את הדברים הבאים: −2 (2) ≡1mod5 {\ displaystyle -2 (2) \ equiv 1mod5} , −1 (6) ≡1mod7 {\ displaystyle -1 (6) \ equiv 1mod7} ו- - 5 (2) ≡1mod11 {\ displaystyle -5 (2) \ equiv 1mod11 } .
- כדוגמה, המקדמים למחלקים הם התשובות למשוואות משלב 4, חלק 2. התשובות למשוואות משלב 4, חלק 2 הן 4 {\ displaystyle 4} עבור modulo 5 {\ displaystyle 5} , 6 {\ displaystyle 6} עבור modulo 7 {\ displaystyle 7} , ו- 9 {\ displaystyle 9} עבור modulo 11 {\ displaystyle 11} .
- 6זכור למה פתרת. המשוואות המקוריות שניסית לפתור עבורן היו 77x≡3mod5 {\ displaystyle 77x \ equiv 3mod5} , 55x≡1mod7 {\ displaystyle 55x \ equiv 1mod7} ו- 35x≡7mod11 {\ displaystyle 35x \ equiv 7mod11} , שהם משוואות כמו 2x as3mod5 {\ displaystyle 2x \ equiv 3mod5 } , 6x≡1mod7 {\ displaystyle 6x \ equiv 1mod7 } ו- 2x≡7mod11 {\ displaystyle 2x \ equiv 7mod11} , בהתאמה.
- 7נהל את המשוואות מעט.
- מכיוון ש -2 (−2) ≡1mod5 {\ displaystyle 2 (-2) \ equiv 1mod5 } , הכפלת שני הצדדים ב- 3 {\ displaystyle 3} נותנת 2 (−6) ≡3mod5 {\ displaystyle 2 (-6) \ equiv 3mod5 } .
- מכיוון ש- −1 (6) ≡1mod7 {\ displaystyle -1 (6) \ equiv 1mod7} , אתה יכול להשאיר את זה לבד.
- מכיוון ש -5 (2) mod1mod11 {\ displaystyle -5 (2) \ equiv 1mod11} , הכפלת שני הצדדים ב- 7 {\ displaystyle 7} נותנת −35 (2) ≡7mod11 {\ displaystyle -35 (2) \ equiv 7mod11 } .
- 8פשט את המשוואות על ידי הוספה או חיסור של מכפילי המודול למקדמי המחלקים.
- −6 {\ displaystyle -6} הופך ל- −6 + 5 (2) {\ displaystyle -6 + 5 (2)} או 4 {\ displaystyle 4} , והופך 2 (−6) ≡3mod5 {\ displaystyle 2 (-6) \ equiv 3mod5} ל- 2 (4) ≡3mod5 {\ displaystyle 2 (4) \ equiv 3mod5 } .
- −1 {\ displaystyle -1} הופך ל- -1 + 7 (1) {\ displaystyle -1 + 7 (1)} או 6 {\ displaystyle 6} , והופך ל -1 (6) ≡1mod7 {\ displaystyle -1 (6) \ equiv 1mod7} עד 6 (6) ≡1mod7 {\ displaystyle 6 (6) \ equiv 1mod7} .
- −35 {\ displaystyle -35} הופך ל- −35 + 11 (4) {\ displaystyle -35 + 11 (4)} או 9 {\ displaystyle 9} , והופך −35 (2) ≡7mod11 {\ displaystyle -35 (2) \ equiv 7mod11} עד 9 (2) ≡7mod11 {\ displaystyle 9 (2) \ equiv 7mod11} .
- 9הכפל את התשובות למונחים במודולים המתאימים.
- הכפל 4 {\ displaystyle 4} למונחים במודולו 5 {\ displaystyle 5} , 6 {\ displaystyle 6} למונחים במודולו 7 {\ displaystyle 7} , ו 9 {\ displaystyle 9} למודולו 11 {\ displaystyle 11} .
- 10הוסף את המספרים למעלה.
- התוצאה היא 77 (4) +55 (6) +35 (9) = 953 {\ displaystyle 77 (4) +55 (6) +35 (9) = 953} .
- 11התאם את גודל המספר על ידי הוספה או חיסור באמצעות LCM של המחלקים. בסיום זו התשובה שלך!
- כאן, ה- LCM של 5 {\ displaystyle 5} , 7 {\ displaystyle 7} ו- 11 {\ displaystyle 11} הוא 385 {\ displaystyle 385} . על ידי חיסור 953 {\ displaystyle 953} על ידי 385 (2) {\ displaystyle 385 (2)} , אנו מקבלים 183 {\ displaystyle 183} . מכיוון שההבדל קטן מה- LCM, זו התשובה החיובית הקטנה ביותר.
- שים לב שאתה יכול להשתמש בשיטה זו כדי להתאים את גודל המספר. בעיות רבות נותנות טווח שהתשובה יכולה להיות בו.
קרא גם: איך לקצר?
