D - Together Square

この問題では、以下の命題が重要そうです。

$i\times j$ が平方数となるための必要十分条件は、任意の素数 $p$ について、 $i,j$ に含まれる $p$ の個数の偶奇が等しい

厳密な証明までは必要なさそうですが、一応理解を深めるため、ここでは証明しておきます。(素人なので、間違っていたらすみません)

まず、以下の補題を証明します。

整数 $X$ が平方数である $\Leftrightarrow$ 任意の素数 $p$ について、 $X$ に含まれる $p$ の個数が偶数

[証明]

[ $\Rightarrow$ ] $X$ は平方数であるから、 $x=\sqrt{X}$ を満たす整数 $x$ が存在する。 $x$ の素因数分解を $x=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k}$ とすると、
$X=x^2=(p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k})\times (p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_l})=p_1^{2a_1}\times p_2^{2a_2}\times \cdots \times p_k^{2a_k}$
となり、示された。

[ $\Leftarrow$ ] $X$ の素因数分解を $X=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k}$ とすると、 $a_1,a_2 ,..., a_k$ は偶数なので、
$x=p_1^{\frac{a_1}{2}}\times p_2^{\frac{a_2}{2}}\times \cdots \times p_k^{\frac{a_k}{2}}$
を満たす整数 $x$ が存在し、先程と同様な議論で $x^2=X$ となるため、 $X$ は平方数である。

では、元の命題を証明してみます。

[証明]

[ $\Rightarrow$ ]対偶を示す。
ある素数 $p$ について、 $i,j$ に含まれる個数の偶奇が等しくないとする。
偶数個であるものを $p^{2n}$ 、奇数個であるものを $p^{2m+1}$ とおく。
$i\times j$ に含まれる $p$ の個数に着目すると、
$p^{2n}\times p^{2m+1}=p^{2n+2m+1}=p^{2(n+m)+1}$
となり、 $p$ は奇数個となる。補題より、 $i\times j$ は平方数では無い。よって、対偶が示された。

[ $\Leftarrow$ ]任意の素数 $p$ について、 $i,j$ に含まれる個数が共に偶数個である場合、それぞれ $p^{2n},p^{2m}$ とすると、 $i\times j$ に含まれる個数も $p^{2n+2m}=p^{2(n+m)}$ となり偶数である。共に奇数個である場合 $p^{2n+1},p^{2m+1}$ とすると、 $p^{2n+1+2m+1}=p^{2(n+m+1)}$ となり偶数となる。よって、偶奇が等しい場合 $i\times j$ に含まれる任意の素数の個数は偶数個となり、補題より $i\times j$ は平方数である。