二項係数 C(3^n, a・3^m) の 3 進割り切り回数を求める方法

今回は、二項係数 C(3^n, a・3^m) が 3 で何回割り切れるかを求める問題について解説します。ここで a は 3 の倍数ではないとします。

1. 基本的な考え方

二項係数 C(N, K) が素数 p で何回割り切れるかは、ルカの定理や p 進展開を使うと便利です。3 進展開で考えると、各桁での繰り上がりにより指数が決まります。

N = 3^n を 3 進数で書くと、1 の後に n 個の 0 が並ぶ形です。K = a・3^m は a が 3 の倍数でないので、3 進展開では m 桁目から始まる数になります。

ルカの定理によれば、C(N,K) mod 3 を考えると、各桁ごとの組み合わせの積により割り切れ具合を把握できます。

例えば、n = 5, m = 2, a = 1 の場合。

3 進展開にすると。

桁ごとに組み合わせを考え、繰り上がりの影響を確認すると、3 で割れる回数が n – m = 3 回となることがわかります。

以上の考え方から、一般的に a が 3 の倍数でない場合、C(3^n, a・3^m) が 3 で割れる指数は

n – m

となります。

・二項係数 C(3^n, a・3^m) の 3 で割れる回数は、a が 3 の倍数でないとき n – m で求められる。
・3 進展開を用いると、ルカの定理から簡単に確認可能。
・具体例として n = 5, m = 2, a = 1 の場合、3^5C1·3^2 は 3^3 で割れる。