 |
מחלק משותף מקסימלי
| Wikipedia ויקיפדיה העברית - האנציקלופדיה החופשית | Download this dictionary |
מחלק משותף מקסימלי
בתורת המספרים, מחלק משותף מקסימלי (או מחלק משותף גדול ביותר, ממג"ב; וכן gcd קיצור של greatest common divisor) של שני מספרים שלמים הוא המספר הגדול ביותר שמחלק את שניהם. למשל, המחלק המשותף המקסימלי של 12 ו־18 הוא 6. במושג זה, שהוא אבן פינה בתורת המספרים האלמנטרית, עסק כבר אוקלידס, שאף כלל בספרו, יסודות, אלגוריתם לחישוב המחלק המשותף המקסימלי.
המחלק המשותף המקסימלי של שני מספרים הוא מכפלה של כל הגורמים הראשוניים המשותפים לשני המספרים. תכונתו החשובה ביותר של המחלק המשותף המקסימלי היא שאפשר להציג אותו כצירוף שלם של שני הגורמים שלו. לדוגמה, המחלק המשותף המקסימלי של 9 ו- 14 הוא 1, ואפשר להציג 
. תכונה זו מאפשרת לחשב הפכי מודולרי ולפתור משוואות מודולריות; מכיוון שניתן למצוא את הצירוף בצורה יעילה, עולה מכך שניתן לבצע חשבון מודולרי בצורה יעילה.
מקובל לסמן את המחלק המשותף המקסימלי של שני מספרים 
בסימון 
, או בקיצור 
.
| להמשך המאמר ראה Wikipedia.org... |
© מאמר זה משתמש בתוכן מ-ויקיפדיה® וכפוף לרשיון לשימוש חופשי במסמכים של גנו GNU Free Documentation License וכפוף לרישיון Creative Commons ייחוס-שיתוף זהה
