数学のブログ

最小公倍数と最大公約数 - 整数の組に共通性を探す - 推移律、2つの整数の積と最小公倍数と最大公約数の積、等式

基礎から学ぶ整数論: RSA暗号入門
 楽天ブックス
Yahoo!

学習環境

基礎から学ぶ整数論: RSA暗号入門 (長嶋祐二(著)、福田一帆(著)、コロナ社)の第2章(最小公倍数と最大公約数 - 整数の組に共通性を探す -)、章末問題の問4、5の解答を求めてみる。

4

c | b \land b | a

ならばある整数

q_{1}, q_{2} \in ℤ

が存在して、

\begin{array}{l} b = c q_{1} \\ a = b q_{2} \end{array}

よって、

a = (c q_{1}) q_{2} = c (q_{1} q_{2})

ゆえに

c | a

5

整数a、 bの最大公約数が g ならば、互いに素なある整数

\begin{array}{l} q_{1}, q_{2} \in ℤ \\ (q_{1}, q_{2}) = 1 \end{array}

が存在して、

\begin{array}{l} a = q_{1} g \\ b = q_{2} g \end{array}

よって、

a b = q_{1} g q_{2} g = (q_{1} q_{2} g) g

また、 lがa、 bの公倍数ならば、ある整数

q_{3}, q_{4} \in ℤ

が存在して、

l = q_{3} a = q_{4} b

また、

\begin{array}{l} q_{1} q_{2} g = q_{1} g q_{2} = a q_{2} \\ q_{1} q_{2} g = q_{2} g q_{1} = b q_{1} \end{array}

より、

\begin{array}{l} a | q_{1} q_{2} g \\ b | q_{1} q_{2} g \end{array}

l は a、 b の最小公倍数なので、

l | q_{1} q_{2} g

よってある整数

q \in ℤ

が存在して、

q_{1} q_{2} g = l q

ゆえに、

\begin{array}{l} a q_{2} = q_{3} a q \\ b q_{1} = q_{4} b q \end{array}

\begin{array}{l} q_{2} = q_{3} q \\ q_{1} = q_{4} q \end{array}

よって、 qは

q_{1}, q_{2}

の公約数である。

このことと、

(q_{1}, q_{2}) = 1

から、

q = 1

よって、

q_{1} q_{2} g = l \cdot 1 = l

ゆえに、

a b = (q_{1} q_{2} g) g = l \cdot g

である。

（証明終）