Vollständige Induktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige, dass der Bruch [mm] \bruch{21n + 4}{14n + 3} [/mm] für alle n [mm] \in \IN [/mm] nicht kürzbar ist. |
Wie kann man das mittels vollständiger Induktion beweisen?
Ich bin mir bewusst, dass andere Beweismethoden schneller und eleganter sind, um dieses Problem zu lösen. Ich bin mir aber nicht ganz sicher, wie man es mit Hilfer vollständiger Induktion löst.
Man zeigt es für n = 0 [mm] \Rightarrow [/mm] gcd(4, 3) = 1.
Man nimmt gcd(21n + 4, 14n + 3) = 1 an und zeigt, dass daraus
gcd(21(n+1) + 4, 14(n+1) + 3) = 1 folgt.
Wie macht man weiter?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:35 Mo 20.07.2015 | | Autor: | abakus |
> Zeige, dass der Bruch [mm]\bruch{21n + 4}{14n + 3}[/mm] für alle n
> [mm]\in \IN[/mm] nicht kürzbar ist.
>
> Wie kann man das mittels vollständiger Induktion
> beweisen?
>
> Ich bin mir bewusst, dass andere Beweismethoden schneller
> und eleganter sind, um dieses Problem zu lösen. Ich bin
> mir aber nicht ganz sicher, wie man es mit Hilfer
> vollständiger Induktion löst.
>
> Man zeigt es für n = 0 [mm]\Rightarrow[/mm] gcd(4, 3) = 1.
> Man nimmt gcd(21n + 4, 14n + 3) = 1 an und zeigt, dass
> daraus
>
> gcd(21(n+1) + 4, 14(n+1) + 3) = 1 folgt.
>
> Wie macht man weiter?
Hallo,
zu zeigen, dass etwas für alle n NICHT gilt, ist nicht gerade ein sinnvolles Anwendungsgebiet für Induktionsbeweise.
Was mir als einzige Möglichkeit einfällt:
Beweise mit vollst. Ind., dass für alle n gilt
[mm]2>\bruch{21n + 4}{14n + 3}>1,5.[/mm]
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:35 Mo 20.07.2015 | | Autor: | tobit09 |
Hallo abakus!
> zu zeigen, dass etwas für alle n NICHT gilt, ist nicht
> gerade ein sinnvolles Anwendungsgebiet für
> Induktionsbeweise.
Auch ich scheitere daran, hier einen "sinnvollen" Induktionsbeweis zu finden.
Ich denke aber nicht, dass sich negierte Aussagen grundsätzlich nicht für Induktionsbeweise eignen.
(Beispielsweise lässt sich der Satz, dass jede nichtleere Teilmenge [mm] $A\subseteq\IN$ [/mm] ein kleinstes Element besitzt wie folgt beweisen:
Man zeigt, dass jede Teilmenge [mm] $A\subseteq\IN$ [/mm] ohne kleinstes Element schon die leere Menge ist, indem man per Induktion nach n zeigt: Für alle [mm] $n\in\IN$ [/mm] gilt NICHT, dass es ein [mm] $m\le [/mm] n$ mit [mm] $m\in [/mm] A$ gibt.)
> Was mir als einzige Möglichkeit einfällt:
> Beweise mit vollst. Ind., dass für alle n gilt
> [mm]2>\bruch{21n + 4}{14n + 3}>1,5.[/mm]
Die rechte Ungleichung ist z.B. für n=1 falsch.
Vor allem aber sehe ich nicht, was uns diese Ungleichungen für den gesuchten Nachweis bringen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:24 Mo 20.07.2015 | | Autor: | M.Rex |
Hallo.
> Zeige, dass der Bruch [mm]\bruch{21n + 4}{14n + 3}[/mm] für alle n
> [mm]\in \IN[/mm] nicht kürzbar ist.
>
> Wie kann man das mittels vollständiger Induktion
> beweisen?
Ist das explizit per vollständiger Induktion angefordert?
Denn dann schließe ich mich mal abakus an, das ist kein geeignetes Verfahren für die Nicht-Existenz.
>
> Ich bin mir bewusst, dass andere Beweismethoden schneller
> und eleganter sind, um dieses Problem zu lösen. Ich bin
> mir aber nicht ganz sicher, wie man es mit Hilfer
> vollständiger Induktion löst.
>
> Man zeigt es für n = 0 [mm]\Rightarrow[/mm] gcd(4, 3) = 1.
> Man nimmt gcd(21n + 4, 14n + 3) = 1 an und zeigt, dass
> daraus
>
> gcd(21(n+1) + 4, 14(n+1) + 3) = 1 folgt.
>
> Wie macht man weiter?
Ich würde den Bruch aufteilen:
[mm] \frac{21n+4}{14n+3}
[/mm]
[mm] =\frac{14n+3+7n+1}{14n+3}
[/mm]
[mm] =\frac{14n+3}{14n+3}+\frac{7n+1}{14n+3}
[/mm]
[mm] =1+\frac{7n+1}{14n+3}
[/mm]
Nun wieder du.
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:45 Mo 20.07.2015 | | Autor: | tobit09 |
Hallo Marius!
> Ich würde den Bruch aufteilen:
>
> [mm]\frac{21n+4}{14n+3}[/mm]
> [mm]=\frac{14n+3+7n+1}{14n+3}[/mm]
> [mm]=\frac{14n+3}{14n+3}+\frac{7n+1}{14n+3}[/mm]
> [mm]=1+\frac{7n+1}{14n+3}[/mm]
>
> Nun wieder du.
Wieder sehe ich nicht, wie uns das weiter bringt.
Zu zeigen ist, dass $21n+4$ und $14n+3$ teilerfremd sind.
Ich erkenne keinen wirklichen Zusammenhang zur rationalen Zahl
[mm] $\frac{21n+4}{14n+3}=\frac{2*(21n+4)}{2*(14n+3)}$,
[/mm]
die sich in gekürzter und ungekürzter Form darstellen lässt.
Viele Grüße
Tobias
|
|
|
| |
|
> Hallo.
>
> Ist das explizit per vollständiger Induktion angefordert?
> Denn dann schließe ich mich mal abakus an, das ist kein
> geeignetes Verfahren für die Nicht-Existenz.
Nein, ist es nicht. Ich wollte es bloß als Übung strikt mit vollständiger Induktion machen.
>Ich würde den Bruch aufteilen:
>
>$ [mm] \frac{21n+4}{14n+3} [/mm] $
>$ [mm] =\frac{14n+3+7n+1}{14n+3} [/mm] $
>$ [mm] =\frac{14n+3}{14n+3}+\frac{7n+1}{14n+3} [/mm] $
>$ [mm] =1+\frac{7n+1}{14n+3} [/mm] $
>
>Nun wieder du.
[mm] $1+\frac{7n+1}{14n+3} [/mm] = [mm] 1+\frac{7n+1}{2(7n+1) + 1} [/mm] $ ?
Da der Nenner immer um 1 größer ist als das doppelte des Zählers, kann es kein $n$ geben, sodass der Bruch gekürzt wird.
Aber wie hilft mir das für eine Vollständige Induktion?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:28 Mo 20.07.2015 | | Autor: | tobit09 |
Hallo m8sar6l1Uu!
> > Ist das explizit per vollständiger Induktion angefordert?
> Nein, ist es nicht. Ich wollte es bloß als Übung strikt
> mit vollständiger Induktion machen.
Ergebnis des Versuches, diese Aussage sinnvoll mit Induktion zu beweisen ist offenbar, dass es unabhängig voneinander 4 Leute (du, ich, abakus und M.Rex) nicht geschafft haben.
Das deutet daraufhin, dass kein "naheliegender" "sinnvoller" Induktionsbeweis existiert.
Induktion ist eben nicht bei jeder Aussage über alle natürlichen Zahlen das Mittel der Wahl.
> >Ich würde den Bruch aufteilen:
> >
> >[mm] \frac{21n+4}{14n+3}[/mm]
> >[mm] =\frac{14n+3+7n+1}{14n+3}[/mm]
> >[mm] =\frac{14n+3}{14n+3}+\frac{7n+1}{14n+3}[/mm]
>
> >[mm] =1+\frac{7n+1}{14n+3}[/mm]
> >
> >Nun wieder du.
>
> [mm]1+\frac{7n+1}{14n+3} = 1+\frac{7n+1}{2(7n+1) + 1}[/mm] ?
>
> Da der Nenner immer um 1 größer ist als das doppelte des
> Zählers, kann es kein [mm]n[/mm] geben, sodass der Bruch gekürzt
> wird.
Mich überzeugt die Begründung noch nicht: Warum sind für alle [mm] $m\in\IN$ [/mm] die Zahlen $m$ und $2m+1$ teilerfremd?
Zu zeigen ist also, dass jede natürliche Zahl [mm] $k\in\IN$, [/mm] die sowohl $m$ als auch $2m+1$ teilt, schon $k=1$ erfüllt.
Gelte also $k|m$ und $k|2m+1$.
Zu zeigen ist $k=1$.
Wegen $k|2m+1$ und $k|m$ gilt auch $k|(2m+1)-m$, also $k|m+1$.
Zusammen mit $k|m$ folgt daraus $k|(m+1)-m$, also $k|1$.
Bekanntlich (?) folgt somit $k=1$.
Damit ist gezeigt, dass $7n+1$ und $2(7n+1)+1$ teilerfremd sind.
Zu zeigen ist in der ursprünglichen Aufgabenstellung jedoch, dass $21n+4$ und $14n+3$ teilerfremd sind.
Gehe dazu (ohne Induktion) ähnlich vor wie ich es dir für das Beispiel mit $m$ und $2m+1$ vorgemacht habe.
> Aber wie hilft mir das für eine Vollständige Induktion?
Marius wollte offenbar einen Weg ohne Induktion beginnen.
Wie gesagt: Anscheinend lässt sich diese Aufgabe gar nicht in naheliegender Weise sinnvoll per Induktion lösen.
Viele Grüße
Toiias
|
|
|
| |
|
Wie wäre es mit einem Widerspruchsbeweis stattdessen?
Angenommen es gebe einen gemeinem Faktor $m > 1$, der beide Terme teilt.
Dann muss gelten:
$ (21n+4) [mm] \equiv [/mm] 0 $ (mod m)
$ (14n+3) [mm] \equiv [/mm] 0 $ (mod m)
Dann muss nach gelten:
$ (2*(21n+4)) [mm] \equiv [/mm] 2*0 $ (mod m)
$ (3*(14n+3)) [mm] \equiv [/mm] 3*0 $ (mod m)
$ (42n+8) [mm] \equiv [/mm] 0 $ (mod m)
$ (42n+9) [mm] \equiv [/mm] 0 $ (mod m)
Und daraus wiederum:
$ ((42n+9) - (42n+8)) [mm] \equiv [/mm] (0-0) $ (mod m)
$ 1 [mm] \equiv [/mm] 0 $ (mod m) [mm] \gdw [/mm] $m = 1$ .
Also gibt es keinen Faktor $m > 1$, der beide Terme teilt. Also ist der Bruch nicht kürzbar.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:54 Mo 20.07.2015 | | Autor: | tobit09 |
> Wie wäre es mit einem Widerspruchsbeweis stattdessen?
>
> Angenommen es gebe einen gemeinem Faktor [mm]m > 1[/mm], der beide
> Terme teilt.
>
> Dann muss gelten:
>
> [mm](21n+4) \equiv 0[/mm] (mod m)
> [mm](14n+3) \equiv 0[/mm] (mod m)
>
> Dann muss nach gelten:
>
> [mm](2*(21n+4)) \equiv 2*0[/mm] (mod m)
> [mm](3*(14n+3)) \equiv 3*0[/mm] (mod m)
>
> [mm](42n+8) \equiv 0[/mm] (mod m)
> [mm](42n+9) \equiv 0[/mm] (mod m)
>
> Und daraus wiederum:
>
> [mm]((42n+9) - (42n+8)) \equiv (0-0)[/mm] (mod m)
>
> [mm]1 \equiv 0[/mm] (mod m) [mm]\gdw[/mm] [mm]m = 1[/mm] .
>
> Also gibt es keinen Faktor [mm]m > 1[/mm], der beide Terme teilt.
> Also ist der Bruch nicht kürzbar.
Sehr schön! ![[ok]](/images/smileys/ok.gif "[ok]")
|
|
|
| |
|
und warum nicht m>0 ?
hängt das damit zusammen, das beim teilen eh alles >1 alles <1 nur invers darstellt?
|
|
|
| |
|
> und warum nicht m>0 ?
Wenn wir zeigen wollen, dass ein Bruch [mm] $\frac{a}{b}$ [/mm] nicht kürzbar ist, heißt das, dass der größte gemeinsame Teiler von $a$ und $b$, gcd($a$, $b$), gleich 1 ist.
Zum Beispiel: [mm] $\frac{2}{4}$ [/mm] ist noch weiter kürzbar, weil der gcd(2, 4) = 2. Man kann also beide Zahlen noch durch die Zahl 2 dividieren.
Hingegen ist [mm] $\frac{1}{2}$ [/mm] nicht weiter kürzbar, da 1 und 2 nur noch die Zahl 1 als geimeinsamen Teiler haben. Aber einen Bruch mit 1 zu kürzen ist sinnlos, da sich an dem Bruch selbst dadurch nichts ändert.
Wenn es also eine Zahl $m$ gebe, die den Zähler und den Nenner gleichzeitig teilt UND größer als 1 ist, dann ist der Bruch kürzbar. Gleichheit mit 1 funktioniert immer.
|
|
|
| |
|
meine frage ziehlte auf 0<m<1 ab
|
|
|
| |
|
$m$ ist ein Teiler einer Zahl und Teiler sind nur ganze Zahlen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:13 Di 21.07.2015 | | Autor: | M.Rex |
Hallo
Wenn eine Zahl z ein Teiler einer anderen Zahl z ist, gibt es ein [mm] n\in\IN [/mm] für die gilt [mm] $z=n\cdot [/mm] t$
Das die Zahl n aus den natürlichen Zahlen ist, ist wichtig, da ohne diese Einschränkung jede Zahl ein Teiler von jeder anderen Zahl wäre, da in [mm] \IR [/mm] die Gleichung [mm] $z=n\cdot [/mm] t$ immer nach n auflösbar ist.
Marius
|
|
|
|
