p-adische Bewertung (Summenformel zu beweisen)

01.12.2010, 15:44

Josef S

p-adische Bewertung (Summenformel zu beweisen)

Hallo Community,

das ist mein erste Frage hier in diesem Board, weshalb ich mal hoffe, dass ich die FAQs richtig gelesen habe...

Da ich wahrscheinlich hier des Öfteren vorbeischauen und schreiben werde, stelle ich mich kurz vor:
Ich heiße Josef Sniatecki und besuche gerade die 12. Klasse eines Gymnasiums, um in der 13. das allgemeine Abitur zu erreichen. Da ich interessiert Mathematik betreibe, beschäftige ich mich auch mit dem Stoff aus Hochschulen.

Mein Problem ist ein zahlentheoretisches Problem. Zuerst die Aufgabe:

Man zeige, dass für alle $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ folgendes gilt:
$\begin{eqnarray*} v_{p}(n!)=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor \end{eqnarray*}$

Hierbei ist $\begin{eqnarray*} \left\lfloor x\right\rfloor \end{eqnarray*}$ die gaußsche Abrundungsfunktion. $\begin{eqnarray*} v_{p}(x) \end{eqnarray*}$ mit $\begin{eqnarray*} x\in\mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} p\in\mathbb P \end{eqnarray*}$ steht für den größten natürlichen Exponent $\begin{eqnarray*} k \end{eqnarray*}$ damit $\begin{eqnarray*} p^{k}\mid x \end{eqnarray*}$ gilt (also $\begin{eqnarray*} p^{k} \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} x \end{eqnarray*}$ ist).

Nun, das einzige was ich bisher herausgefunden habe ist, dass die Summe stets endlich sein muss, da $\begin{eqnarray*} \left\lfloor \frac{n}{p^{k}}\right\rfloor \end{eqnarray*}$ für $\begin{eqnarray*} p^{k}>n \end{eqnarray*}$ immer gleich null ist.

Jetzt brauche ich eure Ratschläge. Vielleicht kennt ja jemand diese Aufgabe aus seinem Studium.
Ich wäre auf jeden Fall sehr über hilfreiche Antworten dankbar, da ich gerne Hausarbeiten über interessante mathematische Themen schreibe und diese gerne vollständig hätte. In meiner aktuellen Hausarbeit geht es um elementare Zahlentheorie und am Ende habe ich ein Kapitel mit Aufgaben und Lösungen angehängt, worunter auch diese Aufgabe aufgeführt werden soll.

Also, vielen Dank im Voraus.
Gruß Josef

01.12.2010, 20:15

Josef S

Auf diesen Beitrag antworten »

Hm... habe ich irgendwas falsch gemacht, weshalb sich niemand zu diesem Beitrag meldet?

Auf jeden Fall habe ich mir die letzten Stunden überlegt, ob man was mit der Information anfangen kann, dass die p-adische Bewertung vollständig additiv ist, wodurch folgendes gelten muss:
$\begin{eqnarray*} v_{p}(n!)=v_{p}(1)+\ldots+v_{p}(n)=\sum_{i=1}^{n}v_{p}(i)=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor \end{eqnarray*}$

Aber irgendwie hilft mir das nicht weiter. Würde mich weiterhin auf Antworten freuen.

Gruß Josef

01.12.2010, 20:34

jester.

Auf diesen Beitrag antworten »

Hallo Josef,

du hast nichts falschgemacht und deine Vorstellung / Begrüßung war sehr freundlich. Also erst mal Willkommen

Bei Gelegenheit kannst du mal, falls du es nicht schon getan hast, unser Prinzip lesen: Prinzip "Mathe online verstehen!"

Alle Helfer hier im Forum sind freiwillig hier und "opfern" ihre Freizeit, das heißt du solltest einfach ein bisschen Geduld mitbringen, wenn du eine Frage stellst.
Vielleicht hat auch der Titel potentielle Helfer abgeschreckt, denn $\begin{eqnarray*} \nu_p \end{eqnarray*}$ als "p-adische Bewertung" kenne ich mit dieser Bezeichnung nur aus der (möglicherweise etwas fortgeschrittenen) Algebra - in der Zahlentheorie-Vorlesung, die ich letztes Semester besucht habe, hatte diese Funktion gar keinen speziellen Namen glaube ich. Aber es ist natürlich de facto die p-adische Bewertung. Augenzwinkern

Wie dem auch sei, hier handelt es sich eigentlich nur um ein kombinatorisches Problem. Wir betrachten die Teilbarkeit von $\begin{eqnarray*} n! \end{eqnarray*}$ durch die Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ . Dazu überlegen wir uns, wie oft der Primfaktor $\begin{eqnarray*} p \end{eqnarray*}$ in den Zahlen von $\begin{eqnarray*} 1 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ , die ja ihrerseits allesamt Faktoren von $\begin{eqnarray*} n! \end{eqnarray*}$ sind, vorkommt.
Zu diesen Zahlen zählen $\begin{eqnarray*} p, ~, 2p, ~ 3p ,..., \left\lfloor \frac n p \right\rfloor \end{eqnarray*}$ , die jeweils 1 zum gesuchten $\begin{eqnarray*} \nu_p(n!) \end{eqnarray*}$ beitragen.
Es gibt aber auch Zahlen im Produkt, die noch durch höhere Potenzen teilbar sind, wie z.B. $\begin{eqnarray*} p^2, ~ 2p^2, ... \end{eqnarray*}$ und jedes weitere Wort wird die Aufgabe wohl vollständig lösen.

01.12.2010, 21:08

Josef S

Auf diesen Beitrag antworten »

Vielen Dank für deinen guten Ansatz, jester. Ich muss nur noch ein bisschen überlegen, wie ich meinen Beweis formulieren kann, damit er schlüssig ist. Auf jeden Fall werde ich für weitere Antworten genug Geduld haben Augenzwinkern

Weil ich Beweise so mag, schreibe ich gerne noch mal hin, wie ich darauf gekommen bin, dass die Bewertung vollständig additiv ist:
$\begin{eqnarray*} a=\prod_{p\in\mathbb{P}}p^{v_{p}(a)}\\ b=\prod_{p\in\mathbb{P}}p^{v_{p}(b)} a\cdot b=\left(\prod_{p\in\mathbb{P}}p^{v_{p}(a)}\right)\cdot\left(\prod_{p\in\mathbb{P}}p^{v_{p}(b)}\right)=\prod_{p\in\mathbb{P}}p^{v_{p}(a)}\cdot p^{v_{p}(b)}=\prod_{p\in\mathbb{P}}p^{\overset{v_{p}(a\cdot b)}{\overbrace{v_{p}(a)+v_{p}(b)}}} \end{eqnarray*}$

So gilt für Produkte aus n Faktoren:
$\begin{eqnarray*} a_{1}\cdot\ldots\cdot a_{n}= \prod_{k=1}^{n}a_{k}=\prod_{p\in\mathbb{P}}p^{\sum_{k=1}^{n}v_{p}(a_{k})}\\ \Longrightarrow v_{p}\left(\prod_{k=1}^{n}a_{k}\right)=\sum_{k=1}^{n}v_{p}(a_{k}) \end{eqnarray*}$

Analog gilt für n!:
$\begin{eqnarray*} v_{p}(n!)=v_{p}(1)+\ldots+v_{p}(n)=\sum_{i=1}^{n}v_{p}(i) \end{eqnarray*}$

Ich melde mich, sobald ich einen Beweis fertig geschrieben habe. Nochmal ein Danke von mir. smile

Gruß Josef

01.12.2010, 22:33

Josef S

Auf diesen Beitrag antworten »

So, wie findet ihr folgende Lösung? Irgendwie habe ich das Gefühl, dass sie nicht allzu besonders schön ist.

Aufgabe:
Man zeige, dass für alle $\begin{eqnarray*} n\in\mathbb{N} \end{eqnarray*}$ und $\begin{eqnarray*} p\in\mathbb{P} \end{eqnarray*}$ folgendes
gilt:

$\begin{eqnarray*} v_{p}(n!)=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor \end{eqnarray*}$

Dabei ist $\begin{eqnarray*} \left\lfloor x\right\rfloor \end{eqnarray*}$ für alle $\begin{eqnarray*} x\in\mathbb{R}_{+} \end{eqnarray*}$ die größte ganze Zahl $\begin{eqnarray*} \leq x \end{eqnarray*}$ .

Lösung:

Fest steht, dass die Summe endlich ist, da $\begin{eqnarray*} \frac{n}{p^{k}} \end{eqnarray*}$ ab einem
bestimmten $\begin{eqnarray*} k_{i} \end{eqnarray*}$ kleiner als $\begin{eqnarray*} 1 \end{eqnarray*}$ ist, wodurch die Abrundungsfunktion
für alle weiteren $\begin{eqnarray*} k>k_{i} \end{eqnarray*}$ den Wert $\begin{eqnarray*} 0 \end{eqnarray*}$ zurückgibt. Nun sind alle
Primzahlen $\begin{eqnarray*} \leq n \end{eqnarray*}$ Teiler von $\begin{eqnarray*} n! \end{eqnarray*}$ , da sie stets im Produkt $\begin{eqnarray*} 1\cdot\ldots\cdot n \end{eqnarray*}$
enthalten sind.

Da die p-adische Bewertung vollständig additiv ist, können wir auch
folgende Eigenschaft feststellen:
$\begin{eqnarray*} v_{p}(n!)=v_{p}(1)+\ldots+v_{p}(n)=\sum_{i=1}^{n}v_{p}(i)=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor \end{eqnarray*}$

Nun ist der Ausdruck $\begin{eqnarray*} \lfloor\frac{n}{p}\rfloor\cdot p \end{eqnarray*}$ für alle
$\begin{eqnarray*} p \end{eqnarray*}$ immer $\begin{eqnarray*} \leq n \end{eqnarray*}$ , woraus folgt, dass $\begin{eqnarray*} x\cdot p \end{eqnarray*}$ mit $\begin{eqnarray*} 0<x\leq\lfloor\frac{n}{p}\rfloor \end{eqnarray*}$ stets Teiler von $\begin{eqnarray*} n! \end{eqnarray*}$ sein muss, weil $\begin{eqnarray*} x\cdot p \end{eqnarray*}$ kleiner $\begin{eqnarray*} n \end{eqnarray*}$ ist. Da es $\begin{eqnarray*} \lfloor\frac{n}{p}\rfloor \end{eqnarray*}$ verschiedene natürliche $\begin{eqnarray*} x \end{eqnarray*}$ gibt, die die Bedingung $\begin{eqnarray*} 0<x\leq\lfloor\frac{n}{p}\rfloor \end{eqnarray*}$ erfüllen, muss auf jeden Fall $\begin{eqnarray*} v_{p}(n!)\geq\lfloor\frac{n}{p}\rfloor \end{eqnarray*}$ gelten. Denn alle Produkte $\begin{eqnarray*} 1\cdot p,\ldots,\lfloor\frac{n}{p}\rfloor\cdot p \end{eqnarray*}$ sind Teiler von $\begin{eqnarray*} n! \end{eqnarray*}$ bzw. Faktoren von $\begin{eqnarray*} n! \end{eqnarray*}$ , woraus folgt, dass $\begin{eqnarray*} p \end{eqnarray*}$ als Primfaktor mindestens $\begin{eqnarray*} x \end{eqnarray*}$ Mal in $\begin{eqnarray*} n! \end{eqnarray*}$ vorkommt. Für jeden Teiler $\begin{eqnarray*} x\cdot p \end{eqnarray*}$ gilt also $\begin{eqnarray*} v_{p}(x\cdot p)\geq1 \end{eqnarray*}$ . Nun ist aber noch zu beachten, dass für manche Teiler $\begin{eqnarray*} v_{p}(x\cdot p)\geq2 \end{eqnarray*}$ ,
$\begin{eqnarray*} v_{p}(x\cdot p)\geq3 \end{eqnarray*}$ usw. gilt. D.h. man muss alle Teiler von $\begin{eqnarray*} n! \end{eqnarray*}$
mit einrechnen, die $\begin{eqnarray*} p \end{eqnarray*}$ mehrfach als Primfaktor besitzen. Addieren wir die errechneten Summen, so ergibt sich schließlich:
$\begin{eqnarray*} v_{p}(n!)=\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^{2}}\rfloor+\lfloor\frac{n}{p^{3}}\rfloor+\ldots=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor \end{eqnarray*}$

02.12.2010, 20:01

jester.

Auf diesen Beitrag antworten »

Zitat:

Original von Josef S
So, wie findet ihr folgende Lösung? Irgendwie habe ich das Gefühl, dass sie nicht allzu besonders schön ist.

Es ist die Lösung, auf die ich abzielte. Das heißt man "zählt". Einen eleganteren Beweis kenne ich nicht - aber ich habe auch bisher nicht versuch mir einen solchen zu überlegen.

Zitat:

Lösung:

Fest steht, dass die Summe endlich ist, da $\begin{eqnarray*} \frac{n}{p^{k}} \end{eqnarray*}$ ab einem
bestimmten $\begin{eqnarray*} k_{i} \end{eqnarray*}$ kleiner als $\begin{eqnarray*} 1 \end{eqnarray*}$ ist, wodurch die Abrundungsfunktion
für alle weiteren $\begin{eqnarray*} k>k_{i} \end{eqnarray*}$ den Wert $\begin{eqnarray*} 0 \end{eqnarray*}$ zurückgibt.

Das ist schonmal gut und wichtig, damit man sich, zum Beispiel, keine Gedanken über Konvergenz machen muss.

Zitat:

Nun sind alle
Primzahlen $\begin{eqnarray*} \leq n \end{eqnarray*}$ Teiler von $\begin{eqnarray*} n! \end{eqnarray*}$ , da sie stets im Produkt $\begin{eqnarray*} 1\cdot\ldots\cdot n \end{eqnarray*}$
enthalten sind.

Da die p-adische Bewertung vollständig additiv ist, können wir auch
folgende Eigenschaft feststellen:
$\begin{eqnarray*} v_{p}(n!)=v_{p}(1)+\ldots+v_{p}(n)=\sum_{i=1}^{n}v_{p}(i)=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor \end{eqnarray*}$

Dass alle Primzahlen $\begin{eqnarray*} \leq n \end{eqnarray*}$ Teiler sind, ist hier eigentlich gar nicht wichtig. Wir betrachten ja in $\begin{eqnarray*} v_p \end{eqnarray*}$ jeweils nur eine feste Primzahl, die ja noch nichtmal ein Teiler sein, $\begin{eqnarray*} v_p \end{eqnarray*}$ kann ja auch $\begin{eqnarray*} 0 \end{eqnarray*}$ als Wert ausgeben.

Zitat:

Nun ist der Ausdruck $\begin{eqnarray*} \lfloor\frac{n}{p}\rfloor\cdot p \end{eqnarray*}$ für alle
$\begin{eqnarray*} p \end{eqnarray*}$ immer $\begin{eqnarray*} \leq n \end{eqnarray*}$ , woraus folgt, dass $\begin{eqnarray*} x\cdot p \end{eqnarray*}$ mit $\begin{eqnarray*} 0<x\leq\lfloor\frac{n}{p}\rfloor \end{eqnarray*}$ stets Teiler von $\begin{eqnarray*} n! \end{eqnarray*}$ sein muss, weil $\begin{eqnarray*} x\cdot p \end{eqnarray*}$ kleiner $\begin{eqnarray*} n \end{eqnarray*}$ ist. Da es $\begin{eqnarray*} \lfloor\frac{n}{p}\rfloor \end{eqnarray*}$ verschiedene natürliche $\begin{eqnarray*} x \end{eqnarray*}$ gibt, die die Bedingung $\begin{eqnarray*} 0<x\leq\lfloor\frac{n}{p}\rfloor \end{eqnarray*}$ erfüllen, muss auf jeden Fall $\begin{eqnarray*} v_{p}(n!)\geq\lfloor\frac{n}{p}\rfloor \end{eqnarray*}$ gelten. Denn alle Produkte $\begin{eqnarray*} 1\cdot p,\ldots,\lfloor\frac{n}{p}\rfloor\cdot p \end{eqnarray*}$ sind Teiler von $\begin{eqnarray*} n! \end{eqnarray*}$ bzw. Faktoren von $\begin{eqnarray*} n! \end{eqnarray*}$ , woraus folgt, dass $\begin{eqnarray*} p \end{eqnarray*}$ als Primfaktor mindestens $\begin{eqnarray*} x \end{eqnarray*}$ Mal in $\begin{eqnarray*} n! \end{eqnarray*}$ vorkommt.

Hier ist die Bezeichnung ein bisschen ungeschickt, du lässt $\begin{eqnarray*} x \end{eqnarray*}$ ja zuerst im Text zwischen 0 und $\begin{eqnarray*} \lfloor n/p\rfloor \end{eqnarray*}$ "laufen", sagst dann aber der Primfaktor komme "x mal" vor, aber x hat keinen festen Wert.

Besser ist also: Jedes $\begin{eqnarray*} xp \end{eqnarray*}$ mit $\begin{eqnarray*} 1\leq x \leq \lfloor n/p \rfloor \end{eqnarray*}$ trägt 1 zu $\begin{eqnarray*} v_p(n!) \end{eqnarray*}$ bei.

Zitat:

Für jeden Teiler $\begin{eqnarray*} x\cdot p \end{eqnarray*}$ gilt also $\begin{eqnarray*} v_{p}(x\cdot p)\geq1 \end{eqnarray*}$ . Nun ist aber noch zu beachten, dass für manche Teiler $\begin{eqnarray*} v_{p}(x\cdot p)\geq2 \end{eqnarray*}$ ,
$\begin{eqnarray*} v_{p}(x\cdot p)\geq3 \end{eqnarray*}$ usw. gilt. D.h. man muss alle Teiler von $\begin{eqnarray*} n! \end{eqnarray*}$
mit einrechnen, die $\begin{eqnarray*} p \end{eqnarray*}$ mehrfach als Primfaktor besitzen. Addieren wir die errechneten Summen, so ergibt sich schließlich:
$\begin{eqnarray*} v_{p}(n!)=\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^{2}}\rfloor+\lfloor\frac{n}{p^{3}}\rfloor+\ldots=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor \end{eqnarray*}$

Das kann man, so wie ich in meinem ersten Beitrag geschrieben habe, etwas differenzierter darstellen. $\begin{eqnarray*} p^2, 2p^2,...,\lfloor n/p \rfloor p^2 \end{eqnarray*}$ tragen ebenfalls je 1 zu $\begin{eqnarray*} v_p(n!) \end{eqnarray*}$ bei.
Gleiches gilt dann für $\begin{eqnarray*} p^3,2p^3,...,\lfloor n/p^3 \rfloor p^3 \end{eqnarray*}$ , sodass man auf die behauptete Summendarstellung kommt.

Insgesamt möchte ich dir aber sagen, dass du das ganze schon sehr ordentlich und nachvollziehbar aufgeschrieben hast. Kompliment.

02.12.2010, 20:18

René Gruber

Auf diesen Beitrag antworten »

Inhaltlich habe ich keine wirkliche Alternative, aber beweistechnisch könnte man die Sache auch mit einer Induktion $\begin{eqnarray*} (<n)\to n \end{eqnarray*}$ aufziehen:

Dazu betrachtet man die Zerlegung $\begin{eqnarray*} n = pn'+r \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq r\leq p-1 \end{eqnarray*}$ und nutzt dazu die dann geltende (und allerdings ebenfalls noch zu begründende) Eigenschaft

$\begin{eqnarray*} v_p(n!) = n' +v_p(n'!) \end{eqnarray*}$ .

Im Induktionsschritt greift man beim Beweis für $\begin{eqnarray*} n \end{eqnarray*}$ dann auf die Induktionsvoraussetzung für $\begin{eqnarray*} n' \end{eqnarray*}$ zurück.

Aber wie gesagt: Inhaltlich passiert eigentlich auch nichts anderes. Augenzwinkern

Neue Frage »

Antworten »

p-adische Bewertung (Summenformel zu beweisen)

Verwandte Themen