互いに素でない2数に関する命題の真偽は？

「$a,b$を自然数、$p$を素数とするとき、以下の命題の真偽を調べよ。

(1)$a$と$b$が互いに素でないならば$a$は$b$の倍数である

(2)$a$と$p$が互いに素でないならば$a$は$p$の倍数である」

(1)

　互いに素とは、最大公約数が$1$であることです。
すると、$a$と$b$が互いに素でないということは、$a$と$b$の最大公約数が$1$でないということになります。

関連：互いに素とは？

別の言い方をすれば、$a$と$b$で共通する割り切れる整数が$1$以外に存在する、あるいは$a$と$b$には共通する素因数が存在する、となります。
また、$a$と$b$のどちらも$1$でないことがいえます。

もし、$1$と$b$以外の$b$の約数の中に$a$がある場合、$a$と$b$の最大公約数は$a$となるため、$a$と$b$は互いに素でないといえます。
このとき、$a$は$b$より小さく、$b$の正の倍数は$b$以上の自然数であるため、$a$は$b$の倍数でないことがわかります。

したがって、上記の場合が命題「$a$と$b$が互いに素でないならば$a$は$b$の倍数である」の反例であり、命題が偽であることがわかります。

　$a$と$b$が互いに素でないとき、$b$に対して$a$はどのような数であるのかについて考えます。
上述の通り、$a$と$b$が互いに素でないとは、$a$と$b$の最大公約数が$1$でないことであり、最大公約数は必ず$a$と$b$の小さい方以下の自然数となります。

$a$と$b$が互いに素でないときの$a$と$b$の最大公約数には、$1$より大きく$a,b$よりも小さいとき、$a$のとき、$b$のときの3通りが考えられます。

1. $1<\gcd(a,b)<\min\{a,b\}$のとき

　$a$と$b$の最大公約数が$1$と$b$以外の$b$の約数$b'$であるとき、$b'$は$a$と$b$の共通の約数であり、

$$\begin{align*}a&=mb'\\[1em]b&=nb'&(m,n:自然数;m\neq n)\end{align*}$$

と書け、$a,b$はともに$b'$の倍数であるといえます。

ここで、$a=mb'$に着目すると$a$は$b$の約数の倍数であるといえます。

2. $\gcd(a,b)=a$のとき

　$a$と$b$の最大公約数が$a$のとき、これは$a\leqq b$であるときに考えられる場合です。

このとき、$b$について$b=na$と書け、$a$は$b$の約数であるといえます。

3. $\gcd(a,b)=b$のとき

　$a$と$b$の最大公約数が$b$のとき、これは$a\geqq b$であるときに考えられる場合です。

このとき、$a$について$a=mb$と書け、$a$は$b$の倍数であるといえます。

上記(1)の反例は2.（ただし、$a<b$）の場合のことであり、1.の場合も反例となります。

(2)

　素数は約数が自身と$1$しかない数のことです。
したがって、$a$と$p$が互いに素でないとき、$a$と$p$の最大公約数は必ず$p$となり、$a$と$p$の大小関係は$a\geqq p$となります。

これは上記の3.の場合であり、このときの$a$は$p$の倍数なので、命題「$a$と$p$が互いに素でないならば$a$は$p$の倍数である」は真であることがわかります。

関連：互いに素とは？

関連：公約数についてこれは正しい？