遊びの数論62　

他のメモへのリンク集。リンク集を飛ばして、このページの前書きへ。本文の目次へ。21、22などの数字は、メモの番号です。

---

『遊びの数論61』の続き。誤字脱字・間違いがあるかも。

---

• 目次。約2の項目があります。2026などの数字は、メモの日付です。
• 2026-06-18　博士の愛した公式（その2）
• 2026-06-20　「二項係数」を斬る！　余りの下克上
• 2026-06-23　ウィルソンの定理の証明（ラグランジュ）の応用　逆三角の倍数列島
• 目次の終わり。このページの最初の項目が続きます。

---

2026-06-18　博士の愛した公式（その2）

Glaisher の「四乗剰余」の公式のうち、 S_k(N) の N が偶数（N + 1 が奇数）の場合に関するものは、スターリング数を使うと、こう要約できる。いわく p が奇素数なら、 0 以上の任意の（ただし (p − 3)/2 を除く）整数 q に対して、次が成り立つ。
　　[p S 2q] ≡ pq⋅[p S 2q + 1] (mod p⁴)

前回は N が偶数の場合について記した。今回は N が奇数（N + 1 が偶数）の場合について、入り口の部分を記す。

N = 2h − 1 が奇数の場合の S_k(N) の σ 表現を引用する。 k = 2t が偶数のケース（§11）と k = 2t + 1 が奇数のケース（§12）。いずれも、
　　σ_j = σ_j(h − 1; 2h), L = 2h (= N + 1), μ = h − t
とする。

S_2t(2h − 1) = σ_t + [μ²/2!]⋅L²⋅σ_t−1 + [(μ + 1)μ²(μ − 1)/4!]⋅L⁴⋅σ_t−2 + [(μ + 2)(μ + 1)μ²(μ − 1)(μ − 2)/6!]⋅L⁶⋅σ_t−3 + ···

S_2t+1(2h − 1) = (μ − 1/2){Lσ_t + [μ(μ − 1)/3!]⋅L³⋅σ_t−1 + [(μ + 1)μ(μ − 1)(μ − 2)/5!]⋅L⁵⋅σ_t−2 + ···}

第1式の (μ − 1/2)⋅L 倍
　　(μ − 1/2){Lσ_t + [μ⋅3μ/3!]⋅L³⋅σ_t−1 + [(μ + 1)μ(μ − 1)⋅5μ/5!]⋅L⁵⋅σ_t−2 + [(μ + 2)(μ + 1)μ(μ − 1)(μ − 2)⋅7μ/7!]⋅L⁷⋅σ_t−3 + ···}
から第2式を引くと:
　　(μ − 1/2)⋅L⋅S_2t(2h − 1) − S_2t+1(2h − 1)
　　 = (μ − 1/2){[μ⋅[3μ − (μ − 1)]/3!]⋅L³⋅σ_t−1 + [(μ + 1)μ(μ − 1)⋅[5μ − (μ − 2)]/5!]⋅L⁵⋅σ_t−2 + [(μ + 2)(μ + 1)μ(μ − 1)(μ − 2)⋅[7μ − (μ − 3)]/7!]⋅L⁷⋅σ_t−3 + ···}
　　 = 1/2(2μ − 1){[μ⋅[2μ + 1]/3!]⋅L³⋅σ_t−1 + [(μ + 1)μ(μ − 1)⋅[(2μ + 1)⋅2]/5!]⋅L⁵⋅σ_t−2 + [(μ + 2)(μ + 1)μ(μ − 1)(μ − 2)⋅[(2μ + 1)⋅3]/7!]⋅L⁷⋅σ_t−3 + ···}
　　 = 1/2(4μ² − 1){[μ⋅1/3!]⋅L³⋅σ_t−1 + [(μ + 1)μ(μ − 1)⋅2/5!]⋅L⁵⋅σ_t−2 + [(μ + 2)(μ + 1)μ(μ − 1)(μ − 2)⋅3/7!]⋅L⁷⋅σ_t−3 + ···}

従って (h − t − 1/2)⋅L⋅S_2t(2h − 1) と S_2t+1(2h − 1) は、もし仮に { } 内の値が因子 2 を十分多く持つなら法 L³ で合同であり、その場合、もし σ_t−1(h − 1; 2h) も L の倍数なら、法 L⁴ でも合同になるかもしれない。

しかし L = 2h は偶数であり { } 内の分母によって素因子 2 が一つ以上約されるので、 { } 内の和に、 L³ 等で割り切れるのに十分なだけの素因子 2 が残るかどうか分からないし、この { } 内全体に係数 1/2 が掛かっているので、素因子 2 の数はさらに一つ減る。従って、一般的に言うならば、上述の合同式の法は―― L³ ないし L⁴ ではなく―― h³ ないし h⁴ となる（以前、別の文脈でも同様の状況が起きた）。

L が素因子 3 を持つとしても、それが分母の 3 と約されて消えることはない。なぜなら因子 μ, 2μ + 1, 2μ − 1 のどれかは 3 の倍数で、約分に必要な 3 はそこから供給される。 { } 内の第2項以降は、十分多くの因子 L を持ち、 L の各素因子 δ (≠ 2) に関しては、 L³ が持つ素因子 δ と同じ個数以上が残る。

要するに N (= 2h − 1) が奇数で k (= 2t) が偶数の場合、 h³ を法として（一定の条件が満たされるときは h⁴ を法として）:
　　[(N + 1)/2 − k/2 − 1/2](N + 1)⋅S_k(N) ≡ S_k+1(N)　つまり
　　(N − k)(N + 1)/2⋅S_k(N) ≡ S_k+1(N)

この最後の合同式で N = L − 1, k = r − 1 と置くと、下記〘ⅲ〙を得る。ただし、任意の正整数 N について S₀(N) = 1 とし、 j > N のときは S_j(N) = 0 とする。

S_k(L − 1) に関する法が3乗数・4乗数の合同式（Glaisher [7], §59, X）
r を（L 以下の）正の奇数とする。 L が正の奇数なら:
　〘ⅰ〙　[L(L − r)/2]⋅S_r−1(L − 1) ≡ S_r(L − 1) (mod L³)
　〘ⅱ〙　特に L が素数かつ r ≠ 3 なら、上記の合同式は mod L⁴ でも成り立つ。
L = 2h が正の偶数なら:
　〘ⅲ〙　[L(L − r)/2]⋅S_r−1(L − 1) ≡ S_r(L − 1) (mod h³)
　〘ⅳ〙　上記の合同式は、しばしば mod h⁴ でも成り立つ。

r = 1 の場合、または L が奇数で r ≥ L の場合、または L が偶数で r ≥ L + 1 の場合、命題は自明。それ以外の場合について、〘ⅰ〙〘ⅱ〙は既知の命題において L = N + 1 かつ r = α + 1 と置いただけ。

Glaisher は〘ⅱ〙と似た形式で〘ⅳ〙の十分条件を記した。その導出は比較的複雑。今はその問題には立ち入らない。

公式 S_k(n − 1) = [n S n − k] を使って、上記の合同式を「スターリング数を使った表記」に変換すると、
　　(L(L − r)/2)⋅[L S L − r + 1] ≡ [L S L − r]
となる。 L と L − r をあらためてそれぞれ n と k と置くなら:

法が3乗数・4乗数の合同式（スターリング数について）
　　[n S k] ≡ (nk/2)⋅[n S k + 1]
この合同式は、 n が正の奇数の場合、任意の偶数 k = 0, 2, 4, ··· に対して mod n³ で有効（n が奇素数かつ k ≠ n − 3 なら mod n⁴ でも有効）。一方、 n = 2h が正の偶数の場合、任意の奇数 k = 1, 3, 5, ··· に対して mod h³ で有効（しばしば mod h⁴ でも有効）。

---

2026-06-20　「二項係数」を斬る！　余りの下克上

げこくじょう【下克上・下剋上】　下の立場の者が上の立場の者をしのぎ、勢力を振るうこと。

15人の選手がいるバスケチームから、5人のスターターを選ぶ方法は 3003 通りもある:
　　(15 C 5) = (15⋅14⋅13⋅12⋅11)/(1⋅2⋅3⋅4⋅5)
　　 = (14⋅13⋅12⋅11)/(1⋅2⋅4) = 7⋅13⋅3⋅11 = 3003
これには優秀なコーチも悩むかも？　どの選手を起用するかもそうだが、この計算は、あまり簡単ではない。

やぶから棒だけど、この (15 C 5) の上の数 15 と下の数 5 をそれぞれ p = 7 で割ると、 15 ÷ 7 の余りは 1。 5 ÷ 7 の余りは 5。「下の余り」の方が大きい。ところで 3003 は p = 7 で割り切れる。

同じ 15 と 5 をそれぞれ p = 13 で割ると、「上の余り」は 2 で「下の余り」は 5。やはり下が大きい。ところで 3003 は p = 13 でも割り切れる！

一般に y = (n C k) の上の数 n と下の数 k をそれぞれ p で割ったとき、もし「下の余り」が「上の余り」を超えるなら（余りの下克上）、 y は p で割り切れる。ここで p は、任意の素数（1 と自分自身でしか割り切れない 2 以上の数）。 p = 2, 3, 5, 7, 11, 13 など。

この豆知識について略述。「下剋上」の概念を使って、とある美しい定理を証明したい。

§1　7 × 13 = 91 は、「素数と間違えられる数」として知られる（70 を引いてみれば、残りは 21 = 3⋅7 で、 7 の倍数であることは明白だが）。特徴的な積 7 × 11 × 13 = 1001 は、 7⋅13 × 11 = 91 × 11 = 910 + 91 と考えれば納得がいく。上の数（上側インデックス）が 14 ～ 16 の二項係数は、しばしば 1001 の倍数。

(15 C 5) = (15⋅14⋅13⋅12⋅11)/(1⋅2⋅3⋅4⋅5)　　ア
　　 = (14⋅13⋅12⋅11)/(1⋅2⋅4)　　← 15 ∕ 3⋅5 を約分
　　 = 7⋅13⋅3⋅11　　← 14 ∕ 2 と 12 ∕ 4 を約分
　　 = 3 × (7⋅13⋅11) = 3 × 1001 = 3003

(n C k) は「n 個の物から k 個の物を選ぶ組み合わせの数」なので整数だが、上記アのような分数の形で表現されることが多い。その分子は、 n から始まってだんだん小さくなる整数 k 個の積。
　　n(n − 1)(n − 2)···(n − k + 1)　　イ
そして分母は k! つまり「1 から k までの各整数の積」。

同じことだが、次のように通分して表記されることもある。分子イに
　　(n − k)(n − k − 1)(n − k − 2)··· 3⋅2⋅1　つまり　(n − k)!
を掛ければ、分子は全体として n! に。分母にも同じ (n − k)! を掛ければ、分数の値は変わらない。
　　(n C k) = n!/[k! (n − k)!]　　ウ

別表現ウを「15人のバスケチームから5人を選ぶ」例に適用すると:
　　(15 C 5) = 15!/[5! (15 − 5)!] = 15!/(5! × 10!)
　　 = 15⋅14⋅13⋅12⋅11⋅10⋅9···3⋅2⋅1/[(5⋅4⋅3⋅2⋅1)(10⋅9···3⋅2⋅1)]
分子の 10⋅9···3⋅2⋅1 を分母の (10⋅9···3⋅2⋅1) と約分すれば、アと同じこと。

§2　「余りの下克上」によって、二項係数 (n C k) が p で割り切れる仕組み。一般論の前に、具体的な数値例を。

「下克上」が起きない場合から観察した方が、見通しがいい。例えば (19 C 12) = 50388 の上と下をそれぞれ p = 5 で割ると、上の余りは 4、下の余りは 2。下克上は起きず、もちろん 50388 は p = 5 で割り切れない。ウのように、
　　(19 C 12) = 19!/[12! (19 − 12)!]　　エ
と見るなら、この 18564 という数は、「分子が 19! で、分母が 12! × 6! の分数」に等しい。

エの分子 19! は、因子 5 をいくつ持つか？
　　19! = 1⋅2⋅3⋅4⋅5　　カ
　　 × 6⋅7⋅8⋅9⋅10　　キ
　　 × 11⋅12⋅13⋅14⋅15　　ク
　　 × 16⋅17⋅18⋅19　　ケ
の構成要素のうち、 5 の倍数はカ・キ・クの右端の 5 と 10 と 15 だけ（ケも、あと一つ長ければ、 5 の倍数 20 を含んでいたところだが、そこまでいかず 19 で打ち切り）。よって「5 で何回割れるか？」だけを問題にするなら、
　　5 × 10 × 15 = (1⋅5)(2⋅5)(3⋅5) = 1⋅2⋅3 × 5³ = 3!⋅5³
を考えればいい。

このうち 3! の部分には因子 5 はないけど、もっと大きな数、例えば 33! を扱うなら、対応する同様の数は、
　　5 × 10 × 15 × 20 × 25 × 30 = 1⋅2⋅3⋅4⋅5⋅6 × 5⁶ = 6!⋅5⁶
となり 6! の部分にも因子 5 が入り込む。一般に n を p で割った商が a のとき（余りを無視）、 n が持つ因子 p の総数は、 a!⋅p^a が持つ因子 p の総数に等しい。

同様に考えると、「因子 5 を何個持つか？」という観点では、エの分母のうち:
　　12!　は　2!⋅5²　は同等（12 ÷ 5 の商は 2）
　　(19 − 12)!　つまり　7!　は　1!⋅5¹ と同等（7 ÷ 5 の商は 1）
後者は要するに 5 だが、統一的に a!⋅p^a スタイルで表記した。これらの情報を総合すると、分数エは
　　(3!⋅5³)/(2!⋅5² × 1!⋅5¹)
と同等（「因子 5 を何個持つか？」に関して）であり、分子・分母にそれぞれ三つだけ因子 5 がある。よって、因子 5 は約分により全部消滅し、結果の整数は 5 の倍数ではない。

ここで重要なのは (19 − 12)! の部分の挙動。 p = 5 と置き、 p で割った商と余りを考えると、
　　19 = 3p + 4　そして　12 = 2p + 2
　　∴　19 − 12 = (3p + 4) − (2p + 2) = (3p − 2p) + (4 − 2)
という関係だ。 3p + 4 の後ろの 4 と、 12 = 2p + 2 の後ろの 2 は、それぞれ (19 C 12) の上と下を p で割ったときの余りに他ならない。この「下の余り」の 2 が「上の余り」の 4 を超えないからこそ、
　　(3p − 2p) + (4 − 2) = (3p − 2p) + w
の w の部分が 0 以上になる。

しかし 5 で割った余りは {0, 1, 2, 3, 4} のどれかなので、 p = 5 の場合、
　　「上の余り」と「下の余り」の差（それを w とする）
は最大で 4 − 0 = 4、最小で 0 − 4 = −4。場合によっては、負になる。 w が負になるケースとは、すなわち「下の余り」が「上の余り」を超えるケース、つまり「余りの下克上」だ！

〔注意〕　「下の余り」が「上の余り」に等しい場合（w = 0）は、下剋上に含まれない。下剋上が成立するためには、「下の余り」が「上の余り」を超える必要がある（w < 0）。

もし w が負の数、例えば −1 だとすると、 (3p − 2p) + w = (1⋅p) + (−1) = 0⋅p + 4 のように（p = 5 の例）、「分母が持つ因子 p の個数」が一つ少なくなる（w が 0 以上の場合と比べて）。その結果、約分の後でも分子には因子 p が残り、結果は p で割り切れる、と。

まぁ、一応そんな感じ。

§3　下剋上が起きる場合・起きない場合と、その違いがもたらす影響について、もうちょいきちんと。

補助命題1　D を任意の正の整数、 p を素数とする。 D を p で割ったとき商が E で余りが F だとしよう:
　　D = Ep + F　　ここで F は 0 以上 p 未満
このとき D! が含む因子 p の個数は、
　　E!⋅p^E
が含む因子 p の個数と一致する。

証明　積 D! = 1⋅2⋅3···D を構成するちょうど D 個の整数たちを、次のように「原則として 1 行につき p 個の数」があるように、 p 個ずつ区切って考える。

【表1】　D! = (Ep + F)! の D 個の因子たちを p 個ずつ並べる

p 個 の 数 × E 行	1	2	3	···			p
	p + 1	p + 2	p + 3	···			2p
	2p + 1	2p + 2	2p + 3	···			3p
	︙	︙	︙	︙			︙
	(E − 1)p + 1	(E − 1)p + 2	(a − 1)p + 3	···			Ep
	Ep + 1	Ep + 2	Ep + 3	···	Ep + F (= D)		↑p の 倍数
	F 個だけの数 × 1 行

もし D が p で割り切れないなら（つまり余り F ≠ 0 なら）、最後に「F 個だけの因子から成る短い行」が一つできる。もし D が p 未満なら（つまり商 E = 0 なら）、そのような「短い行」しかできないが、それでもいい。 1 から D までの数のうち、因子 p を含むものは、
　　p, 2p, 3p, ···, Ep
の E 個だけ（もし E = 0 なら 0 個）。よって D! が含む因子 p の総数は、次の積が含む因子 p の総数と一致する。
　　p × 2p × 3p × ··· × Ep = (1⋅2⋅3···E)⋅p^E = E!⋅p^E

E > 0 なら、上記の関係は明白。一方、もし E = 0 なら D! が含む因子 p は 0 個だが、その場合も同じ等式は有効。実際、そのとき E!⋅p^Eは 0! = 1 と p⁰ = 1 の積に（つまり 1 に）等しいが、この 1 という数は、因子 p をちょうど 0 個含む。∎

§4　今 n, k を正の整数とする。二項係数の性質（定義）から、もし n = k なら (n C k) = 1、もし n < k なら (n C k) = 0 だが、 1 ないし 0 については「p の倍数か否か？」は考えるまでもない。そこで、以降 n > k と仮定しよう――その場合、 n − k も正の整数。

(n C k) の n を p で割ったときの商を a、 余りを u とする。 k を p で割ったときの商を b、 余りを v とする。
　　n = ap + u　　ここで u は 0 以上 p 未満
　　k = bp + v　　ここで v は 0 以上 p 未満
このとき:
　　n − k = (a − b)p + (u − v)
表記簡潔化のため c = a − b, w = u − v と置くと:
　　n − k = cp + w　　ここで w は −p < w < p の範囲の整数

仮定により商 a, b, c (= a − b) はいずれも 0 以上。

「因子 p の個数」だけを問題にするなら、補助命題1により n! は a!⋅p^a と同等で、 k! は b!⋅p^b と同等。同様に、もし仮に w = u − v が 0 以上なら、同じ補助命題により (n − k)! は c!⋅p^c と同等。その場合、
　　(n C k) = n!/[k! (n − k)!]
は、
　　(a!⋅p^a)/(b!⋅p^b × c!⋅p^c)
と同等であり、 a! と b! と c! をひとまず無視するなら、分子にも分母にも因子 p が a 個ずつある（分母のうち p^b は b 個の p を含み、 p^c = p^a−b は a − b 個の p を含む。それらの合計は a 個）。ゆえにこのケースでは、一般には、約分によって分子・分母の因子 p は全部消滅し、結果は p の倍数にならない（例外として、もし「a! が含む因子 p の個数」が「b! と c! が含む因子 p の個数の合計」を上回るなら、約分後にも因子 p が残り、結果は p の倍数）。

w = u − v が 0 以上ということは、「下の余り」 v が「上の余り」 u を超えない、ということ。下克上が起きない、ということ。

他方において、もし仮に下剋上が起きて w = u − v が負なら、もはや (n − k)! は c!⋅p^c と同等にならず、 (c − 1)!⋅p^c−1 と同等になる。

なぜなら w が負なら n − k = cp + w は cp より少し小さいから、それを p で割ると、商は c より少し小さい（正確には c − 1 に等しい）。よって、その場合 (n − k)! の積を構成する整数たち 1, 2, 3, ···, n − k を 1 行につき p 個ずつ並べると、「p 個の数から成る行」が c − 1 個だけでき、 c 行目には p 個未満の数しかない。 1 から n − k までの整数のうち p の倍数は p 個ごとに最後の 1 個だから、「p 個の数から成る各行」の末端のものだけが p の倍数。つまり、その範囲の p の倍数を列挙すると:
　　p, 2p, 3p, ···, (c − 1)p
これら c − 1 個の「p の倍数」の積は (c − 1)!⋅p^c−1 に等しい。

要するに w が負の場合（＝下剋上が起きた場合）、もし a! と b! と c! の影響を無視するなら、「分母が含む因子 p の個数」は「分子が含む因子 p の個数」より 1 小さいので、約分後にも因子 p が残り、結果は p の倍数。 a! と b! と c! の影響も考慮するなら、約分後に残る p の個数はさらに増える可能性があるが、減る可能性はない（※補足1）。従って「下剋上 ⇒ 約分後の数は因子 p を含み p の倍数」は常に成り立つ（逆は必ずしも真ではない）。

※補足1　下記の分数の分子が（または分子と分母の両方が）因子 p を含むなら、約分後も因子 p が残る。
　　a!/(b! × c!)　すなわち　a!/[b! (a − b)!]

実際、分母 b! (a − b)! が因子 p を含むなら、分子 a! も因子 p を同じ個数以上含む。もしもそうでなかったら（つまり、もしも分母が含む因子 p の個数の方が多かったなら）、約分後の分数は 1/p などの非整数になってしまうが、それは不合理。なぜならこの分数は、二項係数
　　(a C b) = a!/[b! × (a − b)!]
であり、 a 個の物から b 個の物を選ぶ組み合わせの数。当然、整数でなければならない。

より直接的に、例えば a = 7 と b = 3 と c = a − b = 7 − 3 = 4 の場合を考えてみる。
　　a! = 1⋅2⋅3⋅4⋅5⋅6⋅7
　　b! = 1⋅2⋅3　そして　c! = 1⋅2⋅3⋅4
であるから、 a!/(b! × c!) が整数であることを言うには、 b! の内容を約分した後の (4⋅5⋅6⋅7)/(1⋅2⋅3⋅4) が整数であることを言えばいい。そのためには、 4, 5, 6, 7 を適当に並び替えると、順に「1 の倍数」「2 の倍数」「3 の倍数」「4 の倍数」になることを、示せばいい。それは易しい。連続する 4 整数の中に、必ず「4 の倍数」が一つ含まれること、「3 の倍数」が一つ以上含まれること、等々は（それら各数を 4 で割った余り、 3 で割った余り、等々を考えれば）明白。 a = 7 の例に限らず、一般の場合も同様。

§5　実用上 a! と b! と c! が何の影響も持たないケースを扱うことも多いと思われる。すなわち:

n < p² の場合、「下克上」が起きるか否かだけによって、二項係数が p で割り切れるか否かを完全に判定できる。

証明　n < p² なら n を p で割った商 a は p 未満なので、 a! = 1⋅2⋅3···a は因子 p を含まない。このとき b! も c! も因子 p を含まない（仮定により b も c = a − b も a 以下だから）。よって a! と b! と c! は因子 p の個数に何の影響も与えず、「下剋上」が起きるか起きないかによって、結果が決まる。∎

n < p² の条件があってもなくても、「下剋上が起きれば p で割り切れる」という部分は変わらない。

二項係数 y が p で割り切れるためには、 y を表す分数の分子が含む因子 p の個数が、分母が含む因子 p の個数より、一つでも多ければいい。下剋上は、この一つの差を可能にしてくれる（分母側の因子数を一つ少なくすることによって）。他方において、もし n が p² 以上で、かつ k も n − k も p² 未満なら、もともと分子が含む因子 p の個数の方が多いので、下剋上が起きても起きなくても y は p で割り切れる。

〔例〕　y = (11 C 4) = (11⋅10⋅9⋅8)/(1⋅2⋅3⋅4) = 11⋅5⋅3⋅2 = (11⋅3)(5⋅2) = 330 について。
㋐　p = 11 の場合。 4 ÷ 11 による「下の余り」 4 は、 11 ÷ 11 による「上の余り」 0 を超える。下克上が起き、 y は p で割り切れる。
㋑　p = 7 の場合。 4 ÷ 7 による「下の余り」 4 は、 11 ÷ 7 による「上の余り」 4 を超えない（注: 等しい場合は「下剋上」にならない）。下克上は起きず、 y は p で割り切れない。
㋒　p = 5 の場合。 4 ÷ 5 による「下の余り」 4 は、 11 ÷ 5 による「上の余り」 1 を超える。下克上が起き、 y は p で割り切れる。
㋓　p = 3 の場合。 4 ÷ 3 による「下の余り」 1 は、 11 ÷ 3 による「上の余り」 2 を超えない。下克上は起きていないが、 y は p で割り切れる。 n = 11 は p² = 9 以上なので。
㋔　p = 2 の場合。 4 ÷ 2 による「下の余り」 0 は、 2 ÷ 3 による「上の余り」 1 を超えない。下克上は起きていないが、 y は p で割り切れる。 n = 11 は p² = 4 以上なので。

§6　関連する話題として、 Glaisher による美しい定理を紹介したい。いわく n と k を p で割ったとき、それぞれ商が a, b で余りが u, v ならば、二つの整数
　　(n C k)　と　(a C b) × (u C v)
は、法 p の下で合同（つまり p で割った余りが等しい）。

次の補題を使う。

補助命題2（Glaisher [8], §3）　D を任意の正整数、 p を素数とする。
　　D = Ep + F, 0 ≦ F < p
のとき、下記の合同式が成り立つ:
　　D!/p^E ≡ (−1)^E⋅E!⋅F! (mod p)

証明　D! は、次の三つの因子の積に等しい。
　　Q₁ = 「法 p の下で 1, 2, ···, p − 1 に合同な数たち」の積 × E 組
　　Q₂ = p⋅2p⋅3p···Ep
　　Q₃ = 「法 p の下で 1, 2, ··· , F に合同な数たち」の積 × 1 組

【表2】　D! の D = Ep + F 個の因子たち（表1も参照）

	Q1						Q2
p 個 の 数 × E 行	1	2	···			p − 1	p
	p + 1	p + 2	···			2p − 1	2p
	2p + 1	2p + 2	···			3p − 1	3p
	︙	︙	︙			︙	︙
	(E − 1)p + 1	(E − 1)p + 2	···			Ep − 1	Ep
Q3	Ep + 1	Ep + 2	···	Ep + F (= D)

Q₁ の各組の数は p を法として ≡ −1 なので（Wilson の定理）、
　　Q₁ ≡ (−1)^E (mod p)
であり、また Q₃ ≡ F! (mod p) である。よって D! = Q₁⋅Q₂⋅Q₃ を Q₂ = E!⋅p^E で割った整数について、
　　D!/(E!⋅p^E) = Q₁⋅Q₃ ≡ (−1)^E × F! (mod p)
が成り立つ。両辺を E! 倍して、
　　D!/p^E ≡ (−1)^E⋅E!⋅F! (mod p)
を得る。∎

y = (n C k) に関連して、
　　n = ap + u (0 ≦ u < p)
　　k = bp + v (0 ≦ v < p)
　　n − k = cp + w (−p < v < p)
と置くとき（ただし c = a − b, w = u − v）、「因子 p の個数」だけを問題にする限りにおいて、 y は
　　(a!⋅p^a)/(b!⋅p^b × c!⋅p^c)　　（✽）
と同等（§4）。この同等性は、補助命題2にいう Q₂ の部分だけを考慮したもの（Q₁ と Q₃ は因子 p を含まないので、それらを無視した。補助命題1参照）。

今、因子 p の個数を考える代わりに、三つの整数 n! と k! と (n − k)! の値について mod p で考えたい。そのためには Q₁ と Q₃ も計算に含める必要がある。補助命題2において D に n ないし k ないし n − k を代入することに当たる。

例えば D = n = ap + u に関して、もし（✽）の分子を n! で割った上で、 Q₁ に当たる (−1)^a と Q₃ に当たる u! をそこに因子として追加すれば、新しい分子は、整数 n!/p^a と一致し、補助命題2が示すように、その整数について、次の合同式が成り立つ:
　　n!/p^a ≡ (−1)^a⋅a!⋅u! (mod p)

議論の便宜上、 w は負でない（下剋上が起きていない）と仮定する。その場合、 a! と b! と c! を無視するなら、（✽）の分子にも分母にも因子 p が a 個ずつある（§4）。言い換えると、 p^a = p^b × p^c であり、（✽）において、これらの因子は約分によりきれいに消滅する。

ゆえに、「分子を n! で割った上で」…という上記の処理は、単に（✽）から p^a, p^b, p^c を削除（約分）することによって、正当に実行可能。結局 n! に関して補助命題2の合同式・右辺の形式を得るためには、（✽）の分子から因子 p^a を除去し、代わりに因子 (−1)^a⋅u! を追加すればいい。

D = n に関してだけでなく、 D = k に関して、および D = n − k に関しても、それぞれ同様に扱うことによって、（✽）から次の合同式の右辺を得る:
　　n!/[k! (n − k)!] ≡ [a!⋅(−1)^a⋅u!]/[b!⋅(−1)^b⋅v! × c!⋅(−1)^c⋅w!] (mod p)
仮定により w は負でないので、分母の因子 w! は普通の階乗。

この左辺は、 Q₁ と Q₃ も計算に含めたものであり、 Q₂ だけを考慮した（✽）とは（一般には）異なる整数値を持つ。右辺はそれを mod p で簡約したもの。部分的に（✽）を利用して導出したけど、内容は（✽）と直接関係ない。

この合同式の右辺において、 (−1)^a と (−1)^b と (−1)^c は、全体としては無いのと同じ（c = a − b なので）。従って:
　　n!/[k! (n − k)!] ≡ (a! × u!)/[b!⋅c! × v!⋅w!] ≡ a!/[b! (a − b)!] × u!/[v! (u − v)!]

この合同式と、二項係数の定義（§1・ウ）から、下記の優美な定理を得る。

定理1（Lucas [9], §3; cf. Glaisher [8], §6）　正の整数 n, k を素数 p で割ったとき、商が a, b で余りが u, v なら:
　　(n C k) ≡ (a C b)⋅(u C v) (mod p)

何ともきれいで心に残る。形式的に、二項係数は「商ベクトル」と「余りベクトル」の内積（？）に等しい！

証明　「下克上」が起きない場合については、上述の通り。「下克上」が起きる場合、 (n C k) が p で割り切れるので、合同式の左辺は ≡ 0。かつ、下剋上の定義によって「下の余り」は「上の余り」を超えるので、 (u C v) は自明に = 0、ゆえに合同式の右辺も ≡ 0。∎

〔例1〕　(23 C 11) = 1352078 ≡ 3 (mod 5) について。 23 と 11 を 5 で割ると、商は 4 と 2、余りは 3 と 1。そして:
　　(4 C 2)⋅(3 C 1) = 6⋅3 = 18 ≡ 3 (mod 5)

〔例2〕　同じ (23 C 11) = 1352078 = 193154⋅7 ≡ 0 (mod 7) について。 23 と 11 を 7 で割ると、商は 3 と 1、余りは 2 と 4。そして:
　　(3 C 1)⋅(2 C 4) = 3⋅0 = 0 ≡ 0 (mod 7)

「下剋上」が起きて p で割り切れることは、定理1では、 (2 C 4) = 0 のような自明な二項係数に対応する。定理1はさらに、下剋上が起きずに p で割り切れない場合についても、追加情報を与えてくれる――「割り切れないのなら、余りは何？」という情報を。

定理1を最初に発見したのは Lucas [9] だという^†。定理1は Concrete Mathematics, 5.61 にも収録され、 Knuth も Lucas [9] を出典としている。 Glaisher [8] は、同じことを独立に再発見したらしい。 Glaisher の証明は素朴で平明。本文の議論はそれに基づく。「下克上」という表現は説明の便宜上のもので、もちろん Lucas や Glaisher がそのような用語を使ったわけではない。

† https://oeis.org/A348884
(Number of pairs of base-p digits for which binomial coefficients support a Lucas congruence modulo p^2, where p is the n-th prime)

References:
[8] J. W. L. Glaisher, “On the residue of a binomial-theorem coefficient with respect to prime modulus.”, The Quarterly Journal of Pure and Applied Mathematics 30 (1899), 150–156
https://gdz.sub.uni-goettingen.de/download/pdf/PPN600494829_0030/LOG_0010.pdf
https://gdz.sub.uni-goettingen.de/id/PPN600494829_0030?tify=%7B%22pages%22%3A%5B154%5D%2C%22view%22%3A%22%22%7D
［変数名 q と g の誤植に注意］
Cf. Glaisher, “On the reside with respect to pⁿ⁺¹ of a binomial-theorem coefficient divisible by p”, Quarterly Journal, 30 (1899), 349–360
https://gdz.sub.uni-goettingen.de/download/pdf/PPN600494829_0030/LOG_0019.pdf
https://gdz.sub.uni-goettingen.de/id/PPN600494829_0030?tify=%7B%22pages%22%3A%5B353%5D%2C%22view%22%3A%22%22%7D
[9] Édouard Lucas, “Sur les congruences des nombres eulériens et des coeficients diiérentiels des fonctions trigonométriques, suivant un module premier," Bulletin de la Société mathématique de France 6 (1878) , 49−54.
https://www.numdam.org/item/?id=BSMF_1878__6__49_1

---

2026-06-23　ウィルソンの定理の証明（ラグランジュ）の応用　逆三角の倍数列島

再び (x + 0)(x + 1)(x + 2)(x + 3)(x + 4) = x⁵ + 10x⁴ + 35x³ + 50x² + 25x + 0 の係数（W₀ = 1, W₁ = 10, W₂ = 35, ··· とする）や、同種の数について。n が素数のとき (x + 0)(x + 1)···(x + n − 1) の W₁ ～ W_n−1 として n の倍数が並ぶ（Lagrange の定理）。

n = 0, 1, 2, ··· のそれぞれに対する W たちを逆順で三角形状 ◣ に並べた場合、「ある数 A の n 倍 + A の左の数」が「A の真下の数」に（例: 10 × 5 + 35 = 85）。よって p の倍数が並んでいる下には「p の倍数Ⅱ世」が出現。「Ⅱ世」が並べば、下に「Ⅲ世」。こうして「同じ p の倍数たち」が逆三角形状 ◥ に配列される。

Glaisher は「二項係数の下克上」（Lucas の定理）を利用して、このような現象を検討した。

§7　『ゴルゴ13』にも登場したウィルソンの定理。その内容は、
　　　1⋅2⋅3⋅4 = 24　は　5 の倍数より 1 小さい
　　　1⋅2⋅3⋅4⋅5⋅6 = 720　は　7 の倍数より 1 小さい
　　　︙
等々。一般に「p が素数なら、 1 から p − 1 までの積は p の倍数より 1 小さい」という命題だ。

現代の観点からは、その証明は易しい。しかし、フランスのラグランジュが最初にそれを証明したとき――1770年代、マリー・アントワネットが10代の少女で、その首がちゃんと胴体の上に乗っていた時代――の古風な論法は、ちょっとややこしい。その内容をあらためて整理し直してみると、次の通り。

n を 3 以上の整数とする。 ƒ₁(x) = (x + 1)(x + 2)··· (x + n − 1) を展開した n − 1 次式 を
　　ƒ₂(x) = W₀⋅xⁿ⁻¹ + W₁⋅xⁿ⁻² + W₂⋅xⁿ⁻³ + ···  + W_n−3⋅x² + W_n−2⋅x¹ + W_n−1⋅x⁰
とする。もちろん W₀ = 1, x⁰ = 1, x¹ = x であるが、表記の統一のため、あえて「1 乗」なども明記した。 ƒ₂ は ƒ₁ を展開しただけで、両者は同一の多項式である！

ƒ₁(x) の積を展開し、同類項をまとめて ƒ₂(x) の形にしたときの W₁ や W₂ などの係数――それらが具体的にどんな数になるかは n の値次第。ラグランジュの論法では、その値を知る必要はない。任意の素数 n について定理を証明したいのだから、 n などの値が具体的に固定されていたら、むしろうまくない。

とはいえ n を特定した方が分かりやすい部分もある。参考として n = 5 の場合を付録Aに記載した。

ƒ₁ の定義から:
　　ƒ₁(x + 1) = ((x + 1) + 1)((x + 1) + 2)···((x + 1) + n − 1) = (x + 2)(x + 3)··· (x + n)　　サ

サの両辺を x + 1 倍すると、 n 個の因子がきれいに並ぶ:
　　(x + 1)⋅ƒ₁(x + 1) = (x + 1)⋅(x + 2)(x + 3)··· (x + n)
　　 = (x + 1)(x + 2)··· (x + n − 1)⋅(x + n) = ƒ₁(x)⋅(x + n)
ƒ₁ と ƒ₂ は同じ多項式なので、
　　(x + 1)⋅ƒ₂(x + 1) = ƒ₁(x)⋅(x + n) = ƒ₂(x)⋅(x + n)　　（✽）
でもある。

ƒ₂ の定義から:
　　ƒ₂(x + 1) = W₀⋅(x + 1)ⁿ⁻¹ + W₁⋅(x + 1)ⁿ⁻² + ···  + W_n−2⋅(x + 1)¹ + W_n−1⋅(x + 1)⁰　　シ

シの両辺を (x + 1) 倍すると、右辺の (x + 1)^● たちの ● がそれぞれ 1 ずつ増えて、
　　(x + 1)⋅ƒ₂(x + 1)
　　 = W₀⋅(x + 1)ⁿ + W₁⋅(x + 1)ⁿ⁻¹ + ···  + W_n−2⋅(x + 1)² + W_n−1⋅(x + 1)¹　　㊧
となる。これが等式（✽）の左端に当たる！

再び ƒ₂ の定義から:
　　ƒ₂(x)⋅(x + n)
　　 = {W₀⋅xⁿ⁻¹ + W₁⋅xⁿ⁻² + W₂⋅xⁿ⁻³ + W₃⋅xⁿ⁻⁴ + ···  + W_n−1⋅x⁰}⋅(x + n)　　㊨
これが等式（✽）の右端に当たる！

㊧と㊨は等式（✽）の左右だから、同一の内容（多項式）を表しているはず。よって、それぞれを展開したら、各係数が一致するはず。――これがラグランジュの議論のアイデアであった。

さて、㊨の展開は易しい。{ } 内の x 倍
　　　　　W₀⋅xⁿ + W₁⋅xⁿ⁻¹ + W₂⋅xⁿ⁻² + W₃⋅xⁿ⁻³ + ···  + W_n−1⋅x¹
と、 { } 内の n 倍
　　　　　　nW₀⋅xⁿ⁻¹ + nW₁⋅xⁿ⁻² + ···  + nW_n−2⋅x¹ + nW_n−1⋅x⁰
の和だから、結果は、係数だけ書くと、
　　xⁿ　の係数は　W₀　だけ
　　xⁿ⁻¹　の係数は　W₁ + nW₀　　《ス》
　　xⁿ⁻²　の係数は　W₂ + nW₁　　《セ》
　　xⁿ⁻³　の係数は　W₃ + nW₂　　《ソ》
等々となるだろう。

㊧、すなわち
　　W₀⋅(x + 1)ⁿ + W₁⋅(x + 1)ⁿ⁻¹ + ···  + W_n−2⋅(x + 1)² + W_n−1⋅(x + 1)¹
の展開には、二項定理が必要。 (x + 1)ⁿ や (x + 1)ⁿ⁻¹ などの「二項の和の累乗」をそれぞれ展開すると:
　　　　㊧ = W₀⋅[(n C 0)xⁿ + (n C 1)xⁿ⁻¹ + (n C 2)xⁿ⁻² + (n C 3)xⁿ⁻³ + (n C 4)xⁿ⁻⁴ + ···  + (n C n)x⁰]
　　 + W₁⋅[(n − 1 C 0)xⁿ⁻¹ + (n − 1 C 1)xⁿ⁻² + (n − 1 C 2)xⁿ⁻³ + (n − 1 C 3)xⁿ⁻⁴ + ···  + (n − 1 C n − 1)x⁰]
　　 + W₂⋅[(n − 2 C 0)xⁿ⁻² + (n − 2 C 1)xⁿ⁻³ + (n − 2 C 2)xⁿ⁻⁴ + ···  + (n − 2 C n − 2)x⁰]
　　 + W₃⋅[(n − 3 C 0)xⁿ⁻³ + (n − 3 C 1)xⁿ⁻⁴ + ··· + (n − 3 C n − 3)x⁰]
　　　︙
　　 + W_n−1⋅[(1 C 0)x⁰ + (1 C 1)x⁰]

このうち xⁿ⁻² の係数
　　W₀⋅(n C 2) + W₁⋅(n − 1 C 1) + W₂⋅(n − 2 C 0) = (n C 2) + W₁⋅(n − 1) + W₂
は、㊨の xⁿ⁻² の係数――すなわち《セ》の W₂ + nW₁ ――に等しいはずだから、
　　(n C 2) + W₁⋅(n − 1) = nW₁　整理すると　(n C 2) = W₁　　タ
が成り立つだろう^†。 xⁿ⁻³ の係数は、㊨の xⁿ⁻³ の係数《ソ》と等しいはずだから、
　　(n C 3) + W₁⋅(n − 1 C 2) + W₂⋅(n − 2) + W₃ = W₃ + nW₂
　　整理すると　(n C 3) + W₁⋅(n − 1 C 2) = 2W₂　　チ
が成り立つだろう。同様に進めれば、
　　(n C 4) + W₁⋅(n − 1 C 3) + W₂⋅(n − 2 C 2) = 3W₃　　ツ
　　(n C 5) + W₁⋅(n − 1 C 4) + W₂⋅(n − 2 C 3) + W₃⋅(n − 3 C 2) = 4W₄　　テ
　　　︙
となる。

n が素数の場合、これらの関係を基に Lagrange の定理が示され、容易に Wilson の定理と Fermat の小定理が派生する（ここでは、それらについては略）。

† 任意の整数 a について (a C 1) は a に等しく、 (a C 0) は 1 に等しい。「二項係数・超入門」参照。

§8　W₁, 2W₂, 3W₃, 4W₄, ···  を表す上記の等式タ・チ・ツ・テ…などを、一つの一般公式に要約すると:

Lagrange の再帰公式　1 以上 n 未満の整数 μ について、 μ⋅W_μ を W_j (0 ≤ j ≤ μ − 1) についての式として、次のように表現可能:
　　μ⋅W_μ = W₀⋅(n C μ + 1) + W₁⋅(n − 1 C μ) + W₂⋅(n − 2 C μ − 1) + ··· + W_μ−1⋅(n − μ + 1 C 2)

ここで W_j は、
　　ƒ₁(x) = (x + 1)(x + 2)···(x + n − 1)
を展開した n − 1 次式の x^n−j−1 の係数に等しい。あるいは、実質的に同じことだが、
　　ɡ(x) = (x + 0)(x + 1)(x + 2)···(x + n − 1)
を展開した n 次式の x^n−j の係数に等しい（どちらの定義でも、最高次の係数 1 を W₀ とし、降べき順に W₂, W₃ 等とする。 1 倍 を表す係数 W₀ は、通常、書いても書かなくても同じことであり、任意に省略可能）。

〔例〕　n = 5 の場合:
　　(x + 0)(x + 1)(x + 2)(x + 3)(x + 4) = 1x⁵ + 10x⁴ + 35x³ + 50x² + 24x¹ + 0x⁰
　　W₀ = 1, W₁ = 10, W₂ = 35, W₃ = 50, W₄ = 24, W₅ = 0
再帰的公式の数値例:
　　1⋅W₁ = (5 C 2) = 10　⇒　W₁ = 10
　　2⋅W₂ = (5 C 3) + W₁⋅(4 C 2) = 10 + 10⋅6 = 70　⇒　W₂ = 35
　　3⋅W₃ = (5 C 4) + W₁⋅(4 C 3) + W₂⋅(3 C 2) = 5 + 10⋅4 + 35⋅3 = 150　⇒　W₃ = 50

再帰公式を使って μ⋅W_μ を求めるには、二項係数の下側インデックス μ + 1 から開始（上側インデックスは n から）。上下のインデックスは項ごとに 1 ずつ減少し、下側が 2 になると打ち切り。 W_j の j は 0 から始まり 1 ずつ増える（W₀ は省略可）。この公式は理論的に有用だが、実際に W の値を求めたい場合には、もっと便利な方法もある（例えば、パスカルの三角形の変種）。

n 次式 ɡ(x) を基準にするなら、最初の係数 W₀ から数えて n + 1 個目の係数 W_n も意味を持ち（μ = n）、それは ɡ(x) の定数項（0 次の係数）を表す。明らかに W_n = 0。再帰公式は（形式的に）その場合についても有効（右辺は自明な 0 の和となる）。

〔参考〕　W_μ は曖昧な記法で、その具体的意味は、暗黙に仮定されている n によって定まる。特定の n に関連する W_μ は n 次式 ɡ(x) の x^n−μ の係数であり、根と係数の関係により、「1 から n − 1 までの数」の μ 個ずつの積の和 S_μ(n − 1) に等しい。それは、符号なし第一種スターリング数 [n S n − μ] と一致する。

§9　p を任意の奇素数、 n を p より大きい整数とする。 n を p で割った商と余りをそれぞれ a と u としよう:
　　n = ap + u　ただし　0 ≤ u < p

議論の便宜上、これ以降しばらくの間 n が p で割り切れるケースを別にして、 u ≠ 0 と仮定する。

このとき、上記の再帰公式で μ = u と置くと、次のような u 項の和となる。
　　u⋅W_u = W₀⋅(n C u + 1) + W₁⋅(n − 1 C u) + W₂⋅(n − 2 C u − 1) + ··· + W_u−1⋅(n − u + 1 C 2)
　　 = (ap + u C u + 1) + W₁⋅(ap + u − 1 C u) + W₂⋅(ap + u − 2 C u − 1) + ··· + W_u−1⋅(ap + 1 C 2)

この右辺の二項係数が表す各整数は、ある種の例外ケースを別にすると、「余りの下剋上」によりどれも p で割り切れる。実際、上下のインデックスをそれぞれ p で割ったとき:
　　(ap + u C u + 1)　の「下の余り」 u + 1 は「上の余り」 u を超える（例外あり）
　　(ap + u − 1 C u)　の「下の余り」 u は「上の余り」 u − 1 を超える
　　(ap + u − 2 C u − 1)　の「下の余り」 u − 1 は「上の余り」 u − 2 を超える
　　　︙
　　(ap + 2 C 3)　の「下の余り」 3 は「上の余り」 2 を超える
　　(ap + 1 C 2)　の「下の余り」 2 は「上の余り」 1 を超える

例外は u = p − 1 のケース。その場合、最初の下側インデックスにおいて u + 1 = p を p で割った余りは 0 なので、下克上が不成立。

この他にも、もしも例えば下側インデックス u − 1 （ないし u − 2 等々）のケースで、それぞれ u = 1 （ないし u = 2 等々）であれば、下剋上は成立しないはず。しかしこの再帰公式には項が u 個しかない。 u = 1 （あるいは u = 2 等々）の場合、下側インデックス u + 1 （ないし u 等々）の項までで足し算は終了し、下側インデックス u − 1 （ないし u − 2 等々）を含む項は生じない。例外として u = p − 1 の場合にだけ、「下克上が不成立」という現象が起こる（右辺の最初の項において）。

u = p − 1 のケースを除外して 1 ≤ u ≤ p − 2 と仮定するなら、再帰公式の右辺各項は、二項係数の「下剋上」による p の倍数を因子とし、従って、それら各項の和に等しい左辺 u⋅W_u も p の倍数。従って W_u が p の倍数でなければならない（今考えている条件下では u は p の倍数ではないから）。すなわち:

補題3　p を奇素数、 n を p より大きい整数、 n を p で割った余りを u とする。 u = 0 の場合と u = p − 1 の場合を除けば、 W_u つまり S_u(n − 1) は必ず p で割り切れる。

u = 0 の場合に関しては、補題3の言う通り確かに W₀ = S₀(n − 1) = 1 は p で割り切れないけれど、 W₁ 以降において話が変わってくる。よって u = 0 のケースについては別扱いとする。

〔例1〕　p = 3 の場合。 n = 4 や n = 7 を p で割ると 1 余る。 W₁ = S₁(4 − 1) = 6 は p で割り切れる。 S₁(7 − 1) = 21 も。
n = 5 や n = 8 を p で割ると 2 余る。 2 = p − 1 なので、これは例外ケースに当たる。実際 W₂ = S₂(5 − 1) = 35 は p で割り切れない。 S₂(8 − 1) = 322 も。

〔例2〕　p = 5 の場合。 n = 6 を p で割ると 1 余る。 W₁ = S₁(6 − 1) = 15 は p で割り切れる。
n = 7 を p で割ると 2 余る。 W₂ = S₂(7 − 1) = 175 は p で割り切れる（注: 上記の W₁ とこの W₂ では基準となる n が異なる。以下の W₃ 等についても、一般には基準となる n が異なる）。
n = 8 を p で割ると 3 余る。 W₃ = S₃(8 − 1) = 1960 は p で割り切れる。
n = 9 を p で割ると 4 余る。 4 = p − 1 なので、これは例外ケース。実際 W₄ = S₄(9 − 1) = 22449 は p で割り切れない。

補題3の内容は u が W_u を割る十分条件だが、必要条件ではない。というのも、下剋上が起きなくても二項係数が p で割り切れる場合がある（§5）。例えば p = 3, n = 11 のとき u = 2 = p − 1 なので、補題3の条件（十分条件）は満たされない。にもかかわらず n = 11 に対する W₂ つまり S₂(11 − 1) = 1320 は、実際には 3 で割り切れる。この例では (11 C 2 + 1) において（p = 3 に関して）下剋上が起きていないので、補題3のロジックでは「それで十分」と認定されない。しかるに 11⋅10⋅9/3! = 165 の素因子 3 の個数は分子側が二つ、分母側が一つだから、約分後も素因子 3 が残り 3 で割り切れる数が生じる。

§10　引き続き n (= ap + u) を p で割った余りを u とし、 u ≠ 0 と仮定する。再帰公式で μ = u と置く代わりに μ = u + 1 としてみる。すなわち p が W_u を割るかを問題にするのではなく、今度は p が W_u+1 を割るかを問題にする。
　　(u + 1)⋅W_u+1 = W₀⋅(n C u + 2) + W₁⋅(n − 1 C u + 1) + W₂⋅(n − 2 C u) + ··· + W_u+1⋅(n − u C 2)
　　 = (kp + u C u + 2) + W₁⋅(kp + u − 1 C u + 1) + W₂⋅(kp + u − 2 C u) + ··· + W_u+1⋅(kp C 2)

u + 2 が p または p + 1 に等しい場合、および u + 1 が p に等しい場合を例外として（これら例外ケースの条件を一つにまとめて u + 2 ≥ p と述べることができる）、どの二項係数でも下克上が置きる。つまり u + 2 < p と仮定するなら、 W_u のみならず W_u+1 も p で割り切れる。

さらに μ = u + 2 の場合（p が W_u+2 を割るか否か）:
　　(u + 2)⋅W_u+2 = (kp + u C u + 3) + W₁⋅(kp + u − 1 C u + 2) + W₂⋅(kp + u − 2 C u + 1) + W₃⋅(kp + u − 3 C u)
　　 + W₄⋅(kp + u − 4 C u − 1) + ··· + W_u⋅(kp C 3) + W_u+1⋅(kp − 1 C 2)

u + 3 ≥ p なら、右辺の最初の3項の中に、下剋上が起きないものがある。 u + 3 < p と仮定するなら、それらの項も含めて、右辺の二項係数は、最後の一つを除き p で割り切れる。最後の二項係数では、下剋上が起きない（下の余り 2 は上の余り p − 1 を超えない）。しかし仮定は u + 2 < p を含意するので、前述のように W_u+1 は p で割り切れ、よって最後の項も p で割り切れ、結局、右辺の全部の項は p で割り切れる。つまり u + 3 < p ならば W_u+2 も p で割り切れる。

このように μ が u + 2 以上のとき、 u の範囲を適切に制限しても、最後の幾つかの二項係数では下剋上が起きない（つまり一般には p で割り切れない）。にもかかわらず、そのような係数を含む項について、もう一つの因子 W が p で割り切れることが（μ が 1 小さい場合の議論から）既に分かっているため、結局、その項は p で割り切れる。「p がその項を割ることの証明を μ が 1 小さい場合の議論に帰着させる」という、一種の帰納法が成り立つ。

いっそう一般的に、 μ = u + α の場合（α は正整数）について（ただし W_u+α が n 次式の係数として意味を持つように u + α ≤ n を原則とする）。
　　(u + α)⋅W_u+α = (kp + u C u + α) + W₁⋅(kp + u − 1 C u + α − 1) + ··· + W_u⋅(kp C α)
　　 + W_u+1⋅(kp − 1 C α − 1) + ··· + W_u+α−3⋅(kp − α + 3 C 3) + W_u+α−2⋅(kp − α + 2 C 2)

u + α < p と仮定すると、右辺の W_u を含む項までは p の倍数（下剋上成立。下側の余りは上側に比べて α だけ大きい）。 W_u+1 を含む項以降では下剋上が起きないが、帰納的な議論から W_u+1, W_u+2 などは p の倍数であり、結局、各項は p の倍数。

以上を要約すると、次の通り。

補題4（cf. Glaisher [7], §43）　p を n 未満の素数、 n を p で割ったときの余りを u とする。もし 1 ≤ u ≤ p − 2 なら、
　　W_u, W_u+1, W_u+2, ··· , W_p−2
の各数は p で割り切れる。

補題4の条件が満たされるなら、確実に W は p で割り切れる。それ以外の場合、 W が p で割り切れるのか否かを一般には（まだ）決定できない。

〔例3〕　n = 6, p = 5 の場合を考える。 u = 1 である。関連して W_u から W_p−2 までの数、すなわち W₁ = 15, W₂ = 85, W₃ = 225 の三つの数は、 p の倍数。 W_p−1 = W₄ = 274 はそうでない。ちなみに、補題4の対象範囲外だが、 W₅ = 120 = 5! も p の倍数。

〔例4〕　n = 7, p = 5, u = 2 に関連して W_u から W_p−2 までの数、すなわち W₂ = 175 と W₃ = 735 の二つの数は、 p の倍数。 W_p−1 = W₄ = 1624 はそうでない。ちなみに W₆ = 720 = 6! も p の倍数。

〔例5〕　n = 8, p = 5, u = 3 に関連して W_u から W_p−2 までの数が、すなわち一つの数 W₃ = W_p−2 = 1960 だけが、補題4の対象範囲内の p の倍数。 W_p−1 = W₄ = 6769 はそうでない。ちなみに W₇ = 5040 = 7! も p の倍数。

スターリング数の言葉では―― n を p で割った余りが u のとき、 p が [n S y] を割る十分条件は u ≤ n − y ≤ p − 2 つまり n − p + 2 ≤ y ≤ n − u。例4の場合、 4 ≤ y ≤ 5 なら、条件が満たされる。実際 [7 S 4] = 735 と [7 S 5] = 175 は 5 の倍数。それとは別に [n S 1] = (n − 1)! は、 p ≤ n − 1 なら当然 p で割り切れる。

Glaisher の証明では、 Lagrange の定理と、二項係数に関する Lucas の定理が使われている。結論の少なくとも一部は、第一種スターリングの三角形の性質からも、直ちに得られる。例えば 5 の段には、両端以外は 5 の倍数が並んでいる（Lagrange の定理）。 6 の段の各数は、真上の数の 5 倍と左上の数の和だから、 5 の段に 5 の倍数が並んでいる以上、 6 の段にも 5 の倍数が「遺伝」するのは、当然（一つの例外を除き、どのケースも「両親とも 5 の倍数なら、子は再び 5 の倍数」という原理による）。「そのスターリング数は 5 の倍数」という性質は、部分的には 6 の段から 7 の段にも継承され、そのまた一部は 8 の段に再継承される。一般に、同様の仕組みによって、 Lagrange の定理による p の倍数列の下には、逆三角形状に p の倍数が並ぶ。

付録A　Lagrange の (x + 1)(x + 2)···(x + n − 1) の処理の具体例。 n = 5, n − 1 = 4 のケースの概要。

ƒ₁(x) = (x + 1)(x + 2)(x + 3)(x + 4) = (x + 1)(x + 4)⋅(x + 2)(x + 3) = (x² + 5x + 4)(x² + 5x + 6)
　　 = [(x² + 5x) + 4][(x² + 5x) + 6] = (x² + 5x)² + 10(x² + 5x) + 24
　　 = (x⁴ + 2⋅x²⋅5x + 25x²) + 10x² + 50x + 24 = (x⁴ + 10x³ + 25x²) + 10x² + 50x + 24
　　 = x⁴ + 10x³ + 35x² + 50x + 24

従って、4次式 (x + 1)(x + 2)(x + 3)(x + 4) を展開して、
　　ƒ₂(x) = W₀⋅x⁴ + W₁⋅x³ + W₂⋅x² + W₃⋅x¹ + W₄⋅x⁰
の形式にする場合、具体的な数値は:
　　W₀ = 1, W₁ = 10, W₂ = 35, W₃ = 50, W₄ = 24

個々の数値と無関係に、一般論的に W たちの再帰的関係を導く手順は、次の通り。

　ƒ₁ と ƒ₂ は同一の多項式の別表現に過ぎないから、
　　ƒ₁(x + 1) = (x + 2)(x + 3)(x + 4)(x + 5)　と
　　ƒ₂(x + 1) = W₀⋅(x + 1)⁴ + W₁⋅(x + 1)³ + W₂⋅(x + 1)² + W₃⋅(x + 1)¹ + W₄⋅(x + 1)⁰
は等しい。よって、
　　《ア》　(x + 1) ƒ₁(x + 1) = (x + 1)(x + 2)(x + 3)(x + 4)(x + 5)　と
　　《イ》　(x + 1) ƒ₂(x + 1) = W₀⋅(x + 1)⁵ + W₁⋅(x + 1)⁴ + W₂⋅(x + 1)³ + W₃⋅(x + 1)² + W₄⋅(x + 1)¹
も等しい。そして、この《ア》は次に等しい。
　　(x + 1)(x + 2)(x + 3)(x + 4)⋅(x + 5) = ƒ₁⋅(x + 5) = ƒ₂⋅(x + 5)
　　 = [W₀⋅x⁴ + W₁⋅x³ + W₂⋅x² + W₃⋅x¹ + W₄⋅x⁰]⋅(x + 5)　　Ⓐ

　《イ》を二項展開すると:
　　W₀ [(5 C 0)⋅x⁵ + (5 C 1)⋅x⁴ + (5 C 2)⋅x³ + (5 C 3)⋅x² + (5 C 4)⋅x¹ + (5 C 5)⋅x⁰]
　　 + W₁ [(4 C 0)⋅x⁴ + (4 C 1)⋅x³ + (4 C 2)⋅x² + (4 C 3)⋅x¹ + (4 C 4)⋅x⁰]
　　 + W₂ [(3 C 0)⋅x³ + (3 C 1)⋅x² + (3 C 2)⋅x¹ + (3 C 3)⋅x⁰]
　　 + W₃ [(2 C 0)⋅x² + (2 C 1)⋅x¹ + (2 C 2)⋅x⁰]
　　 + W₄ [(1 C 0)⋅x¹ + (1 C 1)⋅x⁰]　　Ⓑ

　Ⓐ と Ⓑ は等しいので、対応する各係数は一致。係数比較の便宜上、 Ⓑ の3次の項だけ集めると:
　　W₀⋅(5 C 2)⋅x³ + W₁⋅(4 C 1)⋅x³ + W₂⋅(3 C 0)⋅x³
同様に2次の項　W₀⋅(5 C 3)⋅x² + W₁⋅(4 C 2)⋅x² + W₂⋅(3 C 1)⋅x² + W₃⋅(2 C 0)⋅x²
1次の項　W₀⋅(5 C 4)⋅x¹ + W₁⋅(4 C 3)⋅x¹ + W₂⋅(3 C 2)⋅x¹ + W₃⋅(2 C 1)⋅x¹ + W₄⋅(2 C 0)⋅x¹
0次の項　W₀⋅(5 C 5)⋅x⁰ + W₁⋅(4 C 4)⋅x⁰ + W₂⋅(3 C 3)⋅x⁰ + W₃⋅(2 C 2)⋅x⁰ + W₄⋅(1 C 1)⋅x⁰

一方、 Ⓐ を再掲すると [W₀⋅x⁴ + W₁⋅x³ + W₂⋅x² + W₃⋅x¹ + W₄⋅x⁰]⋅(x + 5):
　　3次の項　W₂⋅x³ + 5W₁⋅x³　そして　2次の項　W₃⋅x² + 5W₂⋅x²
　　1次の項　W₄⋅x¹ + 5W₃⋅x¹　そして　0次の項　5W₄⋅x⁰

　Ⓐ と Ⓑ の3次の項の係数の比較から:
　　W₂ + 5W₁ = (5 C 2) + W₁⋅4 + W₂⋅1　　← 両辺の W₂ はキャンセルされる
　　∴　W₁ = (5 C 2)　　❶

2次の項の係数の比較から:
　　W₃ + 5W₂ = (5 C 3) + W₁⋅6 + W₂⋅3 + W₃⋅1　　← 両辺の W₃ はキャンセル
　　∴　2W₂ = (5 C 3) + W₁⋅(4 C 2)　　❷

1次の項の係数の比較から:
　　W₄ + 5W₃ = (5 C 4) + W₁⋅(4 C 3) + W₂⋅(3 C 2) + W₃⋅2 + W₄⋅1
　　∴　3W₃ = (5 C 4) + W₁⋅(4 C 3) + W₂⋅(3 C 2)　　❸

0次の項の係数の比較から:
　　W₀⋅1 + W₁⋅1 + W₂⋅1 + W₃⋅1 + W₄⋅1 = 5W₄
　　∴　4W₄ = (5 C 5) + W₁⋅(4 C 4) + W₂⋅(3 C 3) + W₃⋅(2 C 2)　　❹

具体的な数値計算とは別に、❶❷❸❹共通の次の構造を観察できる（μ = 1, 2, 3, 4）:
　　μ⋅W_μ = (5 C μ + 1) + W₁⋅(4 C μ) + W₂⋅(3 C μ − 1) + W₃⋅(2 C μ − 2)

これが Lagrange の再帰公式の例（n = 5 の場合）。 μ は 1 以上 n 未満の整数。例えば μ = 3 の場合、公式は ❸ の意味になる。

右辺で足し算される項は必ずしも四つではなく、ケースバイケース。項ごとに二項係数のインデックスがだんだん小さくなり、下側インデックスが 2 になる項まで足したら、そこで終了。右辺の最初の二項係数の上側インデックスは n = 5。複数の項がある場合、二項係数の上下のインデックスは項ごとに 1 ずつ減少し、 W_j の j は 0, 1, 2, ··· と増加する（ここでは、右辺の先頭にあるはずの因子 W₀ = 1 の表記を省略した）。

---