$100$以下の相異なる合成数が5個あるとき, それらのうち少なくとも2つは共通の素因数を持つことを証明してください｡
まず, 一般に, $n$を合成数とすると, $n$には$\sqrt{n}$以下の素因数が少なくとも1つ含まれていることを示します｡ この事実はテキストで証明されていますが(参考:素数が無限個あることについての考察の定理), テキストとは少し異なる証明を紹介します｡
$n$が合成数なので, 素数$p, q$で$pq \mid n$となるものが存在します｡ ($p=q$の可能性もあります｡) このとき, 一般性を失うことなく$p \leq q$とします｡ すると \[n \geq pq \geq p^2\] となることから$p\leq \sqrt{n}$を得ます｡ この議論でわかったことは, 合成数$n$には$\sqrt{n}$以下の素因数が少なくとも1つ含まれているということです｡
この問題では$100$以下の合成数を考えているので, 各合成数には$\sqrt{100}=10$以下の素因数が含まれることがわかります｡ $10$以下の素数は$2, 3, 5, 7$の4つのみです｡ つまり, $5$個の合成数のうち少なくとも2つには$2, 3, 5, 7$の素数のうちどれかを共有しなければならないことがわかりました｡