ggT(2^a-1,2^b-1)

Neue Frage »

1379 Auf diesen Beitrag antworten »
ggT(2^a-1,2^b-1)
Meine Frage:
Ich muss den ggT(2^a-1,2^b-1) in Abhängigkeit vom ggT(a,b) zeigen.
Die Lösung sollte sein ggT(2^a-1,2^b-1)=2^ggT(a,b)-1



Meine Ideen:
Die Lösung sollte sein ggT(2^a-1,2^b-1)=2^ggT(a,b)-1

Ich habe schon zeigen können, dass 2^ggt(a,b)-1 die beiden Terme teilt.
Zu zeigen bleibt aber dass es der GRÖSSTE gemeinsame Teiler ist also dass für alle x aus Z : x|2^a-1 und x|2^b-1 gilt x|2^ggT(a,b)-1

Kann mir jemand helfen?
1379 Auf diesen Beitrag antworten »
RE: ggT(2^a-1,2^b-1)
nochmal schöner:
zu zeigen ist
HAL 9000 Auf diesen Beitrag antworten »

Wegen der Symmetrie reicht es ja, die Aussage für o.B.d.A zu zeigen. Vermutlich hast du ja auch schon sowas wie die auf basierende Hilfsaussage



nachgewiesen, auf deren Grundlage man nun den anstehenden Beweis "organisieren" kann.


Ich würde das in einen indirekten Beweis packen:

Für sowie gilt die Aussage, wie man durch Einsetzen sieht. Angenommen, die Aussage gilt nicht für alle mit , dann gibt es unter allen Paaren , für die die Aussage nicht gilt, ein Paar mit minimalen , nennen wir es . D.h. es gilt dann sowie



sowie

für alle mit .

Offenbar kann man aus (1) mit Hilfe von (*) leicht einen Widerspruch zu (2) folgern.
1379 Auf diesen Beitrag antworten »

danke das klingt auf jeden fall mal sehr einleuchtend, trotzdem steh ich irgendwie noch total auf der leitung.

erstens ist mir die Umformung



nicht ganz klar und ich sehe einfach nicht, wie ich den Widerspruch zeigen kann...
RavenOnJ Auf diesen Beitrag antworten »

und sind teilerfremd.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von 1379
ich sehe einfach nicht, wie ich den Widerspruch zeigen kann...

Mit (*) bekommt man ja auch



zudem ist . Damit folgt aus (1)

,

was aber wegen und im Widerspruch zu (2) steht, d.h. es ist ein Widerspruch zur "Minimalität" des Gegenbeispiels .
 
 
1379 Auf diesen Beitrag antworten »

Achja, ist klar!

Vielen Dank!!!
RavenOnJ Auf diesen Beitrag antworten »

Der Beweis mit dem Widerspruch ist elegant.

Es gibt noch einen anderen, weniger eleganten Beweis über den Euklidischen Algorithmus.

Sei und . Da und teilerfemd, gilt



und deswegen

,

Nun kann man entsprechend dem Euklidischen Algorithmus auf immer kleinere Reste kommen und damit folgern, dass mit dem letzten Rest und folgt:

Neue Frage »
Antworten »



Verwandte Themen