インテジャーズ

インテジャーズ

数、特に整数に関する記事。

一年生の夢とLucasの合同式

一年生の夢(Freshman's dream)とは

(X+Y)^n = X^n+Y^n

のことを言います。中学生が展開を習ったときに

(X+Y)^2=X^2+2XY+Y^2

が正しいところを

(X+Y)^2 =X^2+Y^2

と間違えてしまうことはよく見かける光景だと思います。ちなみに二年生の夢(sophomore’s dream)もあるのですが、こちらは正しい式です:

\begin{align}\int_0^1\frac{1}{x^x}dx &= \sum_{n=1}^{\infty}\frac{1}{n^n} \\ \int_0^1x^xdx &= -\sum_{n=1}^{\infty}(-n)^{-n}\end{align}
mathtrain.jp

一年生の夢が成り立つ世界

最初の式ではどこで物事を考えるか明示していませんでしたが、標数p > 0の体係数多項式環では

(X+Y)^p = X^p+Y^p

が正しい式となります。理由は

integers.hatenablog.com

です(使うのはタイトルでリンク先に飛んでも違う話が書いてあります)。繰り返し適用すれば、任意の自然数kに対して

(X+Y)^{p^k} = X^{p^k}+Y^{p^k}

が成り立つこともわかります。

Lucasの合同式

1878年にLucasは二項係数に関する非常に美しい合同式を発表しています:

Lucasの合同式 pを素数とし、非負整数n, m \ (n \geq m)をそれぞれ、
\begin{align}n &= a_0+a_1p+\cdots +a_lp^i\\ m&= b_0+b_1p+\cdots + b_lp^l\end{align}
p進法表示する(0 \leq a_i, b_i \leq p-1)。このとき、二項係数に関する合同式
\displaystyle \binom{n}{m} \equiv \binom{a_0}{b_0}\binom{a_1}{b_1}\cdots \binom{a_l}{b_l} \pmod{p}
が成り立つ。

パスカルの三角形に現れない二項係数については\binom{0}{0}=1, \ \binom{a}{b}=0 \ (a < b)として扱います。この記事ではFineが1947に発表した証明を紹介します。この証明は二項定理と一年生の夢を用いた母関数表示による証明です。

証明. \mathbb{F}_p[X]において

\begin{align}\sum_{m=0}^n\binom{n}{m}X^m &= (1+X)^n= \prod_{i=0}^l(1+X)^{a_ip^i} = \prod_{i=0}^l(1+X^{p^i})^{a_i} \\ &= \prod_{i=0}^l\left( \sum_{b_i=0}^{a_i}\binom{a_i}{b_i}X^{b_ip^i} \right) \\ &= \prod_{i=0}^l\left( \sum_{b_i=0}^{p-1}\binom{a_i}{b_i}X^{b_ip^i} \right) \\ &= \sum_{b_0=0}^{p-1}\sum_{b_1=0}^{p-1}\cdots \sum_{b_l=0}^{p-1}\left(\prod_{i=0}^l\binom{a_i}{b_i}\right) X^{b_0+b_1p+\cdots +b_lp^l} \\ &= \sum_{m=0}^n \left( \prod_{i=0}^l\binom{a_i}{b_i} \right) X^m \end{align}

と変形できる。よって、係数比較をすれば定理が得られる。 Q.E.D.

Lucasの合同式と言えば次の合同式を指すことも多いです:

Lucasの合同式(其の二) a, b, c, dを自然数、pを素数とする。0 \leq a, c \leq p-1ならば、合同式
\displaystyle \binom{a+pb}{c+pd} \equiv \binom{a}{c}\binom{b}{d} \pmod{p}
が成り立つ。

証明. b, dp進展開してLucasの合同式を二回用いいればよい。 Q.E.D.