数学 – 整数 - 最大公約数(整数の最大公約数)

代数系入門
(岩波書店)
松坂 和夫 (著)

学習環境

• 数式入力ソフト(TeX, MathML): MathType
• MathML対応ブラウザ: Firefox、Safari
• MathML非対応ブラウザ(Internet Explorer, Google Chrome...)用JavaScript Library: MathJax

代数系入門 (松坂 和夫(著)、岩波書店)の第1章(整数)、3(最大公約数)、問1.を解いてみる。

問1.

$d_{\mathrm{n-1}}$を$a_1,a_2,···,a_{n-1}$ の最大公約数とする。

そのとき、
$\begin{array}{l}{a}_1{x}_1+a_x{x}_2+···+a_n{x}_n\\ =d_{n-1}x+a_n{x}_n\end{array}$
となるので、
$a_1{x}_1+a_x{x}_2+···+a_n{x}_n$
は、$\left(d_n-1,a_n\right)=d_n$ のすべての倍数の集合と一致する。

よって、帰納法より$d_n$は、$a_1,a_2,···,a_n$の最大公約数となる。

証明終。