Primfaktorzerlegung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:30 Sa 16.02.2019 | | Autor: | magics |
| Aufgabe | Es sei $n [mm] \ge [/mm] 2$ eine natürliche Zahl. Dann gibt es eine Zahl $m [mm] \in \IN*$ [/mm] sowie Primzahlen [mm] $p_1, [/mm] ..., [mm] p_m$ [/mm] mit $n = [mm] \produkt_{i=1}^{m}p_i$.
[/mm]
Beweis:
Als Induktionsaufhängung nehmen wir $n=2$ und stellen fest, die Aussage stimmt. Nun sei $N [mm] \in \IN\*$ [/mm] und $N > 2$. Wir nehmen an, dass jedes [mm] $\red{m N hat einen Primteiler r. Falls $N=r$ so ist N prim und nichts weiter zu zeigen. Sei deshalb N nicht prim, also $r < N$. Damit ist $M = [mm] \bruch{N}{r}$ [/mm] echt kleiner als N. Mit Induktionsannahme gibt es eine natürliche Zahl [mm] $\ell \in \IN\*$ [/mm] und Primzahlen [mm] $p_1, [/mm] ..., [mm] p_{\ell}$ [/mm] mit $M = [mm] p_1 [/mm] * ... * [mm] p_{\ell}$. [/mm] Wir setzen nun [mm] $\ell [/mm] = 1$ und [mm] $p_m [/mm] = r$, um mit
$N = M * [mm] p_m [/mm] = [mm] \produkt_{i=1}^{m}p_i$
[/mm]
eine Primfaktorzerlegung von N zu erhalten.
# |
Hallo werte Gesellschaft,
die Vollständige Induktion gibt mir zuweilen Grund zur Annahme, dass ein Perpetuum Mobile tatsächlich möglich ist.
Um meine Gedanken präziser zu formulieren, möchte ich noch kurz die hier verwendete Variante der vollständigen Induktion skizzieren:
Für jedes n aus [mm] $\IN$ [/mm] sei $Q(n)$ eine Aussage. Angenommen, man kann die beiden folgenden Eigenschaften nachweisen:
1. Induktionsverankerung: Es ist $Q(0) = wahr$
2. Induktionsschritt: Ist $Q(k) = wahr$ für alle $k [mm] \le [/mm] m$, so folgt $Q(m+1) = wahr$
Dann ist $Q(n) = wahr$ für alle $n [mm] \in \IN$.
[/mm]
Meine Frage gilt dem in der Aufgabenstellung rot markierte Satz: "Wir nehmen an, dass jedes [mm] $\red{m".
Einfach gefragt: Warum darf man das annehmen? Bei einer klassichen Vollständigen Induktion, bei der wir den Induktionsschritt $n [mm] \mapsto [/mm] n+1$ vollziehen, haben wir ja auch nur im Induktionsanfang gezeigt, dass die Aussage für ein Exempel wahr ist. Durch das $n [mm] \mapsto [/mm] n+1$ wird dann der sinnbildliche Dominostein angestoßen.
In dem hier gezeigten Beweis, ist die Voraussetzung bereits, das, was man eigentlich beweisen soll... wie kann das ein Beweis sein?
Grüße
Thomas
|
|
| |
|
Zunächst hat dein Beweis eine kleine Schwäche, die aber nichts mit der Fragestellung zu tun hat: die Behauptung, dass r ein Primfaktor ist. Da steckt schon ganz viel von dem drin, was erst durch den Beweis gezeigt werden soll. Ich schlage vor, dass du r nur als echten Teiler betrachtest:
1. Fall: n lässt sich als Produkt nur durch n=n*1 schreiben. Dann ist n = [mm] p_1 [/mm] selber eine Primzahl.
2. Fall: n=r*s mit 1<r<n und somit auch 1<s<n. Dann sind nach IV [mm] r=\produkt_{i=1}^{t}p_i [/mm] und [mm] s=\produkt_{j=1}^{u}p_j [/mm] .... und somit [mm] r*s=\produkt_{i=1}^{t}p_i*\produkt_{i=t+1}^{m}p_i=\produkt_{i=1}^{m}p_i.
[/mm]
Nun aber zu deiner Frage:
Die rote Aussage ist richtig.
Du möchtest - wie gewohnt - von n auf n+1 schließen. Das wird in sofern kritisch, wie man es am Beispiel n=59 sieht: Von n=59 aus kannst du keine Aussage für die Primzerlegung von n+1=60 finden, die sinnvoll wäre. Wenn du aber die Behauptung umformulierst, geht es, und das perpetuum mobile verschwindet auch.
Neue Behauptung: Für alle natürlichen Zahlen n>1 lassen sich alle Zahlen der Menge [mm] M_n=\{x|1
Wenn du nun die Behauptung für n=59 auf n=60 ausdehnen willst, kannst du - weil nun für 59 alle Zahlen von 2 bis 59 als durch Primfaktoren darstellbar anzusehen sind - die 60 z.B. als 6*10 schreiben und nun auf 6 und 10 statt auf 59 zurückgreifen. Nachdem du nun den Beweis für 60 geführt hast, kommt nun die 60 hinzu, und für die Zahlen von 2 bis 59 galt die Aussage ja sowieso als bewiesen, also gilt sie jetzt auch von 2 bis 60.
Bemerkung: Wenn du eine Aussage, die nur für gerade Zahlen gilt, per VI beweisen willst, kannst du ja auch nicht z.B. von 59 auf 60 schließen, weil die 59 nicht dazu gehört. Die übliche Vorgehensweise, die geraden Zahlen als k=2n zu schreiben und die VI über n zu machen, ist letztlich nur ein mathematischer Trick, der die 59 einfach überspringt und auf 58 zurückgreift. Genau so überspringst du beim obigen Beispiel die 59 und gehst auf 6 und 10 zurück.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:04 So 17.02.2019 | | Autor: | magics |
Habe deine Korrektur für die Herleitung der Existenz eines Primteilers verstanden. Darin verbirgt sich auch nochmal ein Ansatz, entsprechend der Variante der Vollst. Indukt. aus meinem Beispiel.
Vielen Dank! Super Erklärung (vor allem das mit dem $k=2n$ Trick bringt aus irgendeinem Grund Klarheit..)
|
|
|
| |
|
Hiho,
> Meine Frage gilt dem in der Aufgabenstellung rot markierte
> Satz: "Wir nehmen an, dass jedes [mm]\red{m
> Primfaktorzerlegung hat.".
>
> Einfach gefragt: Warum darf man das annehmen?
Setze als Aussage:
Q(k) := "k-1 hat eine Primfaktorzerlegung"
Nun gibst du ja an, dass ihr folgendes Verfahren der vollst. Induktion nutzt, welches du ja anscheinend auch akzeptierst:
> Für jedes n aus [mm]\IN[/mm] sei [mm]Q(n)[/mm] eine Aussage. Angenommen, man
> kann die beiden folgenden Eigenschaften nachweisen:
>
> 1. Induktionsverankerung: Es ist [mm]Q(0) = wahr[/mm]
> 2.
> Induktionsschritt: Ist [mm]Q(k) = wahr[/mm] für alle [mm]k \le m[/mm], so
> folgt [mm]Q(m+1) = wahr[/mm]
>
> Dann ist [mm]Q(n) = wahr[/mm] für alle [mm]n \in \IN[/mm].
Dann ist die Aussage "Wir nehmen an, dass jedes $ [mm] \red{m
"Ist [mm]Q(m) = wahr[/mm] für alle [mm]m \le N[/mm]"
Zu zeigen ist dann also nur noch:
> so folgt [mm]Q(N+1) = wahr[/mm]
Und Q(N+1) ist: "N hat eine Primfaktorzerlegung".
Man hat einzig ein bisschen die Bezeichner k,m,M,N geändert, aber das Prinzip beibehalten.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:07 So 17.02.2019 | | Autor: | magics |
Hallo, du lieber Himmel, du hast recht.
Ja, ich habe die Vorgehensweise akzeptiert und ja, wie ich jetzt auch sehe, ist der vorgestellte Beweis eine astreine Anwendung dieser. Deine und HJKweseleits Antwort haben mir den Sachverhalt verständlich rübergebracht.
Ich bin euch wirklich so dankbar... wenn ich euch jedesmal einen Drink eurer Wahl ausgeben würde... boah :D
Beste Grüße
Thomas
|
|
|
|
