Beweis für Gültigkeit folg. Formel für ggt |
08.12.2008, 18:56 | Kitty | Auf diesen Beitrag antworten » | ||
Beweis für Gültigkeit folg. Formel für ggt man beweise , dass folgende Formel gilt: ggt( x^{a} -1 , x^{b} -1)= x^{ggt(a,b)} -1 durch Einsetzen von Zahlen habe ich es ausprobiert - stimmt. aber wie kann ich es durch umformen allg. beweisen? Bin dankbar für jeden Start-tipp! LG Kitty |
||||
08.12.2008, 19:18 | AD | Auf diesen Beitrag antworten » | ||
O.B.d.A. ist . Dann würde ich die Behauptung durch Induktion über zeigen. |
||||
08.12.2008, 19:22 | Kitty | Auf diesen Beitrag antworten » | ||
Bitte um einen Anfang, da mir der im Moment völlig unklar ist |
||||
08.12.2008, 19:24 | AD | Auf diesen Beitrag antworten » | ||
Den (Induktions-)Anfang kannst du selbst. Im Induktionsschritt kann man so argumentieren: Im Fall stimmt die Aussage. Für ist hingegen Jetzt kann man auf die Induktionsvoraussetzung zurückgreifen... Wenn ich noch mehr verrate, steht der Beweis da. |
||||
08.12.2008, 19:34 | Kitty | Auf diesen Beitrag antworten » | ||
Gehe ich richtig in der Annahme, dass der mittlere Teil dem euklidischen Algorithmus entspringt? Die Induktionsvoraussetzung ist doch meine Ausgangsformel ? |
||||
08.12.2008, 19:53 | AD | Auf diesen Beitrag antworten » | ||
Richtig, hier wird genutzt, dass für beliebige ganze Zahlen gilt. Das ist genau die Eigenschaft, auf der der euklidischen Algorithmus beruht. |
||||
Anzeige | ||||
|
||||
08.12.2008, 19:54 | Kitty | Auf diesen Beitrag antworten » | ||
Sorry, aber ich habe bereits im Induktionsanfang Probleme. Wenn ich mit x= 0 anfange .....`? zu viele Variablen, was mache ich mit a,b ? |
||||
08.12.2008, 19:59 | AD | Auf diesen Beitrag antworten » | ||
Ich hab gesagt: Induktion über !!! Nicht über oder . Wobei allerdings im Induktionsanfang für nicht sehr viele Möglichkeiten bestehen angesichts des obigen o.B.d.A.
Diese Formulierung wird dem Wesen der Vollständigen Induktion nicht gerecht. Wenn ich geschrieben habe "Induktionsschluss " statt oder , dann habe ich es auch so gemeint, da solltest du vielleicht mal ein bisschen drüber nachdenken. |
||||
08.12.2008, 20:17 | Kitty | Auf diesen Beitrag antworten » | ||
Tut mir leid, aber bisher ist mir noch keine Aufgabe dieser Art in die Quere gekommen. Also bitte nicht böse sein, wenn ich mich etwas dämlich anstelle. Ich gehe jetzt also davon aus, dass a\leq b ist. Der Induktionsanfang muss bei min. b=2 liegen. Folglich wäre a=1 und x wähle ich wie? |
||||
08.12.2008, 20:26 | AD | Auf diesen Beitrag antworten » | ||
wird nicht angerührt: Alle Betrachtungen haben für beliebige zu gelten! Und den Induktionsanfang sehe ich eher bei . Wenn dir diese Art Induktion nicht geheuer ist, dann kannst du das auch als indirekten Beweis formulieren:
... bis zum Widerspruch. |
||||
08.12.2008, 21:11 | Kitty | Auf diesen Beitrag antworten » | ||
Vielleicht habe ich jetzt nicht das getan, was du von mir erwartest, also bitte nicht die Haare raufen. Folgendes habe ich mir überlegt: wenn a=b ggT(x^{b}-1, x^{b}-1)= x^{ggT(b,b)}-1 ergibt auf beiden Seiten x^{b}-1= x^{b}-1 die Gleichheit ist also gegeben. Jetzt nehme ich an, dass die Behauptung der Gleichheit falsch ist: ggT(x^{a}-1, x^{b}-1) sei kleiner x^{ggt(a,b)}-1 für b setzte ich 1 entsteht somit ggT(x^{a}-1, x^{1}-1) sei kleiner x^{ggt(a,1)}-1 also ggt( n^a-1, n^1-1) sei kleiner n^ggT ( a,1) -1 " " sei kleiner n -1 ergibt sich da nicht ein Widerspruch? |
||||
08.12.2008, 22:43 | AD | Auf diesen Beitrag antworten » | ||
Im Grunde genommen richtig - allerdings ist das dann nur ein Widerspruch für den Fall b=1, nicht allgemein. P.S.: Wäre schön, wenn du das LaTeX adaptieren könntest - deine Formeln brennen in den Augen. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|