Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » ggT(k, n) = ggT(k, n+rk)

ggT(k, n) = ggT(k, n+rk)

Universität / Fachhochschule

Teilbarkeit

Tags: ggT bestimmen, Teilbarkeit

lila13 aktiv_icon

14:56 Uhr, 23.08.2014

Hallo, könnte mir vielleicht jemand von euch bei folgender Aufgabe helfen?

Seien

r, k, n \in ℕ

.
Beweisen Sie, dass

g g T (n, k) = g g T (k, n + r k)

ist.

Mein Ansatz:

Seien

r, k, n \in ℕ

. Sei

d = g g T (n, k)

und

d' = g g T (k, n + r k)

.

Zunächst zeigen wir

d | d' :

d | k

und

d | n

gilt mit den Rechenregeln für Teiler, dass

d | (n + r k),

denn

r k

ist ein Vielfaches von

k

. Es folgt

d | d'

.

Zeigen wir nun

d' | d

. Es gilt

d' | (n + r k),

also

d' | n

und

d' | r k

. Da d'=ggT(k,

n + r k)

gilt auch

d' | k

und daher auch

r k,

denn

r k

ist ein Vielfaches von

k

. Somit gilt

d' | k

und

d' | n,

also

d' | d

.

Da sowohl

d

und

d'

positiv sind, gilt

d = d'

.

Meine Frage: Darf ich in meinem Beweis argumentieren, dass aus

d' | (n + r k),

dass daraus

d' | n

und

d' | r k

gilt oder bin ich da auf dem Holzweg??

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

michaL aktiv_icon

15:02 Uhr, 23.08.2014

Hallo,

mach es dir einfacher, beweise den Fall für

r = 1

. Für

r > 1

folgt die Aussage dann induktiv!

Mfg Michael

EDIT: Zu deiner konkreten Frage: Aus

d ʹ ∣ n + r k

und

d ʹ ∣ k

(

d ʹ := ggT (k, n + r k)

) folgt natürlich auch

d ʹ ∣ n

.
Aber nur so wird ein Schuh draus.

Mfg Michael

lila13 aktiv_icon

15:28 Uhr, 23.08.2014

Mit Induktion:

Sei

d = g g T (n, k)

und sei

r = 1

. Mit den Rechenregeln für Teiler gilt dann auch

d | (n + r k)

.
Nehmen wir nun an, dass

r > 1

und die Aussage bereits für ein

r \in ℕ

bewiesen ist.
Für

r + 1

gilt dann

n + (r + 1) k = n + r k + k

. Nach Voraussetzung gilt

d | n

und

d | k

. Mit Induktionsannahme gilt auch

d | r k

. Mit den Rechenregeln für Teiler sowie dem Prinzip der vollständigen Induktion folgt dann, dass

d = g g T (n, k) = g g T (k, n + r k)

ist.

Stimmt das so?

michaL aktiv_icon

17:02 Uhr, 23.08.2014

Hallo,

> Stimmt das so?

Na, ja, so halbwegs.

Einmal schreibst du d|(n+rk), wobei es doch sicher

d = ggT (k, n + r k)

heißen soll.
Außerdem: Wenn es eine Regel ist (etwa so:

ggT (a, b) = ggT (a, a + b)

), dann ist der Anfang eben genau diese Regel.

Der Induktionsschluss müsste auch ein bisschen sauberer formuliert werden. Das sähe etwa so aus:

ggT (a, b) = ggT (a, a + b)

nach Regel.

ggT (a, a + b) = ggT (a, a + (a + b)) = ggT (a, 2 a + b)

nach Regel usw.

Mfg Michael

EDIT: Tippfehler korrigiert

lila13 aktiv_icon

17:31 Uhr, 23.08.2014

Vielen Dank für die Geduld und die hilfreichen Erklärungen!!

Versuch der Umformulierung:

g g T (a, a + b) = g g T (a, b + (r b + a)) = g g T (a, (r + 1) b + a)

.

PS: Sollte es in Ihrer Anweisung nicht

2 a + b

heißen, anstatt

a + 2 b

michaL aktiv_icon

17:37 Uhr, 23.08.2014

Hallo,

> PS: Sollte es in Ihrer Anweisung nicht 2a+b heißen, anstatt a+2b?

Doch, sollte es. Habe es korrigiert. Danke für den Hinweis.
Und: bitte verwende das vertraulichere "du". Ich komme mir auch so schon alt genug vor.

Deine "Formulierung" ist (formeltechnisch) in Ordnung. Erläutere, warum die beiden Gleichheitszeichen gelten. Wenn du das hast, ist die Induktion - hm - vollständig. :-)

Mfg Michael

lila13 aktiv_icon

18:20 Uhr, 23.08.2014

Meiner Ansicht nach gelten die Gleichheitszeichen aufgrund der Regel.

Vielen, vielen lieben Dank für die großartige Hilfe und Geduld!! Danke!!

1181183

1181157

	Status: nicht eingeloggt	Noch nicht registriert?