問題
自然数に対して，の相異なる素因数をすべてかけあわせたものをで表すことにする．たとえばである．ただしとする．
(1) ，を自然数，を，の最大公約数とするとき
となることを示せ．
(2) 2つの箱，のそれぞれに1番から10番までの番号札が1枚ずつ10枚入っている．箱，から1枚ずつ札を取り出す．箱から取り出した札の番号を，箱から取り出した札の番号をとするとき
を求めよ．
方針
(1) は各素数について、 のどれを割るかを比較する。 は指数を無視して「その素数が現れるか」だけを見る関数なので、素数ごとに左辺と右辺で現れる回数をそろえればよい。(2) は (1) により条件を 、 に移し、 から までの番号について最大公約数の型を表で数える。
解答
(1)
素数 を1つ固定する。 が を割るかどうか、 を割るかどうかで場合を分ける。 が のどちらも割らないとき、 は のいずれの にも現れない。 が のちょうど一方だけを割るとき、 は には現れず、 には現れる。したがって左辺 に は1回現れる。一方、右辺 にも は1回現れる。 が の両方を割るとき、 は にも にも現れるので、左辺には2回現れる。右辺でも と の両方に現れるので2回現れる。
以上より、すべての素数 について、左辺と右辺に現れる回数が一致する。したがって である。
(2)
(1) より である。ただし は の最大公約数である。
まず となるのは のとき、すなわち のときである。これは が互いに素であることを意味する。 のそれぞれについて、 で となる個数を数えると
である。合計は だから 次に となるのは のときである。これは、最大公約数 が2で割り切れ、しかも奇素数では割り切れないことを意味する。つまり は のように、素因数としては2だけをもつ。
同じように ごとに数えると
である。例えば なら、 は偶数で、かつ3を共有してはいけないので の4個である。
合計は だから