זה לא טריוויאלי בכלל
האלגוריתם של אוקלידס למציאת המחלק המשותף המקסימלי של שני מספרים שלמים a ו-b הוא: כל עוד b לא מחלק את a, בצע צעדים 1-3: 1. d מקבל את השארית של a בחילוק ב-b 2. a מקבל את הערך של b 3. b מקבל את הערך של d הערך של b הוא המחלק המשותף המקסימלי. הסבר:לאחר צעד 1 אנו יודעים ש-
a = qb + d
כאשר q הוא שלם כלשהו, ו-d קטן מ-b. מכאן שכל מחלק משותף של a ו-b הוא גם מחלק משותף של b ו-d ולהפך. לכן, לאחר צעד 3, ל-a ול-b אותם מחלקים, ולכן אותו מחלק משותף מקסימלי. מכיוון שהערך של b יורד לאחר כל ריצה של הלולאה, בשלב כלשהו יחלק b את a והלולאה תיעצר. המחלק המשותף המקסימלי של a ו-b כעת הוא כמובן b, ולכן זהו המספר המבוקש.
