GRE Subject Test · GRE Mathematics · נושא 12
הכנה למבחן GRE לתואר ראשון. מטרות מקומיות בתוך היקף ETS הנבדק; זהו הוראה מקורית, ולא מבחן רשמי או חיזוי ציון.
תנאי קדמה: אלגוריתם אוקליד, גורמים ראשוניים וחשבון מודולרי.
התאמה: שוויון שאריות כיוון שהמודולוס מחלק את ההפרש ביניהן.
פונקציית אוילר: מספר השאריות הקופרימויות למודולוס שלם חיובי נתון.
| English | עברית |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | התאמה מודולרית |
| totient/ˈtəʊʃənt/ | פונקציית טוטיינט |
המשוואה ax≡b מודולו n יש לה פתרון אם ורק אם d=gcd(a,n) מחלק את b. אם כן, לחלק את a,b,n ב-d כדי לקבל משוואה עם מקדם הפיך. יש לה פתרון שארית אחד מודולו n/d ו-d פתרונות נפרדים מודולו n. חלוקת המקדם אך השארת המודולוס המקורי מאבדת לרוב פתרונות. פירוק לגורמים ראשוניים מספק כלים נוספים: אם n^k חייב להיות מתחלק במכפלת כוחות ראשוניים p^a, כל מערך ראשוני ב-n חייב להיות לפחות ceil(a/k). מערכים מינימליים אלו מייצרים בנפרד את ה-n הקביל החיובי הקטן ביותר. עבור n⁴ המתחלק ב-2⁷·3⁵, n חייב להכיל 2² ו-3², ולכן הערך המינימלי הוא 36. זהו תנאי מערכים ראשוניים, לא התאמה שפתורה בחלוקה מודולרית.
אלגוריתם אוקלידס המורחב מבטא gcd(a,n) כ-ua+vn. כאשר ה-gcd הוא ⟨1⟩, u הוא הפוך של a מוד ↯n. בחר נציג בטווח הנדרש לאחר ההפחתה. עבור ⟨7⟩ ו26, ⟨1⟩=15·7−4·26, ולכן ⟨15⟩ הוא ההפוך של ⟨7⟩ מוד ↯26; בדוק את המכפלה כדי לתפוס שגיאת סימן.
עבור מודולוסים חיוביים קופרימו m,n, משפט שארית הסיני נותן בדיוק פתרון אחד מודולו mn לכל זוג תנאי שאריות. הצבה x=r+mk בהתאמה השנייה ופתרון עבור k. אם המודולוסים אינם קופרימו, ערכי השאריות שלהם חייבים להסכים מודולו gcd(m,n); כאשר הם תואמים, היחידיות היא מודולו המכנה המשותף הקטן, ולא המכפלה.
פונקציית אוילר φ(n) סופרת שאריות קופרימויות ל-n. עבור גורמים ראשוניים נפרדים p, φ(n)=n כפול מכפלת (1−1/p). משפט אוילר נותן a^phi(n)≡1 רק כאשר gcd(a,n)=1. המקרה הראשוני הוא משפט קטן של פרמי. לחלק מערכים רק לאחר בדיקת תנאי זה; שאריה שאינה יחידה יכולה להפוך לאפס בעוצמות חוזרות.
פתור 6x≡9 מודולו 15. ה-GCD הוא 3 ומחלק את 9. חלק את שלושת הערכים כדי לקבל 2x≡3 מודולו 5; ההופך של 2 הוא 3, ולכן x≡9≡4 מודולו 5. הפתרונות המקוריים מודולו 15 הם 4,9,14. עבור x≡2 מודולו 4 ו-x≡3 מודולו 7, כתוב x=2+4k; אזי 4k≡1 מודולו 7, מה שנותן k≡2. מכאן x≡10 מודולו 28.
הביטוי a^phi(n)≡1 אינו נכון עבור כל a. לדוגמה, 2 אינו הפיך מודולו 8 ו-2^4 הוא אפס מודולו 8.
פתור את $8x\equiv12\pmod{20}$ במלואו. מצא פיכות של 7 מודולו 20. הסבר מדוע משפט אוילר אינו יכול לשמש להחלפת $2^8$ ב-1 מודולו 20.
The gcd is four and divides 12. Dividing all three numbers gives $2x\equiv3\pmod5$, so $x\equiv4\pmod5$. Modulo 20 the four answers are $4,9,14,19$; substitution gives remainder 12 each time. Since $7\cdot3=21$, the inverse of 7 is 3. Although $\phi(20)=8$, Euler's theorem requires a unit. The gcd of 2 and 20 is two, and $2^8=256\equiv16$, not 1.
פתור $x\equiv2\pmod6$, $x\equiv5\pmod9$, או הוכח אי-התאמה. ציין את המודולו לייחוד. מצא את הקטן ביותר n חיובי כך ש-$2^5\cdot3^7$ מחלק את $n^3$.
השאריות תואמות מודולו ה-GCD שלוש. נניח $x=2+6k$: אז $6k\equiv3\pmod9$, ולכן $2k\equiv1\pmod3$ ו-$k\equiv2\pmod3$. מכאן $x\equiv14\pmod{18}$. המודולו הוא ה-LCM, ולא 54. לעניין החילוק, כתוב מעריכי ראשוניים ב-n. הם חייבים לעמוד ב-$3a\ge5$, $3b\ge7$, ולכן $a\ge2$, $b\ge3$. הקטן ביותר n הוא $2^2\cdot3^3=108$; גורמים ראשוניים אחרים יכולים רק להגדיל אותו.
לעבור על הדברים צעד אחר צעד, עם תרגילים לבדיקה מיידית.
טוען נושאים…