طریقهٔ اقلیدس برای بزرگ‌ترین قاسم مشترک

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

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

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

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

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