Primfaktorzerlegung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [x] die größte ganze Zahle, die kleiner als x ist. Zeigen Sie, dass der Exponent der Primzahl p in der Primfaktorzerlegung von n! den folgenden Wert hat:
[mm] $[\frac{n}{p}]+[\frac{n}{p^{2}}]+[\frac{n}{p^{3}}]+...+[\frac{n}{p^{k}}]$
[/mm]
wobei k die kleinste natürliche Zahl ist mit [mm] $p^k\ge [/mm] n$. |
Hallo Mathefreunde,
leider weiß überhaupt nicht, was ich bei dieser Aufgabe machen soll. Könnte mir jemand bitte einen Tipp geben, wie diese Aufgabe zu lösen ist.
Liebe Grüße
Christoph
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:53 Sa 01.06.2013 | | Autor: | leduart |
Hallo
warum experimentierst du nicht mal mit kleinen [mm] n\ge [/mm] 6?
dann sollte sich ein Weg zeigen.
gruss leduart
|
|
|
| |
|
Hallo leduart und felix,
danke für eure Tipps. Leider steige ich immer noch nicht hinter dieser Aufgabe durch. Wenn ich n= 6 habe habe ich die Summe die n!=720 ergibt. Mein Problem ist, dass ich nicht weiß was ich mit [mm] $p^k$ [/mm] machen soll. Muss ich das irgendwie wählen? Ich habe keine Ahnung :(
Liebe Grüße
Christoph
|
|
|
| |
|
Hallo Christoph,
> danke für eure Tipps. Leider steige ich immer noch nicht
> hinter dieser Aufgabe durch. Wenn ich n= 6 habe habe ich
> die Summe die n!=720 ergibt. Mein Problem ist, dass ich
> nicht weiß was ich mit [mm]p^k[/mm] machen soll. Muss ich das
> irgendwie wählen? Ich habe keine Ahnung :(
Das steht doch in der Aufgabe: das kleinste k, für das [mm] p^k\ge{n} [/mm] ist.
Also für p=2 ist k=3 zu wählen, für p=3 ist k=2 und für p=5 ebenfalls k=5. Das wars. Größere Primfaktoren als p=5 wird 6!=720 sicher nicht haben.
Grüße
reverend
|
|
|
| |
|
Hallo reverend,
danke für deine Hilfe. Jetzt habe ich schon mal einen Teil verstanden. Was ich immer noch nicht verstehe ist, was es mit dem Ausdruch [x] auf sich hat. Ist das eine Äquivalenzklasse oder wie muss ich das auffassen?
Liebe Grüße
Christoph
PS.: Muss bei p=5 nicht auch k=2 folgen? Denn 25=5² ist schon größer als 6.
|
|
|
| |
|
Hallo Christoph,
> danke für deine Hilfe. Jetzt habe ich schon mal einen Teil
> verstanden. Was ich immer noch nicht verstehe ist, was es
> mit dem Ausdruch [x] auf sich hat. Ist das eine
> Äquivalenzklasse oder wie muss ich das auffassen?
Nein, das ist hier die "Floor-Funktion", auch "untere Gaußklammer" genannt. Sie gibt diejenige ganze Zahl zurück, so dass [mm] \lfloor{x}\rfloor\le{x}<\lfloor{x}\rfloor+1 [/mm] ist.
Du kannst wahlweise die +1 auch in die Gaußklammer mit hineinziehen, das macht keinen Unterschied.
> PS.: Muss bei p=5 nicht auch k=2 folgen? Denn 25=5² ist
> schon größer als 6.
Du hast völlig Recht! Ich habe mich vertippt, bekam vorhin gerade Besuch, bevor ich fertig war. Damit machst Du aber auch deutlich, dass Du die Bestimmung von k verstanden hast. Weiter so.
|
|
|
| |
|
Hallo reverend,
bedeutet das, dass die untere Gauß-Klammer mein x abrundet?
Liebe Grüße
Christoph
PS.: Ich gehe nun ins Bett. Ich habe morgen Vorlesung. Wenn du Lust hast, können wir uns auch morgen noch schreiben. Ich bin so ab 12 Uhr wieder online. Ich wünsche eine geruhsame Nacht.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:11 Mo 03.06.2013 | | Autor: | M.Rex |
Hallo
> Hallo reverend,
>
> bedeutet das, dass die untere Gauß-Klammer mein x
> abrundet?
Auf ganze Zahlen, ja.
>
> Liebe Grüße
>
> Christoph
>
> PS.: Ich gehe nun ins Bett. Ich habe morgen Vorlesung. Wenn
> du Lust hast, können wir uns auch morgen noch schreiben.
> Ich bin so ab 12 Uhr wieder online. Ich wünsche eine
> geruhsame Nacht.
Bis dann
Marius
|
|
|
| |
|
Hallo Marius,
also ich habe noch bei der Summe mit gewissen Zahlen herumprobiert. Mir ist dabei aufgefallen, k kann nur den Wert 1 oder 0 annehmen. Falls ich richtig liege frage ich mich, wie ich formal den Beweis führen muss?
Liebe Grüße
Christoph
|
|
|
| |
|
Hallo Christoph,
> also ich habe noch bei der Summe mit gewissen Zahlen
> herumprobiert. Mir ist dabei aufgefallen, k kann nur den
> Wert 1 oder 0 annehmen.
Das stimmt sicher nicht. Versuch mal die Faktorisierung von 25! oder 27!.
> Falls ich richtig liege frage ich
> mich, wie ich formal den Beweis führen muss?
Dazu gibt es keinen besseren Tipp als den, den Felix Dir gegeben hat.
Nach wie vor: viel Erfolg!
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:15 Mi 05.06.2013 | | Autor: | Marcel |
Hallo,
> Hallo reverend,
>
> bedeutet das, dass die untere Gauß-Klammer mein x
> abrundet?
[mm] $[x]:=\lfloor [/mm] x [mm] \rfloor:=\max\{z \in \IZ:\;\; z \le x\}$ [/mm] ist einfach die größte ganze Zahl,
die kleinergleich [mm] $x\,$ [/mm] ist.
Es gilt:
Für alle $x [mm] \in \IR$ [/mm] existiert genau ein $z [mm] \in \IZ$ [/mm] mit
$$z [mm] \le [/mm] x [mm] \red{\;<\;} z+1\,.$$
[/mm]
Dieses [mm] $z=z(x)\,$ [/mm] ist nichts anderes als [mm] $[x]\,.$
[/mm]
Für Zahlen $x [mm] \ge [/mm] 0$ "schneidet [mm] $[x]\,$ [/mm] quasi einfach die Nachkommastellen
weg" - wobei wir beachten, dass wir nicht [mm] $,\overline{9}$ [/mm] schreiben, sondern
sowas benutzen wie [mm] $1,\overline{9}=2\,.$:
[/mm]
[mm] $[1,2]=1\,,$
[/mm]
[mm] $[11,\overline{3}]=11\,,$
[/mm]
[mm] $[27,\overline{9}]=[28]=28\,.$
[/mm]
Bei Zahlen [mm] $<0\,$ [/mm] werden (wieder mit Ausnahme der "Periode 9") die Nachkommastellen
abgeschnitten, und die ganze Zahl dann um 1 verringert, wenn es wirklich
auch Nachkommastellen gab:
[mm] $[-1,\overline{9}]=[-2]=-2\,,$ [/mm] (hier gab es, bei 2,0, KEINE Nachkommastellen)
[mm] $[-2,3]=-2-1=-3\,,$
[/mm]
[mm] $[-102,\overline{453}]=-102-1=-103\,.$
[/mm]
Hier auch mal ein Bild des Graphen dieser Funktion, wobei Du bitte
beachtest, dass so eine Stufe in der Art [.,.) zu lesen ist:
Zum Beispiel ist [mm] $f(2)=2\,$ [/mm] aber [mm] $f(2-\epsilon)=1$ [/mm] für alle $0 < [mm] \epsilon \le 1\,.$
[/mm]
[Dateianhang nicht öffentlich]
Gruß,
Marcel
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:02 Sa 01.06.2013 | | Autor: | felixf |
Moin Christoph,
> Sei [x] die größte ganze Zahle, die kleiner als x ist.
> Zeigen Sie, dass der Exponent der Primzahl p in der
> Primfaktorzerlegung von n! den folgenden Wert hat:
>
> [mm][\frac{n}{p}]+[\frac{n}{p^{2}}]+[\frac{n}{p^{3}}]+...+[\frac{n}{p^{k}}][/mm]
>
> wobei k die kleinste natürliche Zahl ist mit [mm]p^k\ge n[/mm].
ueberleg dir mal:
* wieviele Zahlen zwischen $1$ und $n$ werden durch $p$ geteilt?
* wieviele Zahlen zwischen $1$ und $n$ werden durch [mm] $p^2$ [/mm] geteilt?
* wieviele Zahlen zwischen $1$ und $n$ werden durch [mm] $p^3$ [/mm] geteilt?
* ...
Vielleicht hilft dir das weiter...
LG Felix
|
|
|
| |
|
Hallo reverend,
[mm] $p^k [/mm] | n$, wenn [mm] $p^k [/mm] = [mm] n\iff k=[\frac{n}{lg{p}}]$. [/mm] Wenn ich [mm] $p^k>n$ [/mm] habe, erhalte ich Brüche, die nicht aus den ganzen Zahlen stammen. Daraus schließe ich: Wenn [mm] $p^k [/mm] = n$ ist teilt [mm] $p^k$ [/mm] n nur einmal.
Ich vermute aber, dass dieser Gedankengang ins Leere führt. Irgendwie stocher ich immer noch im Nebel herum :(. Was mache ich nur falsch?
Liebe Grüße
Christoph
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:28 Di 04.06.2013 | | Autor: | leduart |
Hallo
[mm] p^k>n [/mm] hast du recht, [mm] p^k [/mm] teilt n! nicht, aber das heisst doch nicht das k hoechstens 1 ist! und [mm] dassp^k [/mm] n! nicht teilt. du hast wirklich nicht experimentiert!! z.B
p+3, n=20 [mm] n!+1*2*p*4+5*2p*7*8*p^2*......2*p^*19*20
[/mm]
was ist das hoechste k, das [mm] 3^k [/mm] 20! teilt?
Gruss leduart
|
|
|
| |
|
Hallo leduart,
bereits im ersten Satz deines Beitrages hast zwei Aussagen getroffen, die einander widersprechen:
"$ [mm] p^k [/mm] $ teilt n! nicht , aber das heisst doch nicht das k hoechstens 1 ist! und dass $ [mm] p^k [/mm] $ n! nicht teilt."
Hä?!?!
Liebe Grüße
Christoph
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:50 Di 04.06.2013 | | Autor: | leduart |
Hallo
dass das ein dummer Tipfehler war haettest du merken koenne,
[mm] p^k?n [/mm] teilt n nicht kann aber n! teilen/ Bsp [mm] 3^4 [/mm] telt 20 nicht, [mm] 20/3^4<1
[/mm]
aber [mm] 3^4 [/mm] teilt 20!
hast du dn rest des posts angesehen? p=3, n=20 was ist k?
Gruss leduart
|
|
|
| |
|
Hallo leduart,
vielen Dank für die Richtigstellung. Ich schau mir die ganzen Beiträge nochmal an. Ich melde mich auf jeden Fall nochmal.
Liebe Grüße
Christoph
|
|
|
| |
|
Hallo leduart,
also ich denke ich weiß wie die die Aufgabe funktioniert. Es muss auf jeden induktiv gezeigt werden. Aber bevor ich das tue möchte ich Anhand eines Beispieles sicherstellen, dass ich es auch wirklich verstanden habe.
Bsp.: n=6
$6!=6*5*4*3*2*1=(3*2)*5*(2*2)*3*2*1$
Nun will ich wissen, wie man mit Hilfe der Summe festellt, wie oft die 2 potenziert in meiner Primfaktorzerlegung vorkommt.
[mm] $[\frac{6}{2}]+[\frac{6}{4}]=3+1=4$ [/mm] also ist [mm] $2^4$ [/mm] mein erster Primfaktor. Ist das richtig so? Schließlich wären alle Summanden, wegen der unteren Gaußklammern 0.
Liebe Grüße
Christoph
|
|
|
| |
|
Hallo Christoph,
das Beispiel n=6 ist zu klein, um das Prinzip zu erkennen. Du machst da alles richtig, aber...
> also ich denke ich weiß wie die die Aufgabe funktioniert.
> Es muss auf jeden induktiv gezeigt werden.
Nein, definitiv nicht. Es genügt, es für einen (beliebigen) Primfaktor zu zeigen. Induktion bringt hier absolut nichts.
> Aber bevor ich
> das tue möchte ich Anhand eines Beispieles sicherstellen,
> dass ich es auch wirklich verstanden habe.
>
> Bsp.: n=6
>
> [mm]6!=6*5*4*3*2*1=(3*2)*5*(2*2)*3*2*1[/mm]
>
> Nun will ich wissen, wie man mit Hilfe der Summe festellt,
> wie oft die 2 potenziert in meiner Primfaktorzerlegung
> vorkommt.
>
> [mm][\frac{6}{2}]+[\frac{6}{4}]=3+1=4[/mm] also ist [mm]2^4[/mm] mein erster
> Primfaktor. Ist das richtig so? Schließlich wären alle
> Summanden, wegen der unteren Gaußklammern 0.
Jetzt hast Du offenbar endlich die angegebene Rechnung verstanden, aber noch nicht, warum sie funktioniert.
Untersuche doch mal die Primfaktoren 2,3,5,7 in 28! und ermittle ihre Anzahl erst auf einem anderen Weg (z.B. Abzählen...), erst dann mit der Formel.
Grüße
reverend
|
|
|
| |
|
Hallo reverend,
für p=2 und 28! ergibt die Summe
[mm] $[\frac{28}{2}]+[\frac{28}{4}]+[\frac{28}{8}]+[\frac{28}{16}]=14+7+3+1=25\Rightarrow 2^{25}$
[/mm]
für p=3
[mm] $[\frac{28}{3}]+[\frac{28}{9}]+[\frac{28}{27}]=9+3+1=13\Rightarrow 3^{13}$
[/mm]
für p=5
[mm] $[\frac{28}{5}]+[\frac{28}{25}]=5+1=6\Rightarrow 5^6$
[/mm]
für p=7
[mm] $[\frac{28}{7}]=4\Rightarrow 7^4$
[/mm]
für p=11
[mm] $[\frac{28}{11}]=2\Rightarrow 11^2$
[/mm]
für p=13
[mm] $[\frac{28}{13}]=2\Rightarrow 13^2$
[/mm]
[mm] $\vdots$
[/mm]
[mm] $28!=2^{25}*3^{13}*5^6*7^4*11^2*13^2*17*19*23$
[/mm]
Also die einzige Erkenntnis, die ich hieraus ziehe ist, dass für kleiner werdende k p, sodass [mm] $p\le [/mm] n$, immer größer wird.
Ist das hinreichend?
Liebe Grüße
Christoph
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:52 Mi 05.06.2013 | | Autor: | leduart |
Hallo
Hast du denn manl 28! ausgeschrieben, wie zaehlst du dann die 2 er oder 3 er Potenzen zusammen? wie oft kommt [mm] 3^3 [/mm] vor, wie oft [mm] 3^2, [/mm] wie oft 3 als Faktor einer der Zahlen?
wie rechnest du dann die hoechste Potenz von 3 daraus aus? dasselbe mit 2 und 5
Gruss leduart
|
|
|
| |
|
Hallo leduart,
ohne meine Summe aus der Voraussetzung würde 28! so hinschreiben:
$28!=28*27*26*25*24*23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1=$
[mm] $(7*2^2)*(3^3)*(2*13)*(5^2)*(2^3*3)*23*(2*11)*(7*3)*(2^2*5)*19*(2*3^2)*17*(2^4)*(3*5)*(2*7)*13*(2^2*3)*11*(2*5)*(3^2)*(2^3)*7*(3*2)*5*(2^2)*3*2$
[/mm]
Worauf möchtest du hinaus leduart?
Liebe Grüße
Christoph
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:18 Mi 05.06.2013 | | Autor: | M.Rex |
Hallo
> Hallo leduart,
>
> ohne meine Summe aus der Voraussetzung würde 28! so
> hinschreiben:
>
> [mm]28!=28*27*26*25*24*23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1=[/mm]
>
> [mm](7*2^2)*(3^3)*(2*13)*(5^2)*(2^3*3)*23*(2*11)*(7*3)*(2^2*5)*19*(2*3^2)*17*(2^4)*(3*5)*(2*7)*13*(2^2*3)*11*(2*5)*(3^2)*(2^3)*7*(3*2)*5*(2^2)*3*2[/mm]
>
> Worauf möchtest du hinaus leduart?
Wieoft kommt denn die 2 vor? Wieoft 2² 2³ usw. Welches ist der höchstmögliche Exponent der 2
Dasselbe mit der 3. Wieoft kommt die 3 vor, wieoft 3² usw.
Gehe mal alle Primfaktoren durch, die auftauchen.
>
> Liebe Grüße
>
> Christoph
Marius
|
|
|
| |
|
Hallo Marius,
jetzt hab ich es. Weil p|n müssen auch die höheren Potenzen n teilen. Darum funktioniert es.
Richtig?
Liebe Grüße
Christoph
|
|
|
| |
|
Hallo Christoph,
> jetzt hab ich es. Weil p|n müssen auch die höheren
> Potenzen n teilen. Darum funktioniert es.
> Richtig?
Nein, das ist Unsinn. Für p=7 schon funktioniert das nicht, für alle größeren [mm] p\le{28} [/mm] auch nicht.
28! ist das Produkt aller natürlichen Zahlen bis einschließlich 28, richtig? Nun nehmen wir mal die 3. Wie oft wird dieser Primfaktor in n! vorkommen?
Erstmal kommt er in allen durch 3 teilbaren Zahlen vor. Das sind 9 Stück, nämlich 3,6,9,12,15,18,21,24,27.
Aber in der 9 kommt er gleich zweimal vor, und auch in allen Vielfachen von 9. Also müssen wir für 9,18,27 den Faktor 3 noch dreimal hinzufügen, macht bis hierher 12.
Das reicht aber immer noch nicht, denn in 27 kommt er nicht nur zweimal, sondern sogar dreimal vor, deswegen müssen wir noch eins draufrechnen und wissen jetzt: [mm] 3^{13}|28!
[/mm]
Das gleiche nochmal für die 2. Es gibt 14 gerade Zahlen bis 28.
Die durch [mm] 2^2 [/mm] teilbaren haben die 2 aber nochmal, also weitere 7 Faktoren "2", bis hierher also 21.
Die durch [mm] 2^3 [/mm] teilbaren haben die 2 sogar ein drittes Mal, deswegen noch dreimal die 2 für 8,16,24, jetzt also 24 Faktoren "2".
Und sogar [mm] 2^4 [/mm] muss noch berücksichtigt werden, weil die 16 ja auch ein Faktor in 28! ist. Deswegen insgesamt: [mm] 2^{25}|28!
[/mm]
So, und jetzt mach das nochmal genauso für die 5.
Ich weiß wirklich nicht, was an dieser Aufgabe so schwierig ist, dass Du tagelang daran herumrechnest.
Grüße
reverend
|
|
|
| |
|
Hallo reverend,
ja das meine ich [mm] $5^6|28!$ [/mm] usw. Dann gilt es auch allgemein.
So ich danke dir für die Hilfe. Auch Marius, Felix, Marcel und leduart danke ich.
Liebe Grüße
Christoph
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:17 Mi 05.06.2013 | | Autor: | leduart |
Hallo
da du sehr falsch das formuliert hast, von dem du spaeter sagst, dass du es gemeint hast, schrieb doch mal den allgemeinen Beweis jetzt auf.
ganz glaube ich nicht dass du das 100% verstanden hast.
Gruss leduart
|
|
|
|
