整除に関する定理1

定理

abがcで割り切れ、a,cが互いに素ならば、bはcで割り切れる

証明

問題文は以下のように書き換えることができる。

$$ ab = cq \land \mathrm{gcm(a)} = \lbrace1, a \rbrace \land \mathrm{gcm(b)} = \lbrace1, b\rbrace \Rightarrow b = cq $$

まず

$$ \mathrm{gcm(a)} = \lbrace1, a \rbrace \land \mathrm{gcm(b)} = \lbrace1, b\rbrace $$

より

$$ a \neq c $$

である。ab=cq式において、bは必ずcの合成数である。故に

bはcで割り切れる…Q.E.D