基本情報技術者試験 科目Bの問題です。 最大公約数がなぜ、m と nに求まるのかがわかりません。教えてください。

Question

基本情報技術者試験 科目Bの問題です。
最大公約数がなぜ、m と nに求まるのかがわかりません。教えてください。

Answer 1

試しに 30と12の最大公約数を求めてみます。
ちなみに、gcd(30,12)=6です
1, 2, 3, 5, 6, 10, 15, 30
1, 2, 3, 4, 6, 12 だからね

gcd(30, 12)
m←30
n←12
do
r←30 mod 12 =6
m←12
n←6
r←12 mod 6=0
while (r≠0)
return n=6
−−−−

gcd(30, 12)
m←30
n←12
r←30 mod 12 =6
while (r≠0)
m←12
n←6
r←12 mod 6=0
end while
return n=6