روش اقلیدس برای بزرگ‌ترین شمارندهٔ مشترک (ب.م.م)

نوشتن همهٔ شمارنده‌ها برای عددهای کوچک خوب است، ولی برای عددهای بزرگ وقت زیادی می‌گیرد. بیش از ۲۰۰۰ سال پیش اقلیدس راه کوتاه‌تری پیدا کرد: زنجیره‌ای از تقسیم‌ها. این روش فراتر از کتاب‌های درسی ایران است و این کارگاه تکمیلی است.

عدد بزرگ‌تر را بر عدد کوچک‌تر تقسیم کن. بعد مقسوم‌علیه را بر باقی‌مانده تقسیم کن. همین‌طور ادامه بده: هر بار مقسوم‌علیه، مقسوم تازه می‌شود و باقی‌مانده، مقسوم‌علیه تازه.

وقتی باقی‌مانده صفر شد، بایست. آخرین باقی‌مانده غیرصفر (یعنی آخرین مقسوم‌علیه) همان بزرگ‌ترین شمارندهٔ مشترک (ب.م.م) است.

چرا درست است؟ هر عددی که ۸۴ و ۶۰ را بشمارد، ۸۴ − ۶۰ = ۲۴ را هم می‌شمارد و برعکس. پس شمارنده‌های مشترک ۸۴ و ۶۰ دقیقاً همان شمارنده‌های مشترک ۶۰ و ۲۴ است. هر تقسیم، جفت عددها را با جفت کوچک‌تری عوض می‌کند که بزرگ‌ترین شمارندهٔ مشترک (ب.م.م) آن یکی است.

هر رقم درست سبز می‌شود. اگر گیر کردی، «این مرحله را نشانم بده» را بزن.