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

את המחלק המשותף המקסימלי של שני מספרים אפשר לחשב בנקל מתוך ה[[פירוק מספר שלם לגורמים|פירוק לגורמים]] שלהם; למשל, <math>\ \mbox{gcd}(3^2\cdot 5\cdot 11,3\cdot 5^2\cdot 7)=3\cdot 5=15</math>. עם זאת, מציאת הפירוק לגורמים היא בעיה קשה, והרבה יותר קל מבחינה [[סיבוכיות|חישובית]] למצוא את המחלק המשותף המקסימלי ישירות, ללא חישוב הגורמים הראשוניים.