7. Die Sätze von Kummer und Lukas

Wir geben noch eine Beschreibung unserer Intervallfolgen über Reste. Als Anwendung erhalten wir ein klassisches Ergebnis von Ernst Kummer (1852).

Satz (Charakterisierung über Koreste)

Sei x > 0. Weiter seien 0 < r_a, r_b ≤ x die Koreste der Division von a bzw. b durch x, d. h. es gibt ganze Zahlen q_a, q_b mit

a = q_a x − r_a, b = q_b x − r_b.

Dann gilt

x  ∈  ⋃_d ≥ 1 I(d) = ∪_d ≥ 1 ] a/d, b/s(d) ] genau dann, wenn r_a/r_b ≤ a/b.

Beweis

Sei d ≥ 1 derart, dass x  ∈  ] a/d, a/(d − 1) ]. Dann gilt

d = ⌊a/x⌋ + 1 = (a + r_a)/x,

s(d) + 1 = ⌈bd/a⌉ = ⌈b/x (1 + r_a/a)⌉.

Damit ergibt sich die folgende Äquivalenzenkette:

x  ∈  I(d) = ] a/d, b/s(d) ] genau dann, wenn

s(d) ≤ b/x genau dann, wenn

⌈b/x (1 + r_a/a)⌉ ≤ 1 + b/x genau dann, wenn

⌈b/x + br_a/(xa)⌉ ≤ 1 + b/x genau dann, wenn

⌈− r_b/x + br_a/(xa)⌉ ≤ 1 − r_b/x genau dann, wenn

⌈(br_a − ar_b)/(xa)⌉ ≤ 0 genau dann, wenn

br_a ≤ ar_b genau dann, wenn r_a/r_b ≤ a/b.

Weiter brauchen wir noch folgende einfache Beobachtung über Reste:

Satz (Koreste von a, b, ℓ)

Seien 0 < r_a, r_b, r_ℓ ≤ x die Koreste der Division von a, b bzw. ℓ durch x. Dann gilt r_b = r_a + r_ℓ oder r_b = r_a + r_ℓ − x. Weiter sind äquivalent:

(1)	r_b = r_a + r_ℓ.

(2)	r_a < r_b und r_ℓ < r_b.

(3)	r_a < r_b oder r_ℓ < r_b.

Beweis

Die erste Aussage folgt aus b = a + ℓ. Die Äquivalenzen ergeben sich aus r_a, r_ℓ > 0 und x − r_a, x − r_ℓ ≤ 0.

Damit erhalten wir nun:

Korollar

In der Situation I = ⋃_d ≥ 1 I_{n − k,n}(d) ∪ ⋃_c ≥ 1 I_k,n(c) der Binomialkoeffizienten sind für alle x > 0 äquivalent:

(1)

x  ∈  I.

(2)	r_n − k/r_n ≤ (n − k)/n oder r_k/r_n < k/n.

(3)	r_n − k < r_n oder (und) r_k < r_n.

(4)	r_n − k + r_k = r_n.

Beweis

Gilt r_n − k/r_n > (n − k)/n und r_k/r_n > k/n, so ist r_n − k + r_k > r_n. Dies zeigt, dass aus Aussage (4) die Aussage (2) folgt. Der Rest ergibt sich aus den obigen Ergebnissen.

Korollar (Satz von Kummer)

Sei p prim. Dann gilt:

ex_p( $( \binom{n}{k} )$ ) = |{ i ≥ 1 | r_b(pⁱ) = r_a(pⁱ) + r_ℓ(pⁱ) }|

= |{ e ≥ 1 | r_k(pⁱ) < r_n(pⁱ) }|

= „die Anzahl der Überträge der Addition von k und n − k in Basis p“.

Insbesondere ist $( \binom{n}{k} )$ genau dann durch p teilbar, wenn in p-adischer Darstellung eine Ziffer von n kleiner ist als die entsprechende Ziffer von k. Genauer ist die Anzahl dieser Ziffern der p-Exponent von $( \binom{n}{k} )$ .

Beweis

In Basis p findet bei der Addition von k und n − k genau dann ein Übertrag an der i-ten Stelle statt, wenn r_k(pⁱ) < r_n(pⁱ). Dies ist äquivalent dazu, dass die i-te Ziffer der p-adischen Darstellung von n kleiner ist als die entsprechende Ziffer von k.

Binomialkoeffizienten modulo p

Wir geben noch einen direkten Beweis des Satzes von Kummer (1852). Die Methode ergibt zudem eine Formel für die Reste von Binomialkoeffizienten modulo einer Primzahl (Satz von Lucas 1878).

Satz (Sätze von Kummer und Lucas)

Seien n, k mit 0 ≤ k ≤ n, und sei p prim. Weiter seien n = (n_j … n₀)_p, k = (k_j … k₀)_p und n − k = (d_j … d₀)_p in p-adischer Darstellung. Schließlich sei e der p-Exponent von $( \binom{n}{k} )$ . Dann gilt:

(1)	Satz von Kummer: Ist k_i > n_i für ein i, so ist $( \binom{n}{k} )$ durch p teilbar. Genauer ist e die Anzahl der Überträge der p-adischen Addition von k und n − k (und damit die Anzahl aller i < j mit n_i < k_i).

(2)	Satz von Lucas (starke Form): Es gilt ¹_p^e $( \binom{n}{k} )$ ≡ (−1)^e ∏_{0 ≤ i ≤ j} ^n_i_{k_i d_i} mod(p). Ist k_i ≤ n_i (und d_i = n_i − k_i) für alle i, so gilt $( \binom{n}{k} )$ ≡ ∏_{0 ≤ i ≤ j} $( \binom{n_{i}}{k_{i}} )$ mod(p).(Satz von Lucas)

Beweis

Sei m ≥ 1 beliebig, und sei m = (m_j … m₀)_p in p-adischer Darstellung. Wir setzen für i = 0, …, j:

M_i = { (z_j … z_i)_p | 1 ≤ (z_j … z_i 0 … 0)_p ≤ (m_j … m₀)_p, z_i ≠ 0 }.

Der Mengen M_i entstehen, wenn wir in den p-adischen Darstellungen der Zahlen 1, …, m alle Endziffern 0 streichen: genau i Endziffern 0 liefern ein Element von M_i. Setzen wir [ z ]_p = z/ex_p(z) für alle z ≥ 1, so gilt

M_i = { [ z ]_p | 1 ≤ z ≤ m, exp_p(z) = i } für i = 0, …, j.

Unter Verwendung des Satzes von Legendre gilt:

(+)	m!	= ∏_{0 ≤ i ≤ j, z  ∈  M_i} z pⁱ = p^e_m ∏_{0 ≤ i ≤ j, z  ∈  M_i} z, wobei
	e_m	= ex_p(m!) = ∑_{1 ≤ i ≤ j} ⌊^m_pⁱ⌋ = ∑_{1 ≤ i ≤ j} (m_j … m_i)_p.

Hieraus ergibt sich der Satz von Kummer. Denn nach (+) gilt

e = e_n − (e_k + e_n − k) = ∑_{1 ≤ i ≤ j} ((n_j … n_i)_p − ((k_j … k_i)_p + (d_j … d_i)_p))

und für alle i = 1, …, j ist der Summand entweder 1 oder 0, je nachdem, ob bei der Addition von k = (k_j … k₀)_p und n − k = (d_j … d₀)_p an der Stelle i − 1 ein Übertrag auf die Stelle i stattfindet (n_i − 1 < k_i − 1) oder nicht (k_i − 1 ≤ n_i − 1).

Zum Beweis des Satzes von Lucas beobachten wir, dass eine Zahl modulo p äquivalent zur letzten Ziffer ihrer p-adischen Darstellung ist. Damit gilt

[ m! ]_p = m!/p^e_m ≡ ∏_{0 ≤ i ≤ j} ∏_{z  ∈  M_i} z ≡ ∏_{0 ≤ i ≤ j} ∏_{(z_j … z_i)_p  ∈  M_i} z_i mod(p).

Die letzten Ziffern der Zahlen in M₀ durchlaufen genau ⌊ m/p ⌋ oft die Zahlen 1, …, p − 1 und zudem einmal die Zahlen 1, …, m₀. Nach dem Satz von Wilson ist (p − 1)! ≡ −1 mod(p). Dies zeigt:

∏_{z  ∈  M₀} z ≡ m₀! (p − 1)!^⌊m/p⌋ ≡ m₀! (−1)^⌊m/p⌋ mod(p).

Ebenso durchlaufen die letzten Ziffern der Zahlen in M₁ genau ⌊ m/p² ⌋ oft die Zahlen 1, …, p − 1 und zudem einmal die Zahlen 1, …, m₁, sodass

∏_{z  ∈  M₁} z ≡ m₁! (−1)^⌊m/p²⌋ mod(p).

Analoges gilt für die anderen Mengen. Dies zeigt:

(++) [ m! ]_p ≡ m_j! · … · m₀! · (−1)^e_m mod(p).

Wir erhalten also:

¹_p^e $( \binom{n}{k} )$	= ^[ n! ]_p_{[ k! ]_p · [ (n − k)! ]_p}
	≡ $\frac{n_{j}! · … · n_{0}! · (- 1)^{e_{n}}}{k_{j}! · … · k_{0}! · (- 1)^{e_{k}} · d_{j}! · … · d_{0}! (- 1)^{e_{n - k}}}$
	≡ (−1)^e ^{n_j! · … · n₀!}_{k_j! · … · k₀! · d_j! · … · d₀!} mod(p).

Damit ist der Satz von Lucas bewiesen.

Bemerkung

(1)	Den Satz von Lucas können wir äquivalent in der Form $( \binom{n}{k} )$ ≡ $( \binom{n′}{k′} )$ $( \binom{n_{0}}{k_{0}} )$ mod(p) schreiben, mit n′ = (n_j … n₁)_p = ⌊n/p⌋ und k′ = (k_j … k₁)_p = ⌊k/p⌋.

(2)	Es gilt e_m = ∑_{1 ≤ i ≤ j} (m_j … m_i)_p = ^{m − (m₀ + … + m_j)}_p − 1. Denn die erste Summe ist gleich m₁ 1 + m₂(1 + p) + … + m_j(1 + … + p^j − 1). Multiplikation mit p − 1 ergibt (m_j … m₁0)_p − (m₁ + … + m_j). Addition von m₀ in beiden Termen liefert den Zähler der Behauptung.

Beispiel

Wir betrachten p = 5, n = 12 und k = 3. Dann gilt

$( \binom{n}{k} )$ = $( \binom{12}{3} )$ = 220 = 5 · 44, ¹₅ $( \binom{n}{k} )$ = 44 ≡ 4 mod(5).

In Basis 5 gilt

n = 12 = (2, 2)₅, k = 3 = (0, 3)₅, n − k = 9 = (1, 4)₅.

Mit e = 1 ist

(−1)^e ^{n₁! · n₀!}_{k₁! · k₀! · d₁! · d₀!} = − ^{2! · 2!}_{0! · 3! · 1! · 4!} ≡ − ⁻¹₋₁ ≡ 4 mod(5).

Das folgende Diagramm gibt einen Eindruck über die auftretenden Reste.

Die Reste von $( \binom{1400}{400} )$ modulo m für m = 1, …, 2000. Die Reste für Primzahlmoduln sind dabei rot eingefärbt. Genau in den Primzahlbändern des Binomialkoeffizienten sind diese Reste gleich 0.

Binomialkoeffizienten modulo p^e

Der Satz von Lucas lässt sich auf Primzahlpotenzen verallgemeinern (siehe [ Granville 1997 ]). Hierzu definieren wir für alle n ≥ 0 und Primzahlen p die reduzierte Fakultät n!_p durch

(n!)_p = ∏_{1 ≤ k ≤ n, non(p|k)} k.

Wesentlich ist die folgende Verallgemeinerung unserer Berechnung von [ m ]_p:

Satz (reduzierte Fakultäten modulo einer Primzahlpotenz)

Sei p^ν eine Primzahlpotenz. Weiter sei m ≥ 1 mit m = (m_j, …, m₀)_p. Wir setzen:

c = (p^ν!)_p,

σ_m = ∑_{ν ≤ i ≤ j} (m_j … m_i)_p,

m_i,ν = (m_{i + ν − 1} … m_i + 1 m_i)_p für alle 0 ≤ i ≤ j (mit evtl. Führungsnullen).

Dann gilt:

[ m! ]_p ≡ c^σ_m ∏_{0 ≤ i ≤ j} (m_i,ν!)_p mod(p^ν).

Zudem ist c = 1, falls p^ν  ∈  { 2 } ∪ { 8, 16, 32, … }. Andernfalls ist c = −1.

Beweis

Wir definieren die Mengen M_i wie früher. Modulo p^ν ist eine Zahl äquivalent zu den letzten ν Ziffern ihrer p-adischen Darstellung, sodass

[ m! ]_p ≡ ∏_{0 ≤ i ≤ j} ∏_{(z_j … z_i)_p  ∈  M_i} (z_{i + ν − 1} …  z_i + 1 z_i)_p mod(p).

Wir setzen

Z = { k | 1 ≤ k < p^ν, non(p|k) },

sodass c = ∏_{k  ∈  Z} k. Die letzten ν Ziffern der Zahlen in M₀ durchlaufen genau ⌊ m/p^ν ⌋ = (m_j, …, m_ν)_p oft die Zahlen in Z und zudem einmal die nicht durch p teilbaren Zahlen in 1, …, m_0,ν. Ebenso durchlaufen die letzten ν Ziffern der Zahlen in M₁ genau ⌊ m/p^ν + 1 ⌋ = (m_j … m_ν + 1)_p oft die Zahlen in Z und zudem einmal die nicht durch p teilbaren Zahlen im Intervall 1, …, m_1,ν. Analoges gilt für M₂, …, M_j. Wie im Fall ν = 1 ergibt sich hieraus die Formel für [ m!]_p.

Der Zusatz über c ergibt sich durch Verallgemeinerung des Satzes von Wilson durch Bildung von Inversenpaaren modulo p^ν: Die Aussage ist klar für p^ν  ∈  { 2, 4 }. Im Fall p ≠ 2 sind genau 1 und p^ν − 1 selbstinvers modulo p^ν. Ist p^ν = 2^ν mit ν ≥ 3, so sind genau die vier Zahlen 1, 2^ν − 1 − 1, 2^ν − 1 + 1, 2^q − 1 selbstinvers modulo 2^ν, und das Produkt dieser Zahlen ist kongruent 1 modulo p^ν.

Damit können wir nun zeigen:

Satz (Binomialkoeffizienten modulo Primzahlpotenzen)

Seien n, k mit 0 ≤ k ≤ n, und sei p^ν eine Primzahlpotenz. Weiter seien

n = (n_j … n₀)_p, k = (k_j … k₀)_p, n − k = (d_j, …, d₀)_p,

e = |{ i | 0 ≤ i < j, n_i < k_i }|, e* = |{ i | ν − 1 ≤ i < j, n_i < k_i }|.

Dann gilt mit obigen Bezeichnungen:

¹_p^e $( \binom{n}{k} )$ ≡ c^e* ∏_{0 ≤ i ≤ j} ^(n_i,ν!)_p_{(k_i,ν!)_p (d_i,ν!)_p} mod(p^ν).

Beweis

Die Aussage ergibt sich wie im Fall ν = 1 aus der Formel für [ m!] _p mit

σ_n − (σ_k + σ_n − k) = ∑_{ν ≤ i ≤ j} ((n_j … n_i)_p − ((k_j … k_i)_p + (d_j … d_i)_p)).

Beispiel

Wir illustrieren die Formel für [ m! ]_p am Beispiel

p = 5, ν = 2, m = 138 = (0,1,0,2,3)₅ = (m₄m₃m₂m₁m₀)₅.

Die Reste der Zahlen [ 1 ]₅, …, [ 138 ]₅ modulo 25 sind:

1, 2, 3, 4, 1, 6, 7, 8, 9, 2, 11, 12, 13, 14, 3, 16, 17, 18, 19, 4, 21, 22, 23, 24, 1,

1, 2, 3, 4, 6, 6, 7, 8, 9, 7, 11, 12, 13, 14, 8, 16, 17, 18, 19, 9, 21, 22, 23, 24, 2,

1, 2, 3, 4, 11, 6, 7, 8, 9, 12, 11, 12, 13, 14, 13, 16, 17, 18, 19, 14, 21, 22, 23, 24, 3,

1, 2, 3, 4, 16, 6, 7, 8, 9, 17, 11, 12, 13, 14, 18, 16, 17, 18, 19, 19, 21, 22, 23, 24, 4

1, 2, 3, 4, 21, 6, 7, 8, 9, 22, 11, 12, 13, 14, 23, 16, 17, 18, 19, 24, 21, 22, 23, 24, 1,

1, 2, 3, 4, 1, 6, 7, 8, 9, 2, 11, 12, 13

Multiplizieren wir diese Reste auf, so durchlaufen wir die Folge

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24

6 Mal. Der Beitrag dieser Durchläufe zu [ 138!]₅ ist c⁶ = (−1)⁶ = 1. Es gilt 6 = 5 + 1 = (1,0)₅ + (0,1)₅. Weiter durchlaufen wir je einmal die Zahlen

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13 1, 2 1, 2, 3, 4 1

Die Beiträge zur Fakultät sind (13!)_p, (2!)₅, (5)!₅, (1!)₅. In Basis 5 gilt

13 = (2,3)₅ = (m₁m₀)_p, 2 = (0,2)₅ = (m₂m₁)₅,

5 = (1,0)₅ = (m₃m₂)_p, 1 = (0,1)₅ = (m₄m₃)₅.

Insgesamt ist

[ 138! ]₅ ≡ (−1)⁶ · [ 13! ]₅ · [ 2 ]₅ · [ 5 ]₅ · [ 1 ]₅ ≡ 1 · 16 · 2 · 24 · 1 ≡ 18 mod(25)

Satz (Charakterisierung über Koreste)

Beweis

Satz (Koreste von a, b, ℓ)

Beweis

Korollar

Beweis

Korollar (Satz von Kummer)

Beweis

Binomialkoeffizienten modulo p

Satz (Sätze von Kummer und Lucas)

Beweis

Bemerkung

Beispiel

Binomialkoeffizienten modulo pe

Satz (reduzierte Fakultäten modulo einer Primzahlpotenz)

Beweis

Satz (Binomialkoeffizienten modulo Primzahlpotenzen)

Beweis

Beispiel

Satz (Koreste von a, b, ℓ)

Binomialkoeffizienten modulo p^e