Binomialkoeffizient, Teilbarkeit, Primzahl, Logarithmus

17.05.2010, 19:20

daN-R-G

Binomialkoeffizient, Teilbarkeit, Primzahl, Logarithmus

Huhu.
Der Titel ist zwar etwas komisch, aber wusste nicht genau, wie ich ihn sonst beschreiben soll Augenzwinkern

Sitze gerade an einer Aufgabe, bei der mir noch die passende Idee für die Ungleichung fehlt.

Behauptung: Für $\begin{eqnarray*} n \geq m \in \mathbb{N}, p \in \mathbb{P} \end{eqnarray*}$ gilt: $\begin{eqnarray*} p^k | \begin{pmatrix} n \\ m \end{pmatrix} \Rightarrow k \cdot \log p \leq \log n \end{eqnarray*}$

Okay. Also $\begin{eqnarray*} p^k \end{eqnarray*}$ logarithmiert ergibt ja schließlich $\begin{eqnarray*} k \cdot \log p \end{eqnarray*}$ . Dann gilt ja weiter, dass $\begin{eqnarray*} p^k \leq \begin{pmatrix} n \\ m \end{pmatrix} \end{eqnarray*}$ sein muss, denn schließtlich gilt ja $\begin{eqnarray*} p^k | \begin{pmatrix} n \\ m \end{pmatrix} \end{eqnarray*}$
also $\begin{eqnarray*} p^k \cdot d = \frac{n!}{m!(n-m)!} \textbf{für ein } d \in \mathbb{Z} \end{eqnarray*}$ . Weiß leider noch nicht genau, wie mir das nun hier weiterhilft.

Hätte vll. jemand nen Tipp für mich?

17.05.2010, 19:48

tmo

Auf diesen Beitrag antworten »

Betrachte vielleicht erstmal den Fall k=1, das lässt sich dann leicht auf beliebige k übertragen.

Zu zeigen ist dann $\begin{eqnarray*} p|\binom{n}{m} \Rightarrow p \leq n \end{eqnarray*}$ .

Wenn nun p>n gilt, so gilt $\begin{eqnarray*} p \not | ~ s \forall s \leq n \end{eqnarray*}$ , also wegen p prim: $\begin{eqnarray*} p \not | ~ n! \end{eqnarray*}$ . Also sowieso: $\begin{eqnarray*} p \not | ~ \frac{n!}{m!(n-m)!} \end{eqnarray*}$ .

Ganz so einfach ist es für beliebige k nicht. Aber es lässt sich zeigen:

Wenn $\begin{eqnarray*} p^k > n \end{eqnarray*}$ und $\begin{eqnarray*} p^u \leq n \end{eqnarray*}$ für ein $\begin{eqnarray*} u < k \end{eqnarray*}$ , dann kommt bereits $\begin{eqnarray*} p^{u-1} \end{eqnarray*}$ im Nenner $\begin{eqnarray*} m!(n-m)! \end{eqnarray*}$ vor, wird also weggekürzt und alle kleineren Potenzen von p dann natürlich auch. Also kommt p im Binomialkoeffizient nur mit der Potenz u vor.

17.05.2010, 20:10

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Wenn $\begin{eqnarray*} p^k > n \end{eqnarray*}$ und $\begin{eqnarray*} p^u \leq n \end{eqnarray*}$ für ein $\begin{eqnarray*} u < k \end{eqnarray*}$ , dann kommt bereits $\begin{eqnarray*} p^{u-1} \end{eqnarray*}$ im Nenner $\begin{eqnarray*} m!(n-m)! \end{eqnarray*}$ vor, wird also weggekürzt und alle kleineren Potenzen von p dann natürlich auch. Also kommt p im Binomialkoeffizient nur mit der Potenz u vor.

Ich muss gestehen, diese Argumentation verstehe ich nicht: $\begin{eqnarray*} p \end{eqnarray*}$ kommt schließlich in weit größeren Potenzen in diesen Fakultäten vor, sowohl in Zähler als auch Nenner. verwirrt

Mir selbst fällt bisher leider nur etwas erheblich komplizierteres auf Basis von

Exponent der 2 in der Primfaktorzerlegung von 10000!

ein.

17.05.2010, 20:48

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Mir selbst fällt bisher leider nur etwas erheblich komplizierteres auf Basis von

Exponent der 2 in der Primfaktorzerlegung von 10000!
ein.

Für mich gilt Gleiches...

17.05.2010, 21:43

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Ich muss gestehen, diese Argumentation verstehe ich nicht: $\begin{eqnarray*} p \end{eqnarray*}$ kommt schließlich in weit größeren Potenzen in diesen Fakultäten vor, sowohl in Zähler als auch Nenner. verwirrt

Stimmt. War ein Denkfehler, ich hab natürlich 2p, 3p, 4p etc. nicht beachtet.

18.05.2010, 14:20

daN-R-G

Auf diesen Beitrag antworten »

Hallo und Danke erstmal für eure Anregungen!

Diese Formel mit der Anzahl von p in der Primfaktorzerlegung von n! hatten wir ebenfalls besprochen. Im gleichen Zusammenhang hatten wir auch die folgende Äquivalenz:

$\begin{eqnarray*} k \cdot \log p > \log n \stackrel{ \textbf{log ist streng monoton} }{\Leftrightarrow} p^k > n \end{eqnarray*}$

Wäre der Ansatz nicht vll. vielversprechend?

Es gelte $\begin{eqnarray*} p^k | \begin{pmatrix} n \\ m \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \mathbb{A} \textbf{: Es gilt } k \cdot \log p > \log n \end{eqnarray*}$

Kann ich denn nun durch $\begin{eqnarray*} p^k > n \end{eqnarray*}$ folgern, dass $\begin{eqnarray*} p^k \nmid \begin{pmatrix} n \\ m \end{pmatrix} \end{eqnarray*}$ ? Dann hätte ich ja einen Widerspruch und die Behauptung müsste gelten.

Vielen Dank Wink

18.05.2010, 14:28

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von daN-R-G
Kann ich denn nun durch $\begin{eqnarray*} p^k > n \end{eqnarray*}$ folgern, dass $\begin{eqnarray*} p^k \nmid \begin{pmatrix} n \\ m \end{pmatrix} \end{eqnarray*}$ ? Dann hätte ich ja einen Widerspruch und die Behauptung müsste gelten.

Ja, das ist zwar richtig, aber die Frage war doch eigentlich eine ganz andere oder nicht? Nämlich, ob man die oben verlinkte Formel für die Vielfachheit von p in n! für einen Beweis braucht oder nicht... Die Meinung von Arthur und mir dazu kennst du ja inzwischen...

18.05.2010, 15:14

daN-R-G

Auf diesen Beitrag antworten »

Okay. Ich glaube ich verstehe momenten leider nur die Hälfte. Die Vielfachheit von p spielt nun also die gewisse Rolle bei dem Problem.
Ich habe meine Unterlagen nochmal ein wenig durchgeschaut, und hoffe, dass ich nun die Richtige Argumentation habe.

Also es gilt die Äquivalenz $\begin{eqnarray*} k \cdot \log p > \log n \stackrel{ \textbf{log ist streng monoton} }{\Leftrightarrow} p^k > n \Leftrightarrow k > \frac{\log n}{\log p} \end{eqnarray*}$
Das ganze bedeutet in Worten ja, dass man nach $\begin{eqnarray*} \lfloor \frac{\log n}{\log p} \rfloor \end{eqnarray*}$ aufhören kann zu ermitteln, in welcher Vielfachheit p in n! vorkommt.

Nach einem Korollar in der Vorlesung gilt nun ebenfalls: $\begin{eqnarray*} v_p(\begin{pmatrix} n \\ m \end{pmatrix}) \leq \frac{\log n}{\log p} \end{eqnarray*}$ wobei $\begin{eqnarray*} v_p() \end{eqnarray*}$ die Vielfachheit von p sein soll.

Gelte nun $\begin{eqnarray*} p^k | \begin{pmatrix} n \\ m \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \mathbb{A} \textbf{: Es gilt } k \cdot \log p > \log n \end{eqnarray*}$

Es ist also $\begin{eqnarray*} p^k > n \Leftrightarrow k > \frac{\log n}{\log p} \end{eqnarray*}$ .
Nach dem Korollar gilt nun aber: $\begin{eqnarray*} l := v_p(\begin{pmatrix} n \\ m \end{pmatrix}) \leq \frac{\log n}{\log p} \end{eqnarray*}$ , also $\begin{eqnarray*} l < k \end{eqnarray*}$ .
In $\begin{eqnarray*} n! \end{eqnarray*}$ kommt also maximal $\begin{eqnarray*} p^l \end{eqnarray*}$ vor. Somit kann $\begin{eqnarray*} p^k \end{eqnarray*}$ nicht den Zähler, also erst recht nicht den Nenner von $\begin{eqnarray*} \frac{n!}{m!(n-m)!} \end{eqnarray*}$ teilen.
Damit habe ich ja den Widerspruch und die Behauptung muss gelten.

Stimmt das so in etwa? Ansonsten stehe ich richtig aufm Schlauch Augenzwinkern

18.05.2010, 15:46

Auf diesen Beitrag antworten »

Zitat:

Original von daN-R-G
Nach einem Korollar in der Vorlesung gilt nun ebenfalls: $\begin{eqnarray*} v_p(\begin{pmatrix} n \\ m \end{pmatrix}) \leq \frac{\log n}{\log p} \end{eqnarray*}$ wobei $\begin{eqnarray*} v_p() \end{eqnarray*}$ die Vielfachheit von p sein soll.

Aha, so zwischen den Zeilen verrätst du, dass ihr die Behauptung also schon bewiesen habt. Das ist doch nur die logarithmierte Variante deiner Behauptung aus dem Eröffnungsposting! Finger1

Ich weiß nicht, wie es anderen geht, aber ich komme mir jetzt irgendwie kräftig verarscht vor. unglücklich

18.05.2010, 15:55

daN-R-G

Auf diesen Beitrag antworten »

Oh... das tut mir jetzt leid. geschockt

Wie gesagt: Ich glaube ich verstehe den großen Zusammenhang der ganzen Sache noch nicht 100%. Mir ist das Korollar am Anfang auch noch garnicht ins Auge gesprungen.

Ich sinniere besser nochmal über das ganze und versuche es vollständig zu verstehen, aber bedanke mich trotzdem vielmals!!! Zumindest wäre ich nicht direkt drauf gekommen, wieso man die Vielfachheit von p im Binomialkoeffizinten betrachten sollte...

Verarschen wollte ich aber wirklich niemanden... wozu auch? verwirrt

18.05.2010, 16:31

Auf diesen Beitrag antworten »

Schade (für uns) ist jetzt nur, dass die eigentliche Beweisidee nun vollständig in deinem im Nebel bleibenden Korollar versteckt ist. Wäre ja wenigstens spannend zu erfahren, ob es über diesen Weg eleganter geht als in dem von Mystic und mir angedeutetem Zugang. Augenzwinkern

18.05.2010, 18:42

daN-R-G

Auf diesen Beitrag antworten »

Korollar 1

$\begin{eqnarray*} \textbf{Fuer } k, n \in \mathbb{N}, 0 \leq k \leq n \textbf{ gilt:} \end{eqnarray*}$

$\begin{eqnarray*} v_p(\begin{pmatrix} n \\ k\end{pmatrix}) = \sum\limits_{\nu=1}^{[\frac{\log n}{\log p}]}(\Big[\frac{n}{p^{\nu}} \Big]- \Big[\frac{k}{p^{\nu}}\Big] - \Big[\frac{n-k}{p^{\nu}}\Big]) \end{eqnarray*}$

Bemerkung 1

Sei $\begin{eqnarray*} a, b \in \mathbb{R} \end{eqnarray*}$ .
Dann ist $\begin{eqnarray*} [a+b] - [a] - \lbrack b\rbrack \in \lbrace0, 1\rbrace \end{eqnarray*}$ .
Insbesondere ist jeder Summand auf der rechten Seite von Korollar 1 entweder 0 oder 1. Folglich gilt:

$\begin{eqnarray*} v_p(\begin{pmatrix} n \\ k\end{pmatrix}) \leq \Big[\frac{\log n}{\log p}\Big] \leq \frac{\log n}{\log p}. \end{eqnarray*}$

Korollar 2

Für $\begin{eqnarray*} 0 \leq k \leq n, n\in \mathbb{N} \end{eqnarray*}$ gilt: $\begin{eqnarray*} v_p(\begin{pmatrix} n \\ k\end{pmatrix}) \leq \frac{\log n}{\log p} \end{eqnarray*}$

Das sind die 3 Sachen, die ich da jetzt mit einbeziehen würde. Im Beweis von Korollar 1 wendet man auch 3 mal die von dir erwähnte Formel an.

Oder was genau meintest du? Ansonsten missverstehe ich glaube ich was Hammer

18.05.2010, 18:56

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von daN-R-G
Im Beweis von Korollar 1 wendet man auch 3 mal die von dir erwähnte Formel an.

Danke für die Mühe, aber dieser eine Satz beantwortet eigentlich schon alle Fragen...

18.05.2010, 19:33

Auf diesen Beitrag antworten »

Einerseits schön, dass ich den richtigen Riecher hatte, andererseits etwas enttäuschend, dass es nicht einfacher geht. Na egal, danke für die Klärung. Wink

18.05.2010, 20:18

daN-R-G

Auf diesen Beitrag antworten »

Ich habe zu danken! Augenzwinkern

Neue Frage »

Antworten »

Binomialkoeffizient, Teilbarkeit, Primzahl, Logarithmus

Verwandte Themen