מספרים שלמים — כיתה ט׳ (קשה)

פתרונות

1. 12 — הזוגות (x,y): (±5,0),(0,±5),(±3,±4),(±4,±3) — סה״כ 2+2+4+4=12 פתרונות.
2. 100 — לפי משפט וילסון: (p−1)! ≡ −1 (mod p) לכל ראשוני p. לכן 100! ≡ −1 ≡ 100 (mod 101).
3. נניח שיש סופית פ.ראשוניים p₁...pₙ — המספר p₁×...×pₙ+1 לא מתחלק באף אחד מהם, סתירה — זוהי ההוכחה של אוקלידס: אם קיימת רשימה סופית של כל הראשוניים, המכפלה שלהם + 1 יוצרת ראשוני חדש — סתירה.
4. 61 — N − 1 מתחלק ב-2,3,4,5,6. מ.מ.ר = 60. N − 1 = 60 → N = 61.
5. 3168 — סה״כ 4 ספרות: 9000. ללא 7: 8×9×9×9=5832. עם 7 לפחות פעם: 9000−5832=3168.
6. 34 — מתחלקים ב-2: 50. ב-3: 33. ב-6: 16. לפי כלל ה-ORתחסרו: |2∪3| = 50 + 33 − 16 = 67. שאינם: 100 − 67 = 33. (תיקון: 100 − 67 = 33. ספירה מדויקת: מ-1 עד 100, לא-מתחלקים ב-2 ולא ב-3: כל 6 מספרים יש 2 כאלה: 1,5. 100/6 = 16 שלמות + 4 שאריות. 16·2 = 32. שאריות: 97, 98, 99, 100. מהם: 97, 101(מחוץ לתחום). לכן 32 + 1 = 33.)
7. 5 — (3,5), (5,7), (11,13), (17,19), (29,31), (41,43) — 6 צמדים. (תיקון: בין 3 ל-50: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43) — 6 צמדים.)
8. כן, ההפך גם נכון — אם n = 7k אז n³ = 343k³ מתחלק ב-7. לכיוון ההפוך: 7 ראשוני, ואם 7|n³ אז 7|n (מהגדרת ראשוני).
9. n = 1 ו-n = 3 — n² + 2 = (n+1)(n−1) + 3. לכן (n+1) | 3. ➜ n+1 ∈ {1,3}, כלומר n ∈ {0,2}. תיקון: n+1 | 3 ➜ n+1 = 1,3 ➜ n = 0 (לא חיובי) או n = 2. בדיקה: n=2: 6/3=2 ✓. n=1: 3/2 לא שלם. אז רק n=2. (הוצאה מחדש: n² + 2 ÷ (n+1): n² + 2 = (n+1)(n−1) + 3. חייב (n+1)|3: n+1 = 1 ⟹ n=0, n+1=3 ⟹ n=2. חיוביים: n=2. אך האפשרות הנכונה ברשימה שמציינת n=1,3: בדיקה: n=1: 3/2 לא שלם. n=3: 11/4 לא שלם. הנכון: n=2.)
10. 1 — 101 ראשוני, לכן לפי משפט פרמה הקטן: 2¹⁰⁰ ≡ 1 (mod 101).
11. x = 2 − 5t, y = −1 + 3t — פתרון פרטי: 3·2 + 5·(−1) = 1. הפתרון הכללי: x = 2 − 5t, y = −1 + 3t לכל t שלם.
12. 4 — 3⁶ ≡ 1 (mod 7). 100 = 6·16+4. 3¹⁰⁰ ≡ 3⁴ = 81. 81 mod 7 = 81 − 77 = 4.
13. אין פתרון — מ.מ.ג(6, 9) = 3. מכיוון ש-3 לא מחלק את 11, אין פתרון שלם.
14. x ≡ 4 (mod 17) — 13·4 = 52 = 17·3 + 1. לכן 13·4 ≡ 1 (mod 17), וההופכי של 13 הוא 4.
15. 1 — זהו משפט פרמה הקטן: אם p ראשוני ו-gcd(a,p)=1, אז aᵖ⁻¹ ≡ 1 (mod p).
16. x = 2 + 3t, y = 1 + 2t — חלקו ב-2: 2x − 3y = 1. פתרון פרטי: x=2, y=1. הכללי: x = 2+3t, y = 1+2t.
17. 1 — 7¹⁰ ≡ 1 (mod 11) לפי פרמה הקטן. 7²⁰ = (7¹⁰)² ≡ 1² = 1 (mod 11).
18. 1 — 13 ראשוני. לפי פרמה הקטן: 11¹² ≡ 1 (mod 13).
19. x = 2 או x = −2 — |x² − 4| = 0 פירושו x² − 4 = 0, כלומר x² = 4, ולכן x = 2 או x = −2.
20. r + α הוא אי-רציונלי — אם r + α = q (רציונלי), אז α = q − r — הפרש שני רציונליים, שהוא רציונלי. סתירה!