5. Primzahlbänder in den Binomialkoeffizienten, I
Wir haben die Primzahlbänder der Binomialkoeffizienten bm,n im Bereich zwischen (m − 1)n und mn bestimmt und darüber hinaus eine Lücke vor (m − 1)n festgestellt. Es stellt sich die Frage, welche Primzahlen in bm,n im Intervall von 2 bis n vorkommen. Ein Spiraldiagramm für b5,720 zeigt weitere Bänder:
Primzahlbänder von b = b5,720 im Bereich von 2 bis 720
Die unteren Bänder wollen wir nun genauer untersuchen. Mit beginnen mit einer allgemeinen und für sich interessanten Problemstellung.
Zählung von Vielfachen in Intervallen
Für das Folgende seien a,b reelle Zahlen mit 0 < a < b. Wir betrachten das nach links halboffene Intervall
I = ] a, b ]
der Länge ℓ = b − a. Weiter sei x eine beliebige positive reelle Zahl. Wir zählen die Vielfachen von x in den Intervallen ] 0, ℓ ] und I. Seien z1 und z2 die entsprechenden Anzahlen, d. h. es gilt
z1x ≤ ℓ, (z1 + 1)x > ℓ,
(d − 1)x ≤ a, dx > a, (d + z2 − 1)x < b, (d + z2)x > b für ein gewisses d ≥ 1.
Beispiel
Für x = 5, a = 39, b = 53, I = ] 39, …, 52 ], ℓ = 13 gibt es die Vielfachen
5, 10 in ] 0, 13 ],
40, 45, 50 in ] 39, …, 52 ].
In diesem Fall ist also z1 = 2, z2 = 3 und d = 8.
Mit der Abrundungsfunktion notiert gilt
z1 = ⌊ℓx⌋, d = ⌊ax⌋ + 1,
z2 = ⌊bx⌋ − ⌊ax⌋ ≤ ⌊b − ax⌋ + 1 = z1 + 1.
Offenbar gilt z2 = z1 oder z2 = z1 + 1, da in jedem Teilintervall
] a, a + x ], ] a + x, a + 2x ], …, ] a + (z1 − 1)x, a + z1x]
von I genau ein Vielfaches von x liegt und sich im Restintervall ] a + z1x, b ] der Länge b − (a + z1x) = ℓ − z1x kein oder genau ein Vielfaches von x befindet. Letzteres ist der Fall, wenn das erste Vielfache dx von x in I nur wenig größer ist als a. Genauer gilt z2 = z1 + 1 genau dann, wenn
dx ∈ ] a, a + ℓ − z1x ] = ] a, b − z1x ].
Dies ist äquivalent zu x ∈ ] a/d, (b − z1x)/d ]. Weiter gilt
x ≤ b − z1xd genau dann, wenn x ≤ bd + z1.
Wir haben also gezeigt, dass z2 = z1 + 1 genau dann gilt, wenn
(+) ad < x ≤ bd + ⌊ℓ/x⌋.
Wir setzen
U = U(d, a, b) = { x | x erfüllt (+) }, V = V(d, a, b) = ] a/d, a/(d − 1) [ ,
mit der Konvention a/0 = ∞. Ist x ∈ U, so gilt
x(d + ℓ/x − 1) < x(d + ⌊ℓ/x⌋) ≤ b,
sodass x(d − 1) < b − ℓ = a, d. h. x < a/(d − 1). Damit ist U eine Teilmenge des offenen Intervalls V.
Als Funktion f (x) = fd,a,b(x) in x > 0 ist die rechte Seite von (+) monoton steigend, stückweise konstant, linksseitig stetig und schließlich konstant gleich b/d. Die Intervalle konstanter Werte wachsen in ihrer Länge streng monoton. Die Funktion springt an den Stellen ℓ/n mit n ≥ 1. Weiter ist f nach unten und oben beschränkt durch die konkaven Funktionen b/(d + ℓ/x) bzw. b/(d + ℓ/x − 1). Folglich ist f in V nach unten und oben beschränkt durch a/d bzw. a/(d − 1), sodass f [ V ] ⊆ V.
Um die Lösungsmenge U zu bestimmen, betrachten wir eine Sprungstelle ℓ/n von f in V. Dann gilt (mit f (∞) = b/d):
(#) f (ℓ/n) < ℓ/n < f (ℓ/(n − 1)) = f (ℓ/n+) (wobei f (a+) = limx↓ a f (x)).
Denn wegen a/d < ℓ/n ist an < ℓd, sodass bn < ℓd + ℓn = ℓ(d + n). Also gilt
ℓ/n > b/(d + n) = f (ℓ/n).
Analog folgt aus ℓ/n < a/(d − 1), dass ℓ/n < f (ℓ/(n − 1)). Damit ist ] ℓ/n, f (ℓ/(n − 1)) ] ein Lösungsintervall von U. (Ist ℓ/n die größte Sprungstelle in V, so liegt ℓ/(n − 1) nicht in V, aber f (ℓ/(n − 1)) wird in V angenommen.) Insgesamt erhalten wir:
Satz (Struktur der Lösungsintervalle)
In obiger Situation gilt: Seien n ≥ 2 und r ≥ 0 derart, dass
x1 = ℓ/(n − 1), x2 = ℓ/(n − 2), …, xr = ℓ/(n − r)
die Sprungstellen von f in V sind. Weiter sei x0 = a/d. Dann gilt mit rechtsseitigen Grenzwerten f (x+) = limy → x, y > x f (y):
(a) | U = ] x0, f (x0+) ] ∪ ] x1, f (x1+) ] ∪ … ∪ ] xr, f (xr+)], |
(b) | x0 < f (x0+) < x1 < f (x1+) < … < xr < f (xr+). |
Die Lösungsmenge ist also eine Vereinigung von r + 1 halboffenen disjunkten und sich nicht berührenden Intervallen positiver Länge.
Unsere Zählung der Vielfachen lässt sich wie folgt interpretieren:
Satz (Indikatorfunktion der Lösungsintervalle)
Sei U = ⋃d ≥ 1 U(d). Dann gilt
⌊b/x⌋ − ⌊a/x⌋ − ⌊n/x⌋ = indU(x) für alle x ∈ ℝ.
Beweis
Die Funktion auf der linken Seite ist die Differenz der Vielfachen von x in den Intervallen ] a, b ] und ] 0, n ]. Nach unseren Berechnungen ist diese Differenz genau dann gleich 1, wenn x ein Element eines Lösungsintervalls ist (und gleich 0 sonst).
Wir halten noch einige Aussagen über das Wechselspiel zwischen den Werten und Sprungstellen von f fest. Dabei ist d ≥ 1 fest.
Satz (Wertebereichskriterium)
Sei c ≥ 1. Dann sind sind äquivalent:
(a) | b/c ∈ f [ V ]. |
(b) | ad < bc < ad − 1. |
(c) | ad < ℓc − d und ℓc − d + 1 < ad − 1. |
Beweis
Die Aussagen ergeben sich aus b = a + ℓ durch einfache algebraische Umformungen.
Satz (Sprungstellenkriterium)
Sei c ≥ 1. Dann sind äquivalent:
(a) | b/c, b/(c − 1) ∈ f [ V ] . |
(b) | ℓ/(c − d) ist eine Sprungstelle von f in V. |
Beweis
Die Behauptung ergibt sich durch zweifache Anwendung des Wertebereichskriteriums auf c und c − 1 oder direkt aus f(ℓ/(c − d)) = b/c und f [ V ] ⊆ V mit V offen.
Die Grenzen der Lösungsintervalle sind Glieder der drei harmonischen Folgen
a, a/2, a/3, a/4, …
ℓ, ℓ/2, ℓ/3, ℓ/4, …
b, b/2, b/3, b/4, …
Die Glieder der beiden ersten Folgen sind genau die linken Grenzpunkte der Lösungsintervalle in ⋃d ≥ 1 U(d) (wobei Glieder zusammenfallen können). Die rechten Grenzpunkte bilden eine Teilfolge der dritten Folge. Aus dem Satz über die Lösungsintervalle und dem Sprungstellenkriterium ergibt sich, dass die rechten Grenzen genau die Werte von f in ⋃d ≥ 1 V(d) sind. Damit erhalten wir:
Satz (ausgelassene rechte Grenzpunkte)
Sei c ≥ 1. Dann sind äquivalent:
(a) | b/c ist kein rechter Grenzpunkt eines Lösungsintervalls. |
(b) | Es gibt ein d ≥ 1 mit b/c = a/d. |
(c) | ac/b ist ganzzahlig. |
Kurz: b/c ist genau dann eine rechte Grenze, wenn b/c keine linke Grenze ist.
Berechnung der Lösungsintervalle
Um die Lösungsintervalle konkreter zu beschreiben, definieren wir:
Definition (t-Funktion, s-Funktion)
Wir definieren ta,b, sa,b : ℕ* → ℕ* für alle d ≥ 1 durch
sa,b(d) = ⌈bda⌉ − 1, ta,b(d) = ⌈ℓda⌉.
Die Funktionen hängen nur vom Verhältnis a/b ab. Sind a,b fest, so schreiben wir kurz s(d) und t(d). Wir vereinbaren zudem s(0) = −1 und t(d) = 0.
Satz (Eigenschaften der s-t-Funktionen)
Sei d ≥ 1. Dann gilt:
(1) | s(d) = „das größte i ≥ d mit a/d < b/i“, t(d) = „das kleinste i ≥ d mit ℓ/i ≤ a/d“. |
(2) | s(d) = t(d) + d − 1 (speziell s(1) = t(1) = ⌈ℓ/a⌉). |
(3) | s(d + 1) − s(d) ∈ { ⌈b/a⌉ − 1, ⌈b/a⌉ } = { ⌈ℓ/a⌉, ⌈ℓ/a⌉ + 1}. |
(4) | b/(s(d) + 1) = a/d genau dann, wenn bd/a (und ℓd/a) ist ganzzahlig. In diesem Fall ist s(d + 1) − s(d) = ⌈b/a⌉. |
Beweis
zu (1):
Nach Definition von s(d) gilt bd/a − 1 ≤ s(d) < bd/a. Folglich ist
bs(d) + 1 ≤ ad < bs(d).
Dies zeigt die erste Aussage für s(d). Analoges gilt für t(d).
zu (2) und (3):
Diese Aussagen sind klar.
zu (4): Es gilt
b/(s(d) + 1) = b/⌈bd/a⌉ ≤ b/(bd/a) = a/d.
Gleichheit gilt genau dann, wenn ⌈bd/a⌉ = bd/a. Dies zeigt die Äquivalenz in (4). Ist bd/a (oder gleichwertig ℓd/a) ganzzahlig, so ist
s(d + 1) − s(d) = ⌈b(d+1)/a⌉ − ⌈bd/a⌉ = bd/a + ⌈b/a⌉ − bd/a = ⌈b/a⌉.
Nun zeigen wir:
Satz (Struktur der Lösungsintervalle, II)
Sei d ≥ 1, und sei δ = 1ℤ(ℓ(d−1)/a). Dann gilt:
n = t(d), r ∈ { ⌈ℓ/a⌉, ⌈ℓ/a⌉ − 1 },
r = ⌈ℓd/a⌉ − 1 − ⌊ℓ(d − 1)/a⌋ = t(d) − t(d − 1) − δ = s(d) − s(d − 1) − 1 − δ,
U = ] a/b, b/s(d) ] ∪ ] ℓ/(t(d) − 1), b/(s(d) − 1) ] ∪ … ∪ ] ℓ/(t(d) − r), b/(s(d) − r)] .
Beweis
Aus Eigenschaft (1) folgt, dass n = t(d). Weiter gilt: Die Werte der linksstetigen Funktion ⌊ℓ/x⌋ in V bilden die absteigende Zahlenfolge
u0 = ⌈ℓd/a⌉ − 1, u1 = u0 − 1, …, ur = u0 − r, wobei
ur = ⌊ℓ(d − 1)/a⌋ = ⌊ℓd/a − ℓ/a⌋
und r ≥ 0 die Anzahl der Sprungstellen von ⌊ℓ/x⌋ in V ist. Der Wert ⌊ℓd/a⌋ wird genau dann nicht angenommen, wenn ℓd/a ganzzahlig ist. Dies wird durch die Ceiling-Funktion berücksichtigt. Für f erhalten wir die Werte
b/(d + u0) < … < b/(d + ur) ∈ V.
Schließlich ist r = u0 − ur ≤ s(d) − s(d − 1) − 1 ∈ { ⌈ℓ/a⌉ − 1, ⌈ℓ/a⌉ }.
Das Sprungverhalten von s wird beschrieben durch:
Satz (rechte Grenzpunkte der Lösungsintervalle)
Sei d ≥ 1. Dann gilt: Ist ℓ(d − 1)/a nicht ganzzahlig, so sind die folgenden Zahlen die rechten Grenzpunkte von U(d):
| b/s(d), b/(s(d) − 1), …, b/(s(d − 1) + 1) | falls ℓ(d − 1)/a ∉ ℤ |
| b/s(d), b/(s(d) − 1), …, b/(s(d − 1) + 2) | sonst |
Die ersten (und in vielen Fällen einzigen) Lösungsintervalle in U spielen im Folgenden eine Schlüsselrolle. Wir definieren:
Definition (I-Intervalle)
Wir definieren Intervalle Id (= Id,a,b) für alle d ≥ 1 durch
Id = ] a/d, b/sa,b(d) ].
x (gelb), bd + ⌊ℓ/x⌋ (blau), ] a/d, a/(d − 1) [ (rot) für a = 80, b = 100, d = 3
Zusätzlich sind horizontal die Schranken b/(d + ℓ/x) und b/(d + ℓ/x − 1) eingezeichnet.
Es ergibt sich ein Lösungsintervall der Form ]a/d, b/d*].
a = 80, b = 100, d = 9: ein Lösungsintervall, Berührung bei a/(d − 1)
a = 55, b = 100, d = 4 mit ℓ/a ≤ 1:
zwei Lösungsintervalle der Form ] a/d, b/d*], ] ℓ/n, b/(d* − 1) ]
Obiges Diagramm erweitert um d = 3 und d = 5
a = 20, b = 100, d = 4 mit ℓ/a > 1: vier Lösungsintervalle
Nach dieser allgemeinen Analyse betrachten wir nun wieder unsere Binomialkoeffizienten.
Binomialintervalle der Form bm,n
Sei nun I = ] a, b ] von der speziellen Form
I = ] (m − 1)n, mn ] mit natürlichen Zahlen m ≥ 2, n ≥ 1.
Wir setzen m′ = m − 1, sodass
I = ] m′n, mn ].
Mit a = m′n, b = mn gilt
ℓ = n, ℓ/b = 1/m, ℓ/a = 1/m′ ≤ 1, a/b = m/m′.
Sei d ≥ 1 beliebig. Dann gilt r = 0, da
⌊d/m′ − 1/m′⌋ = ⌈d/m′⌉ − 1.
Also existiert genau ein Lösungsintervall in V(d), nämlich
Id = Id,(m−1)n,mn = ] a/d, b/s(d) ], wobei
s(d) = ⌈bd/a⌉ − 1 = ⌈md/m′⌉ − 1.
Auch die s-Funktion ist für diesen Intervall-Typ besonders einfach:
Satz (Eigenschaften der s-Funktion)
Sei d ≥ 1. Dann gilt:
(#) s(d + 1) − s(d) = 1 + ⌈md/m′ + 1/m′⌉ − ⌈md/m′⌉ ∈ { 1, 2 }.
Weiter sind äquivalent:
(1) | s(d + 1) − s(d) = 2. |
(2) | md/m′ ist ganzzahlig, d. h. m′|d. |
(3) | m|(s(d) + 1). |
(4) | b/(s(d) + 1) = a/d. |
Beweis
Die Aussage (#) und damit die Äquivalenz der Aussagen (1) und (2) ergibt sich aus
⌈m(d + 1)/m′⌉ = ⌈md/m′ + m/m′⌉ = ⌈md/m′ + 1 + 1/m′⌉.
Aus s(d) + 1 = ⌈md/m′⌉ und ggT(m′, m) = 1 folgt die Äquivalenz von (2) und (3). Schließlich ist m′|d äquivalent zu
s(d) + 1 = ⌈mdm′⌉ = mdm′.
Dies ist wiederum äquivalent zu
bs(d) + 1 = m′bmd = ad.
Aus dem Satz folgt, dass die s-Funktion genau dann einen Wert c = s(d) + 1 überspringt, wenn c ein Vielfaches von m ist. Wir erhalten also:
Satz (Charakterisierung der rechten Grenzpunkte)
Sei c ≥ 1. Dann ist mn/c genau dann ein rechter Grenzpunkt eines Lösungsintervalls, wenn c kein Vielfaches von m ist.
Natürlich können wir auch unseren allgemeinen Satz über die ausgelassenen rechten Grenzpunkte bemühen. Denn nach diesem Satz gilt ac/b = m′c/m ∈ ℤ wegen (m′, m) = 1 genau dann, wenn c ein Vielfaches von m ist.
Die rechten Grenzpunkte der Lösungsintervalle sind also genau die Zahlen
bs(1), bs(2), bs(3), …
Die s-Funktion hängt nur von m ab. Sie wächst alle m − 1 Schritte um 2 und sonst um 1.
Beispiel
Für m = 5 ist (s(d))d ≥ 1 die Folge
1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, …
Genau die Vielfachen der 5 werden ausgelassen. Die Differenzenfolge (s(d) − d)d ≥ 1 ist
0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, …
Sie besteht aus aufsteigenden Viererblöcken der natürlichen Zahlen.
Wir haben gezeigt:
Satz (Indikatorfunktion der I-Intervalle)
Sei I = ⋃d ≥ 1 Id = ⋃d ≥ 1 ] a/d, b/s(d) ]. Dann gilt
⌊mn/x⌋ − ⌊m′n/x⌋ − ⌊n/x⌋ = indI(x) für alle x ∈ ℝ.
Konkret berechnen sich für alle d ≥ 1 die Vielfachen von x ∈ ] a/d, a/(d − 1) ] in den Intervallen ] 0, n ] und ] a, b ] wie folgt (mit s(d) − d = u1 = ⌈d/m′⌉ − 1):
Fall | Vielfache von x in ] 0, n ] | Vielfache von x in ] a, b ] |
x ∈ Id | x, 2x, …, (s(d) − d)x | dx, …, s(d)x |
x ∉ Id | x, 2x, …, (s(d) − d)x | dx, …, (s(d) − 1)x |
Für die Binomialkoeffizienten erhalten wir:
Korollar (Primzahlbänder von bm,n)
In obiger Situation sei p prim. Dann gilt
exp(bm,n) = |{ e ≥ 1 | pe ∈ I }|.
Ist p2 > b, so gilt:
(a) | Ist p ∈ I, so kommt p in bm,n genau einmal vor. |
(b) | Ist p ∉ I, so kommt p in bm, n nicht vor. |
Beweis
Es gilt
exp(bm,n) = exp(b!) − exp(a!) − exp(n!).
Damit folgt die Behauptung aus dem Satz von Legendre.
Die Lösungsintervalle für m = 5 und n = 720. Sie entsprechen den Primzahlbändern des Binomialkoeffizienten b5, 720. Die Bänder ab 600 hatten wir früher bereits bestimmt.
Bemerkung: Ein direkter Zugang
Die I-Intervalle und die Eigenschaften der s-Funktion lassen sich für unseren Spezialfall auch durch folgende Überlegung gewinnen. Als Gleichung notiert lautet die rechte Seite von (+):
x = b/(d + ⌊ℓ/x⌋).
Eine Lösung hat also die Form x = b/d* mit einer natürlichen Zahl d* ≥ d. Es gilt dann b/d* = b/(d + ⌊ℓ/(b/d*)⌋), sodass d* = d + ⌊d*ℓ/b⌋. Im Spezialfall I = ] (m − 1)n, mn ] erhalten wir
d* = d + ⌊d*/m⌋.
Nun können wir ablesen:
| d* = d | für d = 1, …, m − 1 |
| d* = d + 1 | für d = m, …, 2(m − 1) |
| d* = d + 2 | für d = 2m − 1, …, 3(m − 1) |
und allgemein
d* = d + ⌈dm − 1⌉ − 1 = ⌈d(m − 1) + dm − 1⌉ − 1 = ⌈mdm − 1⌉ − 1.
Anhang: Ein ausführliches Beispiel für bm,n
Wir betrachten noch einmal unser Eingangsbeispiel b5,720. Sei also m = 5 und n = 720. Die ersten vier I-Intervalle berechnen sich zu
] 2880, 3600 ], ] 1440, 1800 ], ] 960, 1200 ], ] 720, 900 ]
Sie entsprechen den oberen Primzahlbändern von b5,720. Die weiteren Intervalle ] a/d, b/s(d) ] geben wir der Übersichtlichkeit halber mit abgerundeten Intervallgrenzen an. Wir erhalten so
] 576, 600 ], ] 480, 514 ], ] 411, 450 ], ] 360, 400 ], ] 320, 327 ], ] 288, 300 ],
] 261, 276 ], ] 240, 257 ], ] 221, 225 ], ] 205, 211 ], ] 192, 200 ], ] 180, 189 ],
] 169, 171 ], ] 160, 163 ], ] 151, 156 ], ] 144, 150 ], ] 137, 138 ], ] 130, 133 ],
] 125, 128 ], ] 120, 124 ], ] 115, 116 ], ] 110, 112 ], ] 106, 109 ], ] 102, 105 ],
] 99, 100 ], ] 96, 97 ], ] 92, 94 ], ] 90, 92 ], ] 87, 87 ], ] 84, 85 ], ] 82, 83 ], ] 80, 81 ],
] 77, 78 ], ] 75, 76 ], ] 73, 75 ], ] 72, 73 ], ] 70, 70 ], ] 68, 69 ], ] 66, 67 ], ] 65, 66 ],
] 64, 64 ], ] 62, 63 ], ] 61, 62 ], ] 60, 61 ], ] 58, 59 ], …
Die Zahl b hat im Intervall 2 bis 720 die folgenden absteigend geordneten Primfaktoren (vgl. das Spiraldiagramm am Beginn des Essays):
599, 593, 587, 577, 509, 503, 499, 491, 487,
449, 443, 439, 433, 431, 421, 419, 397, 389, 383, 379, 373, 367,
293, 271, 269, 263, 257, 251, 241, 223, 211, 199, 197, 193,
181, 163, 149, 131, 127, 109, 107, 103, 97, 83, 73, 67, 61,
59, 43, 41, 37, 31, 29, 19, 17, 11, 7, 5, 3, 2.
Das gerundete I-Intervall ] 320, 327 ] ist das erste Intervall, das keine Primzahlen enthält, sodass es sich in der Primfaktorzerlegung von b5,720 nicht widerspiegelt. Manche I-Intervalle enthalten gar keine natürliche Zahl.
Die Primzahlen, die in b5,720 mehrfach vorkommen, lauten zusammen mit ihren Exponenten:
24, 34, 52, 72, 112, 192, 292, 312, 592.
Für 59 gilt zum Beispiel
59 ∈ ] 58, 59 ], 592 = 3481 ∈ ] 2880, 3600 ].
Ebenso sind die Zahlen 7 und 72 = 49 in den Intervallen enthalten, nicht aber 73 = 343 und 74 = 2401.