ツイッターで見かけた問題
1からn以下の自然数を二つの互いに素な集合に分けて各集合に属する自然数の積が同じになるようにできるか
不可能。
証明
上の条件は1からn以下の自然数の積の素因数分解(以下A)の各素数の指数が偶数であることと同値であるからA中の最大素数(以下p)の指数が偶数でないことを示す。
n=pのとき
A中のpの指数が1なので不可能である。
n≠pのとき
pより大きい合成数はpで割り切れない(※)のでA中のpの指数は1であり不可能である。
(※)pより大きい合成数はpで割り切れないことの証明 pより大きい合成数がpで割り切れると仮定する。 その合成数はqpで表せq≧2である。p<p'<2pを満たす素数p'が存在する(ベルトラン・チェビシェフの定理)からp<p'<qp≦nでありpがA中の最大素数であることに矛盾する。