המחשבון מחזיר את המחלק המשותף הגדול (gcd) ואת הכפולה המשותפת הקטנה (lcm) של שני מספרים.
הקשר ביניהם קבוע ושימושי: gcd × lcm = |a| × |b|, ולכן די לחשב אחד מהם כדי לקבל את השני.
מחלק משותף גדול וכפולה משותפת קטנה
מחלק משותף גדול הוא המספר הגדול ביותר שמחלק את שני המספרים בלי שארית. ב-48 ו-180 הוא 12.
המחשבון מוצא אותו באלגוריתם אוקלידס: מחליפים את הזוג (a, b) בזוג (b, a mod b) ושבים על כך עד ש-b מתאפס. הערך שנותר הוא ה-gcd. זהו אחד האלגוריתמים העתיקים שעוד בשימוש, והוא יעיל להפליא — הוא מסיים בכ-log של גודל המספרים.
כפולה משותפת קטנה היא המספר הקטן ביותר שמתחלק בשניהם. היא מחושבת מהזהות lcm = |a| × |b| ÷ gcd.
הדרך לראות למה הזהות עובדת היא דרך פירוק לגורמים ראשוניים: ה-gcd לוקח מכל ראשוני את החזקה הקטנה מבין השניים, וה-lcm את הגדולה. יחד הם מכסים בדיוק את כל החזקות בשני המספרים.
שני מספרים שה-gcd שלהם 1 נקראים זרים. אין להם גורם משותף, ולכן ה-lcm שלהם הוא פשוט המכפלה. 8 ו-15, לדוגמה, זרים.
דוגמה – 48 ו-180
- פירוק: 48 = 2⁴ × 3, ו-180 = 2² × 3² × 5
- gcd: החזקות הקטנות — 2² × 3 = 12
- lcm: החזקות הגדולות — 2⁴ × 3² × 5 = 720
- בדיקה דרך הזהות: 48 × 180 ÷ 12 = 720 ✓
- באלגוריתם אוקלידס: (180,48) → (48,36) → (36,12) → (12,0) → התשובה 12
מסלול אוקלידס, צעד אחר צעד
לזוג 180 ו-48:
| צעד | a | b | a mod b |
|---|---|---|---|
| 1 | 180 | 48 | 36 |
| 2 | 48 | 36 | 12 |
| 3 | 36 | 12 | 0 |
| 4 | 12 | 0 | עוצרים — gcd = 12 |
שלושה צעדים בלבד למספרים תלת־ספרתיים. היעילות הזו היא הסיבה שהאלגוריתם נמצא בשימוש גם בקריפטוגרפיה, שם המספרים הם בעלי מאות ספרות — ושם פירוק לגורמים ראשוניים היה בלתי מעשי לחלוטין.
איפה זה שימושי
- צמצום שברים. מחלקים מונה ומכנה ב-gcd. 48/180 מצטמצם ל-4/15 בחלוקה ב-12. לכך יש באתר מחשבון שברים.
- חיבור שברים. המכנה המשותף הנוח ביותר הוא ה-lcm של המכנים.
- מחזורים נפגשים. שני אוטובוסים שיוצאים כל 12 ו-18 דקות ייצאו יחד כל 36 דקות — ה-lcm.
- ריצוף. הריבוע הקטן ביותר שניתן לרצף באריחים של 48 על 180 הוא בצלע 720.
- העברת הילוכים. יחסי שיניים בגלגלי שיניים מחושבים ב-gcd וב-lcm.
שאלות נפוצות
מה המחלק המשותף הגדול של 48 ו-180?
12. זה המספר הגדול ביותר שמחלק את שניהם בלי שארית.
איך מחשבים כפולה משותפת קטנה?
מכפילים את שני המספרים ומחלקים במחלק המשותף הגדול. ב-48 ו-180: 8,640 חלקי 12 שווה 720.
מה זה אלגוריתם אוקלידס?
שיטה למצוא gcd בהחלפה חוזרת של הזוג (a,b) בזוג (b, a mod b) עד שהשני מתאפס. היא יעילה מאוד ועובדת גם במספרים עצומים.
מה זה מספרים זרים?
שני מספרים שה-gcd שלהם 1, כלומר אין להם גורם משותף. 8 ו-15 זרים, ולכן ה-lcm שלהם הוא פשוט 120.
איך מצמצמים שבר בעזרת gcd?
מחלקים את המונה ואת המכנה ב-gcd שלהם. 48/180 עם gcd של 12 מצטמצם ל-4/15, שהוא השבר בצורתו המצומצמת.