Beweis: ggT(a^m-1,a^n-1)=a^(ggT(m,n))-1

Neue Frage »

Tobias94 Auf diesen Beitrag antworten »
Beweis: ggT(a^m-1,a^n-1)=a^(ggT(m,n))-1
Hallo,
ich bräuchte eure Hilfe bei dem im Titel genannten Beweis:

Den "1. Teil" , also a^(ggT(m,n))-1 (=:c) teilt a^m-1 und a^n-1, hab ich schon gezeigt.

Aber beim zweiten Teil, also beim Beweis, dass es der größte gemeinsame Teiler ist habe ich Probleme.
Mein Ansatz, wäre zu zeigen, dass die Ergebnisse der beiden bei Division durch c teilerfremd sind.

ggT(m,n):=d
m=d*l;
n=d*k;
ggT(l,k)=1

Als Ergebnisse erhalte ich: a^(k-1)+a^(k-2)+.......+a+1 bzw. a^(l-1)+a^(l-2)+....+a+1
Jedoch schaffe ich es einfach nicht zu zeigen, dass die beiden keinen gemeinsamen Teiler mehr haben.

Ich hab mir auch schon gedacht die Differenz der beiden zu betrachten, da der gemeinsame Teiler auch diese teilen muss.
Die Differenz ist ja: (o.b.d.a k>=l) a^(k-1)+a^(k-2)+....+a^(l)

Aber mir fällt einfach nicht ein ,wie ich weitermachen kann, daher möchte ich euch um Hilfe bitten.

mfG
HAL 9000 Auf diesen Beitrag antworten »

Für kann man schließen

.

Jetzt kann man so vorgehen wie beim euklidischen Algorithmus. Ich empfinde das aber als etwas schwammig, deswegen bevorzuge ich die indirekte Schlussweise:
    Für sowie gilt die nachzuweisende Behauptung offensichtlich. Angenommen nun, es gäbe mit , so dass die Behauptung nicht gilt. Dann wählen wir unter all diesen Paaren eins mit minimalen . Gemäß (*) können wir dann schließen

    .

    Das steht aber im Widerspruch dazu, dass die Behauptung wegen der Minimalitätseigenschaft von für das Paar gilt!
Tobias94 Auf diesen Beitrag antworten »

Danke für die Antwort.

Leider verstehe ich den letzten Satz und somit den entscheidenden nicht ganz. Warum gilt das durch die Minimalitätseigenschaft von n?


mfG
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Dann wählen wir unter all diesen Paaren eins mit minimalen .

Nochmal ausführlich:

Mit der obigen Gleichungszeile wird logisch geschlossen, dass die Behauptung auch für nicht gilt. Setzen wir nun und , so haben wir damit und damit den gewünschten Widerspruch zur Minimalität des im Bereich der Nicht-Lösungen.

Ein bisschen sollte dir schon klar sein, was das Wesen eines indirekten Beweises ausmacht - einen Logik-Grundkurs mache ich hier nicht. Augenzwinkern
Tobias94 Auf diesen Beitrag antworten »

Danke nochmal für die Antwort, jetzt ist es mir auch klar! :-D

Was einen indirekten Beweis ausmacht weiß ich zwar, ich habe in diesem Fall aber leider nicht erkannt wo der Widerspruch liegt, hab leider einfach falsch gedacht.

mfG
Neue Frage »
Antworten »



Verwandte Themen

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