Beweis für Gültigkeit folg. Formel für ggt

Neue Frage »

Kitty Auf diesen Beitrag antworten »
Beweis für Gültigkeit folg. Formel für ggt
Hallo,

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
AD Auf diesen Beitrag antworten »

O.B.d.A. ist .

Dann würde ich die Behauptung durch Induktion über zeigen.
Kitty Auf diesen Beitrag antworten »

Bitte um einen Anfang, da mir der im Moment völlig unklar ist
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.
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 ?
AD Auf diesen Beitrag antworten »

Zitat:
Original von Kitty
Gehe ich richtig in der Annahme, dass der mittlere Teil dem euklidischen Algorithmus entspringt?

Richtig, hier wird genutzt, dass



für beliebige ganze Zahlen gilt. Das ist genau die Eigenschaft, auf der der euklidischen Algorithmus beruht.
 
 
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 ?
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.

Zitat:
Original von Kitty
Die Induktionsvoraussetzung ist doch meine Ausgangsformel ?

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.
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?
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:

Zitat:
Angenommen, es gäbe mit o.B.d.A. , so dass die Gleichung in der Behauptung nicht stimmt. Dann gibt es unter all diesen Gegenbeispielen auch eins mit einem kleinsten ...

... bis zum Widerspruch.
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?
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. traurig
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »