מה זה מ.ש.מ (מחלק משותף מקסימלי)?
מ.ש.מ (מחלק משותף מקסימלי, באנגלית GCD) הוא המספר הגדול ביותר שמחלק את כל המספרים הנתונים ללא שארית. למשל, מ.ש.מ של 12 ו-18 הוא 6.
אלגוריתם אוקלידס, שפותח לפני למעלה מ-2,000 שנה, הוא השיטה היעילה ביותר לחישוב מ.ש.מ. הרעיון: מ.ש.מ(a,b) = מ.ש.מ(b, a mod b).
מ.ש.מ משמש לצמצום שברים. למשל, 12/18 — מ.ש.מ(12,18)=6, אז 12/18 = 2/3. שני מספרים נקראים "זרים" אם המ.ש.מ שלהם הוא 1.
איך מחשבים מ.ש.מ?
אלגוריתם אוקלידס: מחלקים את הגדול בקטן ולוקחים את השארית. חוזרים עד שהשארית היא 0.
נוסחה: מ.ש.מ(a,b) = מ.ש.מ(b, a mod b) | עד ש-b=0
דוגמה: דוגמה: מ.ש.מ(48,18) → 48 = 2×18 + 12 → מ.ש.מ(18,12) → 18 = 1×12 + 6 → מ.ש.מ(12,6) → 12 = 2×6 + 0 → מ.ש.מ = 6.
מקור: תורת המספרים — אלגוריתם אוקלידס
דוגמאות מ.ש.מ
| מספרים | מ.ש.מ | זרים? |
|---|---|---|
| 12, 18 | 6 | לא |
| 15, 28 | 1 | כן |
| 24, 36 | 12 | לא |
| 7, 13 | 1 | כן |
| 100, 75 | 25 | לא |
מתי משתמשים במ.ש.מ?
- צמצום שברים: 24/36 → מ.ש.מ(24,36)=12 → 2/3
- חלוקה שווה: 24 תפוחים ו-36 תפוזים → מקסימום 12 סלים שווים
- אריחים: חדר 12×8 מטר → אריח מרבי 4×4 מטר
- קריפטוגרפיה: RSA משתמש במ.ש.מ לבדיקת זרות מספרים
- גרפיקה: יחס מסך 1920×1080 → מ.ש.מ=120 → יחס 16:9
- מוזיקה: יחסי תדרים והרמוניה
שאלות נפוצות
מה אלגוריתם אוקלידס?
אלגוריתם יעיל: מחליפים (a,b) ב-(b, a mod b) עד שמגיעים ל-(מ.ש.מ, 0). פותח ביוון העתיקה.
מה זה מספרים זרים?
שני מספרים עם מ.ש.מ = 1 נקראים זרים (coprime). למשל 8 ו-15 הם זרים.
מה מ.ש.מ אם אחד מחלק את השני?
אם a מחלק את b, אז מ.ש.מ(a,b) = a. למשל מ.ש.מ(6,18) = 6.
איך משתמשים במ.ש.מ לצמצום?
מחלקים מונה ומכנה במ.ש.מ. למשל 45/60: מ.ש.מ=15, אז 3/4.
תורת המספרים — אלגוריתם אוקלידס