2016　広島大学　AO工学部第二類小論文MathJax

【２】　二つの自然数$m\text{，}n\text{（}m\geqq n\text{）}$の最大公約数について考える．

(1)　$m=1001\text{，}n=364$とするとき，$m$と$n$をそれぞれ素因数分解して，最大公約数を求めよ．

(2)　$m$と$n$の最大公約数は次の手続き（互除法）でも求めることができる．

Step1：$n=0$なら$m$が最大公約数．

Step2：$m$を$n$で割った余りを新たな$n\text{，}$もとの$n$を新たな$m$としてStep1に戻る．

　互除法をつかって，$m=1001\text{，}n=364$の最大公約数を求めたときの，$m$と$n$の変化を記述せよ．

(3)　互除法で最大公約数が求められることの証明を以下の手順で行え．

(a)　自然数$g$が$m$と$n$の公約数であるとき，$m=ga$と$n=gb$となる自然数$a$と$b$がある．$g$が$m$と$n$の最大公約数であるとき，$a$と$b$にはどのような関係があるか．

(b)　$m=qn+r$とする自然数$q\text{，}r$があるとき，$m$と$n$の公約数$d$が$n$と$r$の公約数になることを示せ．

(c)　$m=qn+r$とする自然数$q\text{，}r$があるとき，$m$と$n$の最大公約数$g$が$n$と$r$の最大公約数になることを示せ．

(d)　互除法で最大公約数が求められることを証明せよ．

(4)　一般的に，素因数分解によって最大公約数を求めるよりも，互除法の方が簡単に最大公約数を求めることができる．

整数同士の割り算回数（商と余りを求める計算の回数）の観点から二つの方法を比較し，互除法の方が簡単に最大公約数を求めることができる理由を説明せよ．

(5)　互除法は自然数以外にも適用できる．二つの多項式$f(x)$と$g(x)$に上記の手続きを適用したとき，何を求めることができるか説明せよ．また，自然数，多項式以外にも適用できるものがあれば，その理由とともに説明せよ．