הצגת המקור של הדף "אלגוריתם אוקלידס"

'''אלגוריתם אוקלידס''' הוא [[אלגוריתם]] [[אריתמטיקה|אריתמטי]] המאפשר למצוא, בהינתן שני [[מספר טבעי|מספרים טבעיים]], את ה[[מחלק משותף מקסימלי|מחלק המשותף המקסימלי]] שלהם.

התיעוד הקדום ביותר של האלגוריתם הוא בספר [[יסודות (ספר)|יסודות]] של [[אוקלידס]], בסביבות שנת [[300]] לפני הספירה. זהו אחד האלגוריתמים העתיקים ביותר הנמצאים בשימוש היום.

האלגוריתם הוא אחד מהכלים המרכזיים ב[[תורת המספרים]] ויש לו שימושים רבים, לדוגמה ב[[צופן]] [[RSA]].

==רקע==
המחלק המשותף המקסימלי של מספרים, המסומן <math>\gcd\{a,b\}</math>, היא פעולה המקבלת שני מספרים טבעיים, ומחזירה את המספר הגדול ביותר ש[[מחלק]] את שניהם.

לדוגמה, המחלק המשותף המקסימלי של 36 ו-24 הוא 12, מאחר שהמספר מחלק את שניהם ואין מספר גדול יותר בעל תכונה זאת.

תמיד יש מספר כזה כיוון שהמספר אחד מחלק כל מספר. ואכן המחלק המשותף המקסימלי של שני [[מספר ראשוני|מספרים ראשוניים]] (כלומר זרים) הוא אחד.

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

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

האלגוריתם מבוסס על העיקרון הבא: הוספת כפולה של אחד המספרים למספר השני, אינה משנה את המחלק המשותף הגדול ביותר. בניסוח מתמטי, אם <math>a,b,q</math> מספרים טבעיים אז מתקיים: <math>\gcd\{a,b\}=\gcd\{a,b+qa\}</math>. 

בתכונה זו ניתן להשתמש בכיוון ההפוך – במקום להגדיל את אחד המספרים, מקטינים אותו: לכל זוג מספרים <math>a>b</math>, ניתן לחשב את ה[[חילוק#חילוק עם שארית|שארית]] <math>r</math> מחלוקת <math>a</math> ב-<math>b</math>, כאשר <math>a=qb+r,0\le r\le b-1</math>. מכאן מתקבל השוויון <math>\gcd\{a,b\}=\gcd\{b,r\}</math>, שבו הוחלף המספר הגדול <math>a</math> במספר <math>r</math> קטן יותר משני המספרים המקוריים, בלי לשנות את המחלק המשותף. אפשר להמשיך בתהליך שוב ושוב עם מספרים קטנים יותר ויותר, עד שמגיעים לזוג שאחד המספרים בו הוא 0; <math>\gcd\{c,0\}=c</math>, ולפיכך נמצא המחלק המשותף הגדול ביותר.

באופן [[רקורסיה|רקורסיבי]] ניתן להגדיר את האלגוריתם בצורה הבאה: לחישוב <math>\gcd\{a,b\}</math> כאשר <math>a>b</math>, אם b הוא 0, התוצאה היא a. אחרת, חלק את <math>a</math> ב-<math>b</math> ומצא את השארית <math>r</math>; התוצאה היא <math>\gcd\{b,r\}</math> (שאותה יש לחשב בעזרת אותו אלגוריתם עצמו).

באופן כללי, ניתן להשתמש באלגוריתם בכל [[חוג אוקלידי]]. כך לדוגמה ניתן להשתמש באלגוריתם כדי למצוא את המחלק המשותף המקסימלי של שני [[פולינום|פולינומים]] מעל [[שדה (מבנה אלגברי)|שדה]].

===הוכחה===
ראשית יש [[הוכחה|להוכיח]] את השוויון <math>\gcd\{a,b\}=\gcd\{a,b+qa\}</math>.
#נניח כי <math>d</math> מחלק את <math>a,b</math>. אז קיימים <math>n_1,n_2</math> טבעיים עבורם <math>a=n_1d,b=n_2d</math>. מכאן
#:<math>b+qa=n_2d+qn_1d=(n_2+qn_1)d</math>
#:כלומר <math>d</math> מחלק את <math>b+qa</math>, ומכאן שהוא מחלק משותף של <math>a,b+qa</math>.
#נניח כי <math>d</math> מחלק את <math>a,b+qa</math>. אז קיימים <math>n_1,n_2</math> טבעיים עבורם <math>a=n_1d,b+qa=n_2d</math>. מכאן
#:<math>b=(b+qa)-qa=n_2d-qn_1d=(n_2-qn_1)d</math>
#:כלומר <math>d</math> מחלק את <math>b</math>, ומכאן שהוא מחלק משותף של <math>a,b</math>.
קיבלנו שמספר הוא מחלק משותף של <math>a,b</math> [[אם ורק אם]] הוא מחלק משותף של <math>a,b+qa</math>. לכן [[קבוצה (מתמטיקה)|קבוצת]] המחלקים המשותפים של הזוגות זהה, ובפרט האיבר המקסימלי שלהם זהה. מכאן <math>\gcd\{a,b\}=\gcd\{a,b+qa\}</math>.

==דוגמה==
[[קובץ:Euclidean algorithm 1071 462.gif|ממוזער|שמאל|הדגמה מונפשת של שימוש באלגוריתם אוקלידס לחישוב <math>\gcd\{1071,462\}</math>]]

נחשב את המחלק המשותף המקסימלי של 1071 ו-462, או <math>\gcd\{1071,462\}</math>:
*462 נכנס ב-1071 פעמיים, והשארית היא 147. לפיכך עלינו למצוא את <math>\gcd\{462,147\}</math>.
*147 נכנס ב-462 שלוש פעמים, והשארית היא 21. לפיכך עלינו למצוא את <math>\gcd\{147,21\}</math>.
*21 נכנס ב-147 7 פעמים בדיוק, כלומר בשארית 0. לפיכך עלינו למצוא את <math>\gcd\{21,0\}</math>.
*מאחר שהמספר הקטן הוא 0, התשובה היא 21, וזו גם התשובה לשאלה המקורית.
לפתרון ניתן לתת משמעות גאומטרית כמודגם באיור: 21 הוא אורך הצלע של האריח הריבועי הגדול ביותר שמאפשר לרצף במדויק את המלבן שצלעותיו הן 1071 ו-462.

;דוגמה למימוש האלגוריתם בצורה רקורסיבית בקוד ([[פייתון]])
<syntaxhighlight lang="python" line="1">
def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)
</syntaxhighlight>

==יעילות==
מבחינת [[סיבוכיות]] [[חישוביות|חישובית]], האלגוריתם [[אלגוריתם יעיל|יעיל]]. מספר הפעולות הנדרשות לביצוע אינו עולה על <math>\log_{\varphi}(a)</math> (<math>\varphi</math> הוא [[יחס הזהב]]). על כן הסיבוכיות שלו היא [[לוגריתם|לוגריתמית]]. ניתן להגיד שמספר הפעולות אינו עולה על פי-5 ממספר ה[[ספרה|ספרות]].

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

==אלגוריתם אוקלידס המורחב==
אחת התכונות החשובות של המחלק המשותף המקסימלי היא שניתן להציג אותו בצורה הבאה: <math>\gcd\{a,b\}=n_1a+n_2b</math>, כאשר <math>n_1,n_2</math> [[מספר שלם|שלמים]]. 

ניתן לחשב את <math>n_1,n_2</math> באמצעות אלגוריתם אוקלידס בעזרת התכונה שאם כל פעם השתמשנו ב-<math>a=r+qb</math>, אז <math>r=a-qb</math>. לפיכך, אם אנחנו יודעים בשלב מסוים איך להציג את שני המספרים <math>a,b</math> בצורה <math>n_1a+n_2b</math> (ההתחלה פשוטה: <math>n_1=1,n_2=0</math> או להפך) ניתן להציב בביטוי <math>r=a-qb</math> ולהתקדם בשלבי האלגוריתם עד להצגה הרצויה.

לדוגמה, נמצא בדוגמה להלן את ההצגה של 10 כ-<math>100n_1+230n_2</math>:
*<math>230=0\cdot100+1\cdot230</math>
*<math>100=1\cdot100+0\cdot230</math>
*<math>30=230-2\cdot100=-2\cdot100+1\cdot230</math>
*<math>10=100-3\cdot30=100-3\cdot(-2\cdot100+1\cdot230)=7\cdot100-3\cdot230</math>
לפיכך: <math>n_1=7,n_2=-3</math>.

האלגוריתם המורחב שימושי בחשבון מודולרי, למשל לצורך מציאת [[הופכי כפלי מודולרי]], עבור שני [[מספרים זרים]]. 

מידת סיבוכיות האלגוריתם המורחב היא מאותו [[סדר גודל]] של הרגיל, מאחר שאין צורך לבצע [[איטרציה|איטרציות]] נוספות אלא רק חישובים בסיסיים.

==ראו גם== 
*[[מחלק משותף מקסימלי]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
*{{MathWorld|EuclideanAlgorithm}}
*[http://textuploader.com/5ebyk מימוש האלגוריתם רקורסיבית בשפת C# או C או] ++C
*[http://textuploader.com/5ebyg מימוש האלגוריתם רקורסיבית ב-Python]
*[http://textuploader.com/5ebyz מימוש האלגוריתם רקורסיבית ב-JS]
*{{בריטניקה}}
*[https://www.extendedeuclideanalgorithm.com/xea.php הסבר אלגוריתם אוקלידס המורחב] ([https://www.extendedeuclideanalgorithm.com/xea.php אנגלית] )

{{בקרת זהויות}}

[[קטגוריה:חילוק]]
[[קטגוריה:אלגוריתמים|אוקלידס]]
[[קטגוריה:אוקלידס]]