a | c and b | c implies ab | cd where d = gcd(a, b)

定理
#

$ a, b, c \in \mathbb{Z}$について$a | c \land b | c \implies ab | c d$ where $d = gcd(a, b)$

仮定より、 $a | c \implies \exists x \in \mathbb{Z}: c = ax $ $b | c \implies \exists y \in \mathbb{Z}: c = by $ である。($|$の定義そのもの)

$d = gcd(a,b)$なので、 $\exists a’ \in \mathbb{Z}: a = a’d$、 $\exists b’ \in \mathbb{Z}: b = b’d$ がなりたち、かつ、$gcd(a’, b’)=1$である。

いま、$ab | cd$の$ab$について、$ab = (a’d)(b’d)=d^{2}a’b’$である。

これに対して、$cd$をうまく変形して$ab | cd$であることを示していく。

$cd$の$c$に着目すると、$c = ax, c=by$、$a=a’d, b=b’d$より、$c = a’dx, c= b’dy$と、$c$が2通りに表される。

$c$は$a’d, b’d$の公倍数であることがわかる。
よって、$c$は$lcm(a’d,b’d)$の倍数である。

$gcd(p,q) \cdot lcm(p,q)=pq$なので¹、 $$ lcm(a’d, b’d)=\frac{(a’d)(b’d)}{gcd(a’d,b’d)} \\ = \frac{d^{2}a’b’}{d} \\ = da’b' $$

であり、$c$はある$t \in \mathbb{Z}$で$c=(da’b’)t$と表される。

$ab=d^{2}a’b’, cd = (d^{2}a’b’)t $より、 $ab t = cd$という関係を得るので$ab | cd$が示される。