מחלק משותף וכפולה משותפת
מחלק משותף גדול ביותר (מ.מ.ג) וכפולה משותפת קטנה (כ.מ.ק) — עם אלגוריתם אוקלידס.
ה־מ.מ.ג (Greatest Common Divisor) הוא המספר השלם החיובי הגדול ביותר שמחלק שני מספרים (או יותר) ללא שארית. ה־כ.מ.ק (Least Common Multiple) הוא המספר החיובי הקטן ביותר שמתחלק על־ידי שני המספרים ללא שארית. שניהם קשורים זה לזה דרך הזהות a · b = gcd(a, b) · lcm(a, b).
אלגוריתם אוקלידס — התהליך: חלקי את הגדול בקטן, החלפי את הגדול בקטן ואת הקטן בשארית, וחזרי. ברגע שהשארית 0 — המחלק האחרון הוא ה־מ.מ.ג. השיטה עובדת כי כל מחלק משותף של שני מספרים מחלק גם את השארית שלהם.
- gcd(60, 24): 60 = 2·24 + 12 → 24 = 2·12 + 0 → מ.מ.ג = 12
- gcd(1071, 462): 1071 = 2·462 + 147 → 462 = 3·147 + 21 → 147 = 7·21 + 0 → מ.מ.ג = 21
- lcm(12, 18) = 12·18 / gcd(12, 18) = 216 / 6 = 36
איך משתמשים
מ.מ.ג — מחלק משותף גדול ביותר הוא המספר השלם הגדול ביותר שמחלק את כל המספרים שהוזנו ללא שארית. כ.מ.ק — כפולה משותפת קטנה ביותר הוא המספר החיובי הקטן ביותר שכל המספרים שהוזנו מחלקים אותו ללא שארית.
המחשבון משתמש באלגוריתם אוקלידס ל־מ.מ.ג ובנוסחה a · b / gcd(a, b) ל־כ.מ.ק. בנוסף, מוצג פירוק לגורמים ראשוניים: ה־מ.מ.ג הוא מכפלת המינימום של כל גורם משותף, וה־כ.מ.ק הוא מכפלת המקסימום של כל גורם.
- אלגוריתם אוקלידס — חלקי את הגדול בקטן, החליפי, חזרי. עצרי כשהשארית 0; המחלק האחרון הוא ה־מ.מ.ג.
- 3 מספרים— לחצי על "+הוסף מספר נוסף" כדי להזין שלישי. הצעדים מתבצעים בזוגות.
- שימושים — צמצום שברים (מ.מ.ג), מציאת מכנה משותף (כ.מ.ק), חישוב סיבובי גלגלי שיניים, סנכרון אירועים מחזוריים ועוד.