『最大公約数の求め方』◆広島県 清川 育男 さんからの解答。 ２つの数をＮ，Ｍ。Ｎ＞Ｍとする。 ＮをＭで割る。剰余をＲ1とする。 もしＲ1＝０ならＭが最大公約数。 ＭをＲ1で割る。剰余をＲ2とする。 もしＲ2＝０ならＲ1が最大公約数。 Ｒ1をＲ2で割る。 剰余をＲ3とする。 もしＲ3＝０ならＲ2が最大公約数。 Ｒ2をＲ3で割る。 剰余をＲ4とする。 もしＲ4＝０ならＲ3が最大公約数。 このように、Ｒn-1＝１。Ｒn＝０になるまで行う。 Ｍ＞Ｒ1＞Ｒ2＞Ｒ3＞・・・＞０。 例えば、 １）Ｎ＝１５２３、Ｍ＝８１４とする。 １５２３／８１４＝１．．．７０９。 ８１４／７０９＝１．．．１０５。 ７０９／１０５＝６．．．７９。 １０５／７９ ＝１．．．２６。 ７９／２６ ＝３．．．１。 ２６／１ ＝２６。最大公約数は、１。 ２）Ｎ＝２４。Ｍ＝１８とする。 ２４／１８ ＝１．．．６。 １８／６
