מחלק משותף מקסימלי – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Legobot (שיחה | תרומות)
מ בוט: מעביר קישורי בינויקי לויקינתונים - d:q131752
קוריוז תכנותי + ניטפוק: לא הצירוף הלינארי הקטן ביותר, אלה הצירוף הלינארי *החיובי* הקטן ביותר. תמיד אפשר לקבל 0, שלא לדבר על שליליים.
שורה 11:
== כמה תכונות של המחלק המשותף המקסימלי ==
 
המחלק המשותף המקסימלי של a ו- b מוגדר היטב, פרט למקרה ש- <math>\ a=b=0</math> (אז כל מספר מחלק את שניהם). מקרים מיוחדים אחרים הם: <math>\ (a,0)=a</math>; <math>\ (a,a)=a</math>; <math>\ (a,1)=1</math>. תכונה חשובה נוספת, העומדת בבסיס ההגדרה של [[חבורת אוילר]]: אם a,b זרים, אז לכל n, <math>\ (n,ab)=(n,a)(n,b)</math>. כמו כן, הוא מחלק כל צירוף לינארי במקדמים שלמים של a ו-b (ולכן בפרט הוא המספר החיובי הקטן ביותר שניתן לקבל כצירוף לינארי במקדמים שלמים שלהם).
 
== חישוב המחלק המשותף המקסימלי ==
שורה 84:
 
בין התחומים הראשיים, ה[[חוג אוקלידי|חוגים האוקלידיים]] מתאפיינים בכך שאפשר לבצע בהם חילוק עם שארית. אלו הם בדיוק החוגים שבהם אפשר לממש את האלגוריתם של אוקלידס שתואר לעיל.
 
==כלי להדגמת רקורסיה==
[[פונקציה (תכנות)|פונקציה]] המממשת את האלגוריתם של אוקלידס בצורה רקורסיבית משמשת לעתים קרובות כדי להדגים את העוצמה של שימוש ב[[רקורסיה]] בתכנות. הפונקציה הבאה שמחשבת gcd מפתיעה בפשטותה, בזכות השימוש ברקורסיה. התחביר מתאים למספר שפות קרובות, ביניהן [[C (שפת תכנות)|C]] ו-[[Java]]. ניתן לכתוב פונקציה דומה בכל שפה שתומכת ברקורסיה.
<source lang="c">
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
</source>
 
==ראו גם==