به نام خدا
الگوریتم اقلیدس: روشی موسوم به روش نردبانی برای یافتن بزرگترین مقسومعلیه مشترک (ب. م. م) دو عدد است. سادهترین نسخۀ الگوریتم اقلیدس، بر این واقعیت استوار است که ب. م. م دو عدد، با ب. م. م عدد کوچکتر و تفاضل آن دو عدد، یکسان است.
نسخۀ سادۀ الگوریتم اقلیدس:
در نسخۀ سادۀ الگوریتم اقلیدس، برای بهدست آوردن ب. م. م دو عدد مثلاً $a$ و $b$ ($a>b$)، ابتدا $b$ را از $a$ کم میکنیم و حاصل مثلاً برابر با عددی مثل $ c$ میشود: $a-b=c$. سپس حاصل (یعنی $c$) را از $b$ کم میکنیم و حاصل برابر با عدد دیگر مثل $d$ میشود: $b-c=d$. و بعد $d$ را از $c$ کم میکنیم و حاصل برابر با عدد دیگری مثل $e$ میشود: $c-d=e$ و این عمل را تا جایی که تفاضل صفر شود ادامه میدهیم، حاصل آخرین تفاضل غیرصفر، برابر با ب. م. م $a$ و $b$ است.
برای مثال، یافتن ب. م. م دو عددِ $585$ و $442$ با استفاده از نسخۀ سادۀ الگوریتم اقلیدس بهاین شکل است:
$$585-442=143$$
$$442-143=299$$
$$299-143=156$$
$$156-143=13$$
$$143-13=130$$
$$130-13=117$$
$$117-13=104$$
$$104-13=91$$
$$91-13=78$$
$$78-13=65$$
$$65-13=52$$
$$52-13=39$$
$$39-13=26$$
$$26-13=13$$
$$13-13=0$$
پس ب. م. م برابر با $13$ است.
نسخۀ استاندارد الگوریتم اقلیدس:
در نسخۀ استاندارد الگوریتم اقلیدس، برای بهدست آوردن ب. م. م دو عدد مثلاً $a$ و $b$ ($a>b$)، ابتدا $a$ را بر $b$ تقسیم میکنیم و خارج قسمت و باقیماندۀ آن بهترتیب برابر با اعدادی مثل $c$ و $d$ میشود. سپس $b$ را بر باقیماندۀ تقسیم قبل (یعنی $d$) تقسیم میکنیم و خارج قسمت و باقیماندۀ آن بهترتیب برابر با اعدادی مثل $e$ و $f$ میشود. سپس $d$ را بر $f$ تقسیم میکنیم و خارج قسمت و باقیماندۀ آن بهترتیب برابر با اعدادی مثل $g$ و $h$ میشود و این عمل را تا جایی که باقیمانده صفر شود ادامه میدهیم، آخرین باقیمانده غیرصفر، برابر با ب. م. م $a$ و $b$ است.
برای مثال، یافتن ب. م. م دو عددِ $585$ و $442$ با استفاده از نسخۀ استاندارد الگوریتم اقلیدس بهاین شکل است:
$$ \frac{585}{442}=1,(باقیمانده:143)$$
$$ \frac{442}{143}=3,(باقیمانده:13) $$
$$ \frac{143}{13}=11,(باقیمانده:0) $$
پس ب. م. م برابر با $13$ است.
