3. Die Größe der Teilbarkeitsrelation

Dass die harmonische Reihe wie der Logarithmus wächst, hat eine bemerkenswerte Konsequenz für die Teilbarkeitsrelation. Wir definieren hierzu:

 Wir betrachten noch einmal unser Diagramm für Div₃₀.

Die Spalten eines Diagramms für Div_n haben genau

n,  ⌊n/2⌋,  ⌊n/3⌋,  …,  1

Einträge, wobei wieder

⌊x⌋  =  „das größte n  ∈  ℤ mit n ≤ x“  für alle x  ∈  ℝ

die Floor-Funktion ist.

 Sei nun n ≥ 1 beliebig. Dann gilt

div(n)  =  n  +  ⌊n/2⌋  +  ⌊n/3⌋  +  …  +  1  =  ∑_{1 ≤ k ≤ n} ⌊n/k⌋.

Lassen wir die Abrundungsfunktion auf der rechten Seite weg, so erhalten wir dort den Wert n s_n mit der n-ten Partialsumme

s_n  =  ∑_k ≤ n ¹_k

der harmonischen Reihe. Um den Fehler dieser Ersetzung abzuschätzen, beobachten wir, dass 0 ≤ x − ⌊x⌋ < 1 für alle x. Damit ist

|div(n)  −  n s_n|  =  |∑_{1 ≤ k ≤ n} ( ⌊n/k⌋ − n/k)|  ≤  n.

Mit |s_n − log(n)| ≤ 1 folgt

|div(n)  −  n log(n)|  ≤  |div(n) − n s_n| + |n s_n − n log(n)|  ≤  n + n  =  2n.

Damit gilt

|^div(n)_{n log(n)}  −  1|  =  |^{div(n) − n log(n)}_{n log(n)}|  ≤  ²_log(n)  für alle n ≥ 2.

Der Term auf der rechten Seite konvergiert gegen 0, wenn n gegen unendlich strebt. Damit haben wir gezeigt:

 Die Anzahl der Punkte unserer Teilbarkeitsdiagramme ist also ungefähr (im Sinne des Grenzwerts des Satzes) gleich n log(n). Die folgenden Tabelle gibt einen Eindruck über die Werte der beiden Funktionen und ihren Quotienten.

 Mit Wachstumsvergleichen der Form

lim_{n → ∞} ^f (n)_g(n)  =  1,

der sogenannten asymptotischen Gleichheit zweier Funktionen f und g, werden wir uns bei der Diskussion des Primzahlsatzes noch genauer beschäftigen.