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

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

רקע

המחלק המשותף המקסימלי של מספרים, המסומן  או בקיצור , היא פעולה המקבלת שני מספרים טבעיים, ומחזירה את המספר הגדול ביותר שמחלק את שניהם.
לדוגמה, המחלק המשותף המקסימלי של 36 ו-24 הוא 12, מאחר שהמספר מחלק את שניהם ואין מספר גדול יותר בעל תכונה זאת.
דרך אפשרית למציאת המחלק המשותף המקסימלי היא פירוק שני המספרים לגורמים ראשוניים, והכפלת  הגורמים המשותפים. בדוגמה הנ"ל, הפירוק לראשוניים של 36 הוא ‎2×2×3×3 ושל 24 הוא ‎2×2×2×3, הגורמים המשותפים הם 2, 2 ו-3, ומכפלתם היא 12. דרך זו היא אינטואיטיבית, אך אינה שימושית עבור מספרים גדולים, כי פירוק לגורמים הוא פעולה מורכבת ואין שיטה פשוטה לחישובו. אלגוריתם אוקלידס מאפשר את מציאת המחלק המשותף המקסימלי ללא פירוק לגורמים, בדרך פשוטה יחסית. למעשה, שיטות מתקדמות לפירוק לגורמים (לדוגמה אלגוריתם נפת שדה מספרים) משתמשות באלגוריתם אוקלידס.

דרך פעולת האלגוריתם

האלגוריתם מבוסס על העיקרון הבא: הוספת כפולה של אחד המספרים למספר השני, אינה משנה את המחלק המשותף הגדול ביותר. בניסוח מתמטי, אם b,c ו-q מספרים טבעיים אז מתקיים: . 
בתכונה זו ניתן להשתמש בכיוון ההפוך - במקום להגדיל את אחד המספרים, מקטינים אותו: לכל זוג מספרים a,b, כאשר a הוא הגדול בין השניים, ניתן לחשב את השארית c מחלוקת a ב-b, כך ש-. מכאן מתקבל השוויון , שבו הוחלף המספר הגדול a במספר c קטן יותר משני המספרים המקוריים, בלי לשנות את המחלק המשותף. אפשר להמשיך בתהליך שוב ושוב עם מספרים קטנים יותר ויותר, עד שמגיעים לזוג שאחד המספרים בו הוא 0; , ולפיכך נמצא המחלק המשותף הגדול ביותר.
באופן רקורסיבי ניתן להגדיר את האלגוריתם בצורה הבאה: 
לחישוב  ‏(כאשר a>b), אם b הוא 0, התוצאה היא a. אחרת, מחלק את a ב-b ומצא את השארית c; התוצאה היא  (שאותה יש לחשב בעזרת אותו אלגוריתם עצמו).
באופן כללי, ניתן להשתמש באלגוריתם בכל חוג אוקלידי. כך לדוגמה ניתן להשתמש באלגוריתם כדי למצוא את המחלק המשותף המקסימלי של שני פולינומים מעל שדה.

הוכחה

ראשית יש להוכיח את השוויון .
נניח ש-g מחלק את b ו-c. אז קיימים m,n טבעיים כך ש-. מכאן: . כלומר g מחלק את , ומכאן שהוא מחלק משותף של b ושל .
בכיוון ההפוך, נניח ש-h מחלק את  וגם את b. אז קיימים m,n טבעיים כך ש-. מכאן: . כלומר h מחלק את c, ומכאן שהוא מחלק משותף של b ושל c.
קיבלנו שמספר הוא מחלק משותף של  ושל b אם ורק אם הוא מחלק משותף של b ושל c. לכן קבוצת המחלקים המשותפים של הזוגות זהה, ובפרט האיבר המקסימלי שלהם זהה. מכאן .

דוגמה למימוש האלגוריתם בצורה רקורסיבית בקוד JavaScript

1 function Gcd(a, b) {2 if (b == 0) {3     return a;4 }5 return Gcd(b, a % b);6 }
דוגמה למימוש האלגוריתם בצורה רקורסיבית בקוד Python
1 def gcd (a,b):2     if b == 0:3         return a4     return gcd (b, a % b)

יעילות

מבחינת סיבוכיות חישובית, האלגוריתם יעיל. מספר הפעולות הנדרשות לביצוע אינו עולה על  ( הוא יחס הזהב). על כן הסיבוכיות שלו היא לוגריתמית. ניתן להגיד שמספר הפעולות אינו עולה על פי-5 ממספר הספרות.
המקרה הגרוע ביותר (worst case) הוא כאשר מדובר בשני מספרי פיבונאצ'י עוקבים; זאת, כיוון שככל שהמנה המתקבלת בפעולות החילוק קטנה יותר, המספר קָטֶן פחות, ויש צורך ביותר פעולות. במספרי פיבונאצ'י כל המנות הן 1, ועל כן התהליך הוא הארוך ביותר. תכונה זו נתגלתה על ידי גבריאל לאמה.