אלגוריתם אוקליד

כעת יש לנו את הכלים על מנת להתמודד עם דוגמא מלמדת מעט מורכבת יותר - כתיבת תוכנית שפותרת בעיה מתמטית אמיתית, אם כי פשוטה. נגדיר את הבעיה:

בהנתן שני מספרים חיוביים \(m, n\), מצאו את המכנה המשותף הגדול ביותר שלהם - השלם הגדול ביותר שמחלק את שניהם (ה-greatest common divisor, או GCD).

לדוגמא, נמצא את ה-GCD של 54 ו-24. על מנת לעשות זאת, נמצא את כל המחלקים של שני המספרים.

המחלקים של 54 הם:

$$ { 1, 2, 3, 6, 9, 18, 27, 54 } $$

ושל 24:

$$ 1, 2, 3, 4, 6, 8, 12, 24 $$

ולכן ע״י מציאת המקסימום של החיתוך בין שתי הקבוצות נקבל:

$$ gcd(54, 24) = 6 $$

הבעיה בפתרון זה הוא שהוא דורש למצוא את כל המחלקים של שני המספרים ואז להצליב ביניהם. עבור מספרים גדולים פעולה זו הופכת להיות מאוד לא יעילה - נחפש פתרון שמאפשר לנו להקטין את גודל המספרים איתם אנו עובדים.

אלגוריתם אוקליד

אלגוריתם אוקליד מאפשר לנו להקטין באופן שיטתי את המספרים להם אנו מוצאים את ה-GCD עד שהבעיה הופכת לפשוטה

Note

נשתמש בסימון \(a | b\) עבור המקרה בו \(b\) הוא מחלק של \(a\) ללא שארית.

בדוגמא הקודמת, שאלנו מהם המחלקים של 54 ו-24. אלגוריתם אוקלידס מציע לנו הצגה אחרת - נכתוב את 54 (הגדול מבין שני המספרים) ככפולה שלמה של הקטן עם שארית. כלומר:

$$ gcd(54, 24) = gcd(24 \cdot 2 + 6, 24) $$

כעת נסמן ב-\(d\) מחלק של 54 ו-24, כלומר \(54 | d\) ו-\(24 | d\). לכן גם מתקיים:

$$ 54 | d \Longrightarrow (24 \cdot 2 + 6) | d \Longrightarrow 6 | d $$

כלומר, \(d\) הוא מחלק של אותה השארית, ולכן גם מתקיים:

$$ gcd(54, 24) = gcd(24 \cdot 2 + 6) = gcd(24, 6) $$

הקטנו משמעותית את הבעיה המקורית! כעת מתקיים גם ש-\(24|6\), ולכן ה-GCD הוא 6.