[開設 07/27/23=MM/DD/YY]

「命題 3 (ℕ, lcm, gcd) と (Dm, lcm, gcd) は 分配束である」の証明

最小公倍数と最大公約数に関する分配律
このページでは， | を整除関係， l, m, n, m′, n′ などは すべて正の整数とし， 簡単のため， 最小公倍数 lcm を ⋎， 最大公約数 gcd を ⋏ で表す． すなわち， m⋎n = lcm{m, n}, m⋏n = gcd{m, n} である．
次のことは中学または高校で学んでいると思うので， これを証明なしに用いる．
(∗)   m = m′g, n = n′g とするとき，
m⋏n = g   ⇔   m′⋏n′ = 1
なお， m′⋏n′ = 1 は， m′ と n′ が互いに素 (relatively prime) ということである．
補題 （積に関する分配律）
(lm)⋏(ln) = l(m⋏n).
証明. m = m′(m⋏n), n = n′(m⋏n) とおくと， (∗) より m′⋏n′ = 1 である． このとき， lm = m′[l(m⋏n)], ln = n′[l(m⋏n)] なので， m′⋏n′ = 1 と (∗) より (lm)⋏(ln) = l(m⋏n) である． (Q.E.D.)

(ℕ, ⋎, ⋏) が分配束であることの証明
「分配律と分配束」の 命題 5 と 命題 6 より，
(l ⋎m) ⋏ (l ⋎n) | l ⋎(m⋏n).
を示せばよい． g = m⋏n, m = m′g, n = n′g とおくと， (∗) より m′⋏n′ = 1 である． l | (l ⋎g) であり， 一方 m′(l ⋎g) は l ⋎g の 倍数だから (l ⋎g) | [m′(l ⋎g)] なので， 推移律より l | [m′(l ⋎g)] である． また， l ⋎g が g の倍数であることから m′(l ⋎g) は m′g の倍数なので， m = (m′g) | [m′(l ⋎g)] である． よって m′(l ⋎g) は {l, m} の上界である． そして l ⋎m は {l, m} の最小上界だから， (l ⋎m) | [m′(l ⋎g)] となる． 同様に (l ⋎n) | [n′(l ⋎g)] も言える． したがって， 配布資料「束」命題 5 (ii)， 上の補題， m′⋏n′ = 1 と g = m⋏n を順に用いて
(l ⋎m) ⋏ (l ⋎n) ≼ [m′(l ⋎g)] ⋏ [n′(l ⋎g)] = (m′⋏n′) (l ⋎g) = l ⋎g = l ⋎(m⋏n).
(Q.E.D.)

(Dm, ⋎, ⋏) が分配束であることの証明
(Dm, ⋎, ⋏) は (ℕ, ⋎, ⋏) の部分束なので， (ℕ, ⋎, ⋏) が分配束であることと 「分配律と分配束」命題 4 より明らか． (Q.E.D.)

付録： 積に関する分配律 その 2
次の分配律も成り立つ．
(lm)⋎(ln) = l(m⋎n)
これを示そう． まず，上の (∗) の拡張
(∗∗)   m = m′g, n = n′g とするとき，
m⋏n = g   ⇔   m′⋏n′ = 1   ⇔   m⋎n = m′n′g.
（これも中学または高校で学んだはずである） と，
m = m′g, n = n′g のとき mn = m′n′g 2 であることから， 次の (☆) が解る．
(☆)   mn = (m⋎n)(m⋏n)
（この (☆) も中学または高校で学んでいるかもしれない）．
(☆) と上の補題を用いると
(lm)⋎(ln) = (lm)(ln) / [(lm)⋏(ln)]   (∵ (☆))
= (lm)(ln) / [l(m⋏n)] (∵ 上の補題)
= l [mn / (m⋏n)]
= l (m⋎n). (∵ (☆))
「分配律と分配束」命題 3
離散構造（室伏）のホーム
murofusi "at mark" c "dot" titech "dot" ac "dot" jp ("at mark" -> @ / "dot" -> .)