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

פתרונות

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).