Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis durch vollständige Induktion: ggT

Beweis durch vollständige Induktion: ggT

Universität / Fachhochschule

Elementare Zahlentheorie

Teilbarkeit

Tags: Elementare Zahlentheorie, gemeinsam, ggT, größter, Teil, Teilbarkeit

IwiSD aktiv_icon

23:24 Uhr, 01.05.2017

Folgendes soll mittels vollständiger Induktion bewiesen werden:

\forall n, m \in ℕ_{+}

gilt

g g T (2^{n} - 1, 2^{m} - 1) = 2^{g g T (n, m)} - 1

.
Zusätzlich gilt der Hinweis "Verwenden Sie dabei den Euklidischen Algorithmus."

Induktionsvoraussetzung sowie Induktionsanfang habe ich bereits vorliegen. Für den Induktionsschritt habe ich als Ziel folgendes vor Augen:

g g T (2^{g g T (n, m)} - 1, 2^{g g T (n, m)} - 1) = 2^{g g T (n, m)} - 1 * g g T (1, 1) = 2^{g g T (n, m)} - 1

, womit sich der Beweis schließen würde. Leider ist mir, auch mit dem Eudklidischen Algorithmus vor Augen, schleierhaft, wie sich samt Anwendung der IV aus

(2^{n} - 1, 2^{m} - 1) \to (2^{g g T (n, m)} - 1, 2^{g g T (n, m)} - 1)

ergeben soll.

Als Ansätze hatte ich bisher nur die beiden Regeln:

g g T (n, m) = g g T (m - n, n)

und

g g T (n, m) = g g T (m o d (m, n), n)

. Mir ist aber nicht klar, wie mir diese weiterhelfen sollen. Zumal beide Regeln fordern, dass

n \leq m

gilt, was die Voraussetzungen allerdings nicht hergeben.
Weiterhin wäre da noch

g g T (2^{n} - 1, 2^{m} - 1) = g g T ((2 * 2^{n - 1}) - 1, (2 * 2^{m - 1}) - 1)

als Ansatz, der mich aber offensichtlich nicht zum Ziel führt.

Über eure Hilfe freue ich mich sehr!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Rechnen mit Klammern
Teilbarkeit natürlicher Zahlen