数学のブログ

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

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

4

c|bb|a

ならばある整数

q1,q2

が存在して、

b=cq1a=bq2

よって、

a=(cq1)q2=c(q1q2)

ゆえに

c|a

5

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

q1,q2(q1,q2)=1

が存在して、

a=q1gb=q2g

よって、

ab=q1gq2g=(q1q2g)g

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

q3,q4

が存在して、

l=q3a=q4b

また、

q1q2g=q1gq2=aq2q1q2g=q2gq1=bq1

より、

a|q1q2gb|q1q2g

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

l|q1q2g

よってある整数

q

が存在して、

q1q2g=lq

ゆえに、

aq2=q3aqbq1=q4bq
q2=q3qq1=q4q

よって、 qは

q1,q2

の公約数である。

このことと、

(q1,q2)=1

から、

q=1

よって、

q1q2g=l·1=l

ゆえに、

ab=(q1q2g)g=l·g

である。

(証明終)