1からn以下の自然数を二つの互いに素な集合に分けて各集合に属する自然数の積が同じになるようにできるか

ツイッターで見かけた問題

 

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中の最大素数であることに矛盾する。