מחלק משותף מקסימלי

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

בתורת המספרים, מחלק משותף מקסימלי (Greatest Common Divisor) של שני מספרים שלמים הוא המספר הגדול ביותר המחלק את שניהם.

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

המחלק המשותף המקסימלי של שני מספרים הוא מכפלה של כל הגורמים הראשוניים המשותפים לשני המספרים. תכונתו החשובה ביותר של המחלק המשותף המקסימלי היא שאפשר להציג אותו כצירוף שלם של שני הגורמים שלו. למשל, המחלק המשותף המקסימלי של 9 ו־14 הוא 1, ואפשר להציג . תכונה זו מאפשרת לחשב הפכי מודולרי ולפתור משוואות מודולריות; מכיוון שניתן למצוא את הצירוף בצורה יעילה, עולה מכך שניתן לבצע חשבון מודולרי בצורה יעילה.

מקובל לסמן את המחלק המשותף המקסימלי של שני מספרים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} בסימון הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)} , או בקיצור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,b)} .

שני מספרים שהמחלק המשותף המקסימלי שלהם הוא 1 (כדוגמת 9 ו־14) נקראים מספרים זרים או "ראשוניים הדדית".

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

תכונות המחלק המשותף המקסימלי

המחלק המשותף המקסימלי של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} מוגדר היטב, פרט למקרה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a=b=0} (אז כל מספר מחלק את שניהם).

מקרים מיוחדים אחרים הם: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,a)=a\ ;\ (a,0)=a\ ;\ (a,1)=1} .

תכונה חשובה נוספת, העומדת בבסיס ההגדרה של חבורת אוילר: אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} זרים, אזי לכל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} מתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ (n,ab)=(n,a)(n,b)} . כמו כן, הוא מחלק כל צירוף לינארי במקדמים שלמים של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} (ולכן בפרט הוא המספר החיובי הקטן ביותר שניתן לקבל כצירוף לינארי במקדמים שלמים שלהם).

חישוב המחלק המשותף המקסימלי

את המחלק המשותף המקסימלי של שני מספרים אפשר לחשב בנקל מתוך הפירוק לגורמים שלהם; כך לדוגמה המחלק המשותף המקסימלי של 495 ו-525 הוא 15, לפי החישוב:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gcd(495,525)=\gcd(3^2\cdot5\cdot11,3\cdot5^2\cdot7)=3\cdot5=15}

עם זאת, מציאת הפירוק לגורמים היא בעיה קשה, והרבה יותר קל מבחינה חישובית למצוא את המחלק המשותף המקסימלי ישירות, ללא חישוב הגורמים הראשוניים.

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

האלגוריתם מבוסס על אבחנה יסודית: לכל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b,q,r} , המחלקים המשותפים של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b,r} הם גם המחלקים המשותפים של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b,bq+r} . לפיכך, לשני הזוגות יש אותו מחלק משותף מקסימלי: .

באופן רקורסיבי ניתן להגדיר את האלגוריתם בצורה הבאה: לחישוב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,b)} כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a>b}

  1. אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b=0} התוצאה היא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} .
  2. אחרת, חלק את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} ומצא את השארית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0\le r<b}  ; התוצאה היא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (b,r)} (שאותה יש לחשב בעזרת אותו אלגוריתם עצמו).

ידוע שמספר פעולות החילוק בהפעלת האלגוריתם אינו עולה על הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \log_\varphi(a)} (כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \varphi} יחס הזהב), כאשר החישוב הארוך ביותר (עבור מספרים בגודל נתון) מתרחש בחישוב המחלק המשותף המקסימלי של מספרי פיבונאצ'י עוקבים. מכאן שמציאת המחלק המשותף המקסימלי היא יעילה מבחינה חישובית; האלגוריתם פועל במהירות גם עבור מספרים גדולים, בני מאות ספרות.

דוגמה

המחלק המשותף המקסימלי של 1071 ו־1029 הוא 21. נראה זאת באמצעות האלגוריתם האוקלידי:

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a}
42 1 1029 1071
21 24 42 1029
0 2 21 42
21 0

הצגת המחלק המשותף המקסימלי כצירוף שלם של גורמיו

בגרסה מורחבת מעט, מאפשר האלגוריתם האוקלידי לא רק למצוא את המחלק המשותף המקסימלי של שני מספרים, אלא גם להציג אותו כצירוף של מכפלות שלמות של שני המספרים, כלומר: אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)=r} ניתן למצוא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m,n\in\Z} עבורם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ma+nb=r} . האבחנה המרכזית בחישוב היא האבחנה הבאה: אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a=qb+r} , וכבר ידועה לנו הצגה של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (b,r)} כצירוף לינארי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (b,r)=mb+nr} , ניתן לקבל משתי המשוואות את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (b,r)} כצירוף לינארי של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} באמצעות הצבה פשוטה: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r=a-qb} ולכן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,b)=(b,r)=mb+nr=mb+n(a-qb)=na+(m-qn)b} .

ניתן לסכם את האמור לעיל באלגוריתם הבא:

Extended_GCD(a,b)
1. if b == 0 return [a,1,0]
2. q = a/b, r = a%b
3. [d,m,n]=Extended_GCD(b,r)
4. return [d,n,m-qn]

יעילות האלגוריתם זהה בסדר הגודל שלה ליעילות האלגוריתם הפשוט; מספר האיטרציות שמבצע האלגוריתם נותר זהה, ולכל איטרציה התווספו רק חישובים בסיסיים (מציאת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} , חישוב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m-qn} ).

מחלק משותף מקסימלי בתחומי שלמות כלליים

בכל חוג קומוטטיבי אפשר להגדיר מחלקים: אבר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} מחלק אבר , אם קיים אבר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} עבורו הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b=ta} . יחס החילוק שהוגדר כאן הוא מעין יחס סדר חלש (הוא אינו אנטי־סימטרי), ובעזרתו אפשר לדבר על "מחלק מקסימלי" גם בחוגים שאין בהם יחס סדר טבעי:

  • אבר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d} הוא מחלק משותף מקסימלי של אברים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} , אם הוא מחלק את שניהם וכל אבר אחר המחלק את שניהם – מחלק את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d} .

הגדרה זו מתלכדת עם ההגדרה הרגילה, המתאימה רק לחוג השלמים.

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

  • האידאל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \langle d\rangle} הוא מחלק משותף מקסימלי של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} אם זהו האידאל הראשי המינימלי המכיל את האידאל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \langle a,b\rangle} .

ישנם תחומי שלמות מיוחדים, שבהם תמיד קיים מחלק משותף מקסימלי. אחת הדוגמאות היא תחום פריקות יחידה: בחוג כזה, אפשר לכתוב כל זוג אברים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} כמכפלות

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a=u p_1^{t_1}\ldots p_n^{t_n},b=v p_1^{s_1}\dots p_n^{s_n}}

כאשר הפיכים ו- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_1,\ldots,p_n} הם ראשוניים של החוג, שאינם ידידים זה לזה. במקרה זה, המחלק המשותף המקסימלי הוא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_1^{\min(t_1,s_1)}\ldots p_n^{\min(t_n,s_n)}} .

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

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

כלי להדגמת רקורסיה

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

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

ראו גם

קישורים חיצוניים

סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0