本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
整数の積と素数の関係
素数$p$と整数$m_{1},\ldots,m_{k}$に対し，
\begin{align}
M &= \prod_{i=1}^{k}m_{i}
\end{align}
M &= \prod_{i=1}^{k}m_{i}
\end{align}
が$p$で割り切れるならば，$m_{i}$のいずれかが$p$で割り切れる。
証明
帰納法を用いて示しましょう。$k{=}2$のとき，$M{=}m_{1}m_{2}$が$p$で割り切れるとします。$\gcd(m_{1},p){=}1$のときは$\gcd(m_{2},p){=}p$となるため，$m_{2}$が$p$で割り切れます。$\gcd(m_{1},p){=}p$のときは$m_{1}$が$p$で割り切れます。したがって，$k{=}2$のときは題意を満たします。$k{>}2$のとき，
\begin{align}
M_{k-1} &= \prod_{i=1}^{k-1}m_{i}
\end{align}
M_{k-1} &= \prod_{i=1}^{k-1}m_{i}
\end{align}
とおくと，$M{=}M_{k-1}m_{k}$に対して$k{=}2$のときと全く同様の議論を適用することができます。したがって，帰納法より一般の$k$に対して題意が満たされることが示されました。
コメント