Ordnung Fakultät mit modulo

03.04.2012, 17:34

mattix

Ordnung Fakultät mit modulo

Meine Frage:
Hi,
meine Aufgabe ist, zu beweisen, dass
$\begin{eqnarray*} ord_{p} n! = \left[ \frac{n} {p} \right]+\left[ \frac{n}{p^{2}} \right]+\left[ \frac{n}{p^{3}} \right]+.... \end{eqnarray*}$ gilt.
( $\begin{eqnarray*} \left[ ... \right] \end{eqnarray*}$ soll auf ganze Zahl abrunden bedeuten.)

Meine Ideen:
Ich wollte es mit Induktion über n zeigen, aber bin dann schon auf das Problem gestoßen, dass es für n=1 ja gar nicht stimmt. 1 hat ja immer die Ordnung 1, mit der Formel kommt doch aber 0 raus!?!

03.04.2012, 17:39

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von mattix
1 hat ja immer die Ordnung 1

Vielleicht bist du dir nicht ganz im klaren, was dieses $\begin{eqnarray*} \operatorname{ord}_p(m) \end{eqnarray*}$ bedeutet:

Es sieht ganz danach aus, als wäre damit der Exponent der Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ in der Primfaktorzerlegung von $\begin{eqnarray*} m \end{eqnarray*}$ gemeint. Und in dem Sinne ist dann durchaus $\begin{eqnarray*} \operatorname{ord}_p(1)=0 \end{eqnarray*}$ , und zwar für jede Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ .

04.04.2012, 18:35

mattix

Auf diesen Beitrag antworten »

Oh ja, du hast Recht. Ich hab die Definition falsch verstanden.
Sieht so aus, als wäre Induktion aber nicht der richtige Ansatz,oder?

04.04.2012, 18:50

HAL 9000

Auf diesen Beitrag antworten »

Ich würde es eher direkt beweisen: Betrachte dazu für festes $\begin{eqnarray*} p \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ die Hilfsmengen

$\begin{eqnarray*} A_k = \left\{ m\in \{1,2,\ldots,n\} \Bigm| m \;\mbox{ist teilbar durch}\; p^k \right\} \end{eqnarray*}$

Jetzt musst du dir im wesentlichen nur noch überlegen, warum

$\begin{eqnarray*} \operatorname{ord}_p(n!) = \sum_{k=1}^{\infty} |A_k| \end{eqnarray*}$

gilt.

05.04.2012, 09:52

mattix

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \operatorname{ord}_p(n!) = \sum_{k=1}^{\infty} |A_k| \end{eqnarray*}$ gilt doch wegen der Formel $\begin{eqnarray*} ord_{p} (ab)=ord_{p}a + ord_{p}b\\ \end{eqnarray*}$ ,
da $\begin{eqnarray*} \\ n!=n (n-1)(n-2)...1 \end{eqnarray*}$
Jetzt muss ich doch noch zeigen, dass $\begin{eqnarray*} |A_{k}| = \left[ \frac {n}{p^{k}} \right] \end{eqnarray*}$ , oder?

Neue Frage »

Antworten »

Ordnung Fakultät mit modulo

Verwandte Themen