東大数学 前期(2009)_(1)

＜①の問題＞
自然数 m ≧ 2 に対し、m-1 個の二項係数_mC₁, _mC₂ , ... , _mC_m-1 を考え、これらすべての最大公約数を d_m とする。
すなわち、d_m はこれらすべてを割り切る最大の自然数である。

(1) m が素数ならば、d_m = m であることを示せ。
(2) すべての自然数 k に対し、k^m - k が d_m で割り切ることを、k に関する数学的帰納法によって示せ。
(3) m が偶数のとき、d_m は 1 または 2 であることを示せ。


＜解答＞
(1)
_mC₁ = m だから、_mC_i(i = 1, 2, ... , m-1) が m の倍数になることを示せばよい。
_mC_i = m(m-1) ... (m-(i-1)) / i(i-1) ... 1 = m・(m-1) ... (m-(i-1))/ i(i-1) ... 1 = m・X
(X = (m-1) ... (m-(i-1))/ i(i-1) ... 1 とおく)
i ≦ m-1 より、m が素数ならば、m と i, i-1, ... , 1 は、互いに素だから、X が約分されて整数となり、m の倍数。

(2)
k = 1 のとき、k^m - k = 0 は d_m の倍数
k = n のとき成り立つと仮定すると、n^m - n は d_m の倍数 ・・・①
k = n + 1 のとき、
(n + 1)^m - (n + 1)
= _nC₀n⁰ + _nC₁n¹ + ... + _nC_tn^t + ... + _nC_m-1n^m-1 + _nC_mn^m - (n + 1)
ただし、t は(n + 1)^m を展開したときの t項目です。
= 1 + _nC₁n¹ + ... + _nC_tn^t + ... + _nC_m-1n^m-1 + n^m - (n + 1)
= _nC₁n¹ + ... + _nC_tn^t + ... + _nC_m-1n^m-1 + n^m - n ・・・②

_nC_t (1 ≦ t ≦ m-1) は、d_m の倍数で、これと①より、②は d_m の倍数だから、k = n + 1 のときも成り立つ。
よって、題意は示された。

(3)
(2) より k^m - k ≡ 0 (mod d_m) (k ＝ 0 でも成立)
だから、k = d_m - 1 として
(d_m - 1)^m - (d_m - 1) ≡ 0 (mod d_m)
∴ (-1)^m + 1 ≡ 0
m は偶数だから、 2 ≡ 0 となり、2 は d_m の倍数。
よって、d_m は 1 または 2。


＜解説＞
n! = n(n-1)...2・1 ただし、1! = 0! = 1 と定義する
_nC_r = n! / r!(n-r)!
を教科書で確認する。

(a + b)ⁿ = _nC₀ + _nC₁a^n-1b + ... + _nC_ra^n-rb^r + ... + _nC_n-1ab^n-1 + _nC_nbⁿ
を教科書で確認する。

互いに素は、最大公約数が 1 であること。

数学的帰納法の証明を教科書より確認する。

n ≡ r (mod d) の合同式とは、n ÷ d = X あまり r を意味する。
商 X は扱わなく、剰余（あまり）r を扱うときに、使う記号です。
本来は、大学の代数学で習う記号です。　大学受験より、教える予備校もあります。　たぶん、進学校では教えると思います。
プログラムの BASIC をすると、mod の命令を使います。


＜ポイント＞
₅C₃ = 5! / 3!(5-3)! = 5! / 3!2! = 5・4 / 2・1 = 5・2 = 10
のように、具体的な数字を扱う訳ではないということです。
変数を用いて、数学的な性質を取り扱っていること。

(1) _mC_i = m・X というに、_mC_i が、m の倍数であることの性質を見抜くこと。
m が素数であれば、m とm以外は、必ず互いに素であること。

(2) (n + 1)^m - (n + 1) = = _nC₁n¹ + ... + _nC_tn^t + ... + _nC_m-1n^m-1 + n^m - n と変形をすること。