aとbが互いに素のとき、abとa+bも互いに素

互いに素

2つの正の整数 $a$ と $b$ の最大公約数が1のとき、 $a$ と $b$ は互いに素であるといいます。問題を解くときには、共通な素因数をもたないことを使います。素因数とは、素数の約数のことです。

例　10と21は、10=2×5、21=3×7で、別の素数からできているので互いに素です。

注意　上の例のように、 $a$ と $b$ は素数とは限りません。「互いに素」って「互いに素数」ってこと？という人は結構います。

「 $a$ と $b$ が互いに素のとき、 $ab$ と $a+b$ も互いに素」の証明

正の整数（自然数） $a$ と $b$ について、 $a$ と $b$ が互いに素 $\Rightarrow$ $ab$ と $a+b$ が互いに素が成り立つ。

証明　背理法で証明する。 $ab$ と $a+b$ が互いに素でないと仮定すると、 $ab$ と $a+b$ は共通な素因数をもつ。その共通な素因数の1つを $p$ とすると、 $ab$ と $a+b$ は $p$ の倍数だから、

$ab=pm，a+b=pn$ （ $m，n$ は整数）

とかける。 $p$ は素数だから、 $ab=pm$ より、 $a$ が $p$ の倍数であるか、 $b$ が $p$ の倍数である。 $a$ が $p$ の倍数のとき、 $a=pk$ （ $k$ は整数）とおけて、 $a+b=pn$ に代入すると、 $pk+b=pn$ より、 $b=p(n-k)$ となるから、 $b$ も $p$ の倍数である。これは、 $a$ と $b$ が互いに素ということと矛盾する（ $a$ と $b$ が共通な素因数 $p$ をもつから）。 $b$ が $p$ の倍数のときも同様に矛盾する。よって、 $ab$ と $a+b$ は互いに素である。

「 $ab$ と $a+b$ が互いに素のとき、 $a$ と $b$ も互いに素」も成り立つ

これも背理法で証明できます。

証明　 $a$ と $b$ が互いに素でないと仮定すると、 $a$ と $b$ は共通な素因数をもつ。その共通な素因数の1つを $p$ とすると、 $a$ と $b$ は $p$ の倍数だから、 $a=pa'，b=pb'$ （ $a'，b'$ は整数）とおける。これを用いると、 $ab=p^{2}a'b'，a+b=p(a'+b')$ となるから、 $ab，a+b$ はともに $p$ の倍数である。これは $ab$ と $a+b$ が互いに素ということに反する。よって、 $a$ と $b$ は互いに素である。