Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » größter gemeinsamer Teiler 2

größter gemeinsamer Teiler 2

Universität / Fachhochschule

Teilbarkeit

Tags: diophantisch, ggT, Linearkombination, Teilbarkeit

Wunderblume aktiv_icon

14:04 Uhr, 27.03.2012

Hallo liebe Leute! Ich hab' ein weiteres Problem.

1)

Es gibt Zahlen

m_{1}, . .

, m_{n} \in ℤ,

sodaß sich der größte gemeinsame Teiler der ganzen Zahlrn

a_{1}, . .

, a_{n},

nicht alle gleich

0,

als Linearkombination schreiben lässt:

(a_{1}, a_{2}, . .

, a_{n}) = m_{1} \cdot a_{1} + . .

+ m_{n} \cdot a_{n}

2)

Die lineare diophantische Gleichung in

n

Variablen

a_{1} \cdot x_{1} + . .

+ a_{n} \cdot x_{n} = c

ist lösbar genau dann, wenn die bedingung

(a_{1}, a_{2}, . .

, a_{n})

teilt

c

erfüllt ist.

Beweisen Sie diese beiden Behauptungen.

Ich komm' mit dem nicht zurecht, also würd ich eure hilfe brauchen.
Dankee

Lg

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

Hierzu passend bei OnlineMathe:

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

Rechnen mit Klammern
Teilbarkeit natürlicher Zahlen

weisbrot aktiv_icon

17:50 Uhr, 27.03.2012

1. folgt induktiv mit dem lemma von bezout.
2. "

\Rightarrow

\sum x_{i} \cdot a_{i} = c

ist lösbar, also gibt es ganzen zahlen

m_{i}

sodass

\sum m_{i} \cdot a_{i} = c,

und da

g g T (a_{i})

alle

a_{i}

teilt, teilt er auch

\sum m_{i} \cdot a_{i},

also

c

.
"

\Leftarrow

(a_{i}) | c,

also

\exists p : (a_{i}) \cdot p = c

. wegen 1. gibt es

m_{i}

sodass

(a_{i}) = \sum m_{i} \cdot a_{i};

also:

c = \sum a_{i} \cdot (p \cdot m_{i}) □

Wunderblume aktiv_icon

18:02 Uhr, 27.03.2012

Und ich kann das Lemma von Bézout für mein Beispiel so umformen?
und bei

b)

ist das somit bewiesen?
Auf jeden Fall danke für die Hilfe, hast mir echt weitergeholfen .

weisbrot aktiv_icon

18:11 Uhr, 27.03.2012

ja das sollte funktionieren wenn du

v

. induktion über die anzahl der

a_{i}

machst. was ist

b)

Wunderblume aktiv_icon

18:23 Uhr, 27.03.2012

Hoppla

b) = 2) .

. sorry.

Also bei

1)

hab ich jetzt:

Unter allen Zahlen

x = m_{1} \cdot a_{1} + . .

+ m_{n} \cdot a_{n}

mit

m_{1}, . .

, m_{n} \in ℤ

gibt es sicher auch solche, die positiv und

\neq 0

sind. Sei

d = m_{1} \cdot a_{1} + . .

+ m_{n} \cdot a_{n}

die kleinste unter diesen. Da ggT(a_1,

. .

, a_{n})

alle

a_{i}

teilt, für

i = 1, ..., n,

teilt ggT(a_1,

. .

, a_{n})

auch

d

. Ist

d = 1,

ist auch ggT(a_1,

. .

, a_{n}) = 1

und die Aussage bewiesen. Für den Fall

d > 1

zeigen wir, dass

d

auch ein Teiler von

a_{1}, . .

, a_{n}

ist. Die Division mit Rest liefert uns eine Darstellung zB

a_{1} = q \cdot d + r,

wobei

0 \leq r < d

ist. Setzt man für

d

die Darstellung

m_{1} \cdot a_{1} + . .

+ m_{n} \cdot a_{n}

ein und löst die Gleichung nach

r

auf, so erhält man

r = (1 - m_{1} \cdot q) \cdot a_{1} + . .

+ (1 - m_{n} \cdot q) \cdot a_{n}

.
Wegen der Minimalität von

d

muss

r = 0

sein, also ist

d

ein Teiler von

a_{1}

. Entsprechend gilt auch, dass

d

ein Teiler von

(a_{2}, . .

, a_{n})

ist und somit gilt

d \leq

ggT

(a_{1}, . .

, a_{n})

. Vorher hatten wir schon gesehen, dass ggT

(a_{1}, ...

, a_{n})

ein Teiler von

d

ist. Also gilt

d =

ggT(a_1,

. .

, a_{n})

.

Das hab ich jetzt aufgeschrieben, stimmt das so?

weisbrot aktiv_icon

18:45 Uhr, 27.03.2012

ich meinte zwar nicht, dass du den wikipediaartikel ändern sollst (sondern das resultat für zwei zahlen durch

v

. ind. auf

n

zahlen erweitern, das ginge leichter (vorausgesetzt du darfst das lemma von bezout überhaupt schon benutzen)), aber gut. du hast allerdings im letzten satz des 1. abschnitts einen kleinen fehler: umgeformt erhälts du

r = (1 - m_{1} \cdot q) \cdot a_{1} + (- m_{2} \cdot q) \cdot a_{2} + . .

+ (- m_{n} \cdot q) \cdot a_{n}

.
hauptsache du hast auch verstanden was da abgeht. lg

Wunderblume aktiv_icon

18:50 Uhr, 27.03.2012

ja also verstanden hab' ich es, und ich hab mir halt gedacht, dass wenn ich das ändere, dass es auch stimmt, und nachdem ich es nachvollziehen konnte...

lg

988983

988801

	Status: nicht eingeloggt	Noch nicht registriert?