読者です 読者をやめる 読者になる 読者になる

最大公約数と最小公倍数

数学

定理
a, b \in \mathbb{N} とする.ga,bの最大公約数,la,bの最小公倍数とする.
このとき,ab=glが成り立つ.□

(証明)
ga,bの最大公約数であるから,互いに素であるa',b'を用いて
  a=ga'およびb=gb'
と表せる.またla,bの最小公倍数なので
  l=saかつl=tb
と表せる.つまりsa=tbで,両辺をg で約分するとsa'=tb'が成り立つ.
a'b'は互いに素であるから,sb'で割り切れる.
よってs=s'b'と表せる.同様にしてt=t'a'と表せる.
ゆえにs'=t'である.lは最小であるから,s'=t'=1となる.
したがって,l=ga'b'となる.
両辺をg 倍するとgl=ga' \times gb'=abを得る.(証明終)