問題
整数の組に対して,次の条件(*)を考える。
(*) は1以上の整数であり,との最大公約数,との最大公約数,との最大公約数はそれぞれ1である。
以下の問いに答えよ。ただし,組とはのとき,かつこのときに限り等しい。
(1) 条件(*)かつをみたす組のうちで,をみたすものをすべて求めよ。
(2) を2以上の整数とし,以下の素数の個数をとする。条件(*)かつをみたす組の個数をを用いて表せ。
(3) を2以上の整数とし,以下の素数の個数をとする。条件(*)かつをみたす組のうちで,をみたすものの個数をを用いて表せ。
方針
条件(*)より,積に現れる各素数の累乗部分は のうちただ1つに丸ごと割り振られる。(1)は の3つの素数ブロックを大小順に列挙する。(2)は に現れる 個の素数ブロックを,順序つきの3つの場所へ割り振るので 通りである。(3)では大小順にするため,順序つきの割り振りを並べ替えでまとめる。特別に2つが等しくなるのは の場合だけであることを使う。
解答
(1)
である。条件(*)より, のどの2つも共通の素因数を持たない。したがって ,, は,それぞれ のうち1つだけに丸ごと入る。
3つの素数ブロックを と見て,大小順 で並べた組を列挙する。3つをすべて同じ数に入れると である。2つを同じ数に入れると である。3つを別々に入れると である。
したがって求める組は である。
(2)
に現れる素数は 個である。それぞれの素数 について, に含まれる の累乗部分を のどれか1つへ割り振る必要があり,またそのようにすれば条件(*)を満たす。
各素数の累乗部分について割り振り先は3通りであり, 個の素数について独立に選べる。したがって条件(*)かつ を満たす順序つきの組の個数は である。
(3)
(2)で数えた 通りは, の順序を区別している。ここから を満たす組の個数を求める。
条件(*)のもとで,もし2つの数が等しいなら,その2つは互いに素である同じ正整数である。したがってその共通の値は1でなければならない。 なので,3つすべてが等しいことはなく,2つが等しい場合は を並べ替えた場合だけである。
大小順にした組のうち, は順序つきでは の3通りに対応する。それ以外の大小順の組は3つの値がすべて異なるので,順序つきでは6通りに対応する。
求める個数を とする。すると,大小順の組のうち1個は であり,残り 個はそれぞれ6通りの順序つき組をもつ。よって である。これを解くと である。したがって求める個数は である。