1整数 1 二項係数の最大公約数、フェルマーの小定理の拡張 自然数 m

1整数
1 二項係数の最大公約数、フェルマーの小定理の拡張
自然数 m ≥ 2 に対し、m − 1 個の二項係数
m C1 , m C2 ,…, m Cm−1
を考え、これらすべての最大公約数を dm とする。すなわち dm はこれらすべてを
割り切る最大の自然数である。
(1)m が素数ならば、dm = m であることを示せ。
(2) すべての自然数 k に対し、k m − k が dm で割り切れることを、k に関する数学
的帰納法によって示せ。
(3)m が偶数のとき dm は 1 または 2 であることを示せ。
解法1 m は素数なので、m ≥ 2 である。1 ≦ i ≦ m − 1 を満たす任意の整数 i に
対して
m!
m Ci =
i!(m − i)!
i!(m − i)!m Ci = m!
この右辺は m で割り切れるので左辺も m で割り切れる。
m が素数であることと、1 ≦ i ≦ m − 1 および 1 ≦ m − i ≦ m − 1 から左辺の
i!, (m − i)! は素因数 m をもたない。
よって m Ci (これは自然数)が素因数 m を有することになるので
m Ci は m で割り切れる。
特に m C1 = m であるから m Ci (i ≦ i ≦ m − 1) の最大公約数 dm は m である。(証
明終)
(2)
(I) k=1 のとき、k m−k = 0 なので、k m−k は dm で割り切れる。
(II) ある自然数 k に対して、k m−k が dm で割り切れると仮定する。
二項定理から
m−1
∑
i
m
m
(k + 1) = k +
m Ci k + 1
i=1
よって
(k + 1) − (k + 1) = k
m
m−k
+
m−1
∑
m Ci k
i
i=1
ここで、m Ci (1 ≦ i ≦ m − 1) は dm で割り切れるので、
m−1
∑
は dm で割り切れる。
i=1
また、帰納法の仮定から k m−k は dm で割り切れる。
ゆえに、(k + 1)m − (k + 1) は dm で割り切れる。
(I),(II) から数学的帰納法により、任意の自然数 k に対して k m−k は dm で割り切れ
る。
1
(証明終)
(3) 一般に自然数 n に対して、n − (n − 1) = 1 であるから、n と n-1 の最大公約数
は 1 となり n と n-1 は互いに素である。
したがって、dm と dm − 1 は互いに素である。
また、(2) より、すべての自然数 k に対し、dm は k m − k = k(k m−1 − 1) を割り切
るので、
dm と k が互いに素のときには dm は k m−1 − 1 を割り切る。
よって,dm ≥ 2 のとき、k = dm − 1 とすると (dm − 1)m−1 − 1 が dm で割り切れる。
ここで、m は偶数なので m − 1 は奇数であり、二項定理により
m−1
∑
m−1
i
m−i−1
−1
(dm − 1)
−1=
m−1 Ci dm (−1)
=
m−1
∑
i=0
i
m−i−1
m−1 Ci dm (−1)
−2
i=1
= (dm の倍数) − 2
となる。
これが dm で割り切れることから、2 が dm で割り切れ、dm ≥ 2 より dm = 2 であ
る。
ゆえに、dm = 1 または 2 である。
(証明終)
解法2
(1) < m Ci と m−1 Ci−1 の関係を用いる解法>
1 ≦ i ≦ m − 1 である任意の整数 i に対し
m!
(m − 1)!
m
m
=
= m−1 Ci−1
m Ci =
i!(m − i)!
i (i − 1)!(m − i)!
i
im Ci = mm−1 Ci−1
m Ci , m−1 Ci−1
m Ci , m−1 Ci−1 は整数であるから、im Ci は m の倍数であるが、m が素数であること
と、1 ≦ i ≦ m − 1 から m と i は互いに素である。よって、m Ci は m で割り切れる。
以下解法1に同じ
2