整数の組 に対して，次の条件(＊)を考える。
(＊) ，， は 以上の整数であり， と の最大公約数， と の最大公約数， と の最大公約数はそれぞれ である。
以下の問いに答えよ。ただし，組 と は ，， のとき，かつこのときに限り等しい。
(1) 条件(＊)かつ をみたす組 のうちで， をみたすものをすべて求めよ。
(2) を 以上の整数とし， 以下の素数の個数を とする。条件(＊)かつ をみたす組 の個数を を用いて表せ。
(3) を 以上の整数とし， 以下の素数の個数を とする。条件(＊)かつ をみたす組 のうちで， をみたすものの個数を を用いて表せ。
、、 のどの つも最大公約数が だから、 つの素数 で割り切れるのは つのうち多くても つです。 を素因数分解したときの の累乗は、、、 のうち つにまるごと含まれる。
なので、、、 の つを 、、 に割り当てます。何も割り当てられなかった数は になる。
に並べると、 つを か所にまとめた 、 つと つに分けた 、、、ばらばらにした の 組です。
は から までの積だから、素因数は 以下の素数 個で、それ以外にはありません。 を と素因数分解する。
(1) と同じく、 から までのそれぞれを 、、 のどれか つに割り当てると組が つ決まり、割り当て方が違えば組も違う。割り当ては つにつき 通りで、組の個数は です。
図は の例で、 の つの累乗の行き先を、 通り全部について順に切りかえている。
なら と の最大公約数は 自身で、それが だから です。 つが等しい組は を つ含む組に限られ、 から つとも等しいことはない。
個の組のうち、 を並べかえた 個は、 にすると 組になります。残りの 個は つの数がすべて異なり、並べかえた 個ずつが 組にまとまる。
求める個数は です。 では で、(1) の で数えた 組と一致する。