問題
整数の組に対して，次の条件(＊)を考える。
(＊) は1以上の整数であり，との最大公約数，との最大公約数，との最大公約数はそれぞれ1である。
以下の問いに答えよ。ただし，組とはのとき，かつこのときに限り等しい。
(1) 条件(＊)かつをみたす組のうちで，をみたすものをすべて求めよ。
(2) 条件(＊)かつをみたす組の個数を求めよ。
(3) を2以上の整数とし，以下の素数の個数をとする。条件(＊)かつをみたす組の個数をを用いて表せ。
方針
条件(＊)は，どの2つの数も共通の素因数を持たないという意味である。したがって，積 の素因数分解に現れる各素数の累乗部分は， のうちただ1つに丸ごと入らなければならない。 では3つの素数ブロック を3つの箱へ割り振る問題になる。(1)は大小順に並べた代表を列挙し，(2)(3)は各素数ブロックの割り振り先を独立に数える。
解答
(1)
まず である。条件(＊)より， のどの2つも共通の素因数を持たない。したがって，，， のそれぞれは， のうち1つだけに丸ごと入る。
つまり，3つの数 を， の3つの場所へ重複なく割り振ることを考えればよい。大小順 で並べた組を列挙する。
3つの因子をすべて同じ数に入れると である。2つを同じ数に入れ，残り1つを別の数に入れると である。3つをすべて別々に入れると である。
したがって求める組は である。
(2)
順序を区別して数える。，， のそれぞれについて，入れる先は の3通りである。各素数ブロックの割り振りは独立であり，そのように割り振れば必ず条件(＊)を満たす。したがって個数は である。
(3)
に現れる素数は，問題文より 個である。それらを とし， における の指数を とする。このとき である。
条件(＊)を満たすためには，各 を のうちただ1つに入れなければならない。逆に，各 を のどれか1つへ割り振れば，異なる2つの数が同じ素因数を共有することはないので，条件(＊)を満たす。
各素数について割り振り先は3通りで，素数ごとに独立だから，求める個数は である。