Mathematische Beweise - Wie geht man da ran?

[DarkDragon]

Also ich hab erstmal die Übung gemacht die pflicht ist.



q.e.d.

Daraus kann man eigentlich auch gleich das rechtstotal und linkseindeutig schließen. Aber ich glaub das ist noch recht schwammig oder nicht?

[DarkDragon]

Hallo,

Ich hab wieder mal ein Problem damit. Nach einigen Stunden nachdenken komm ich immernoch nicht weiter. Wir sollen die funktionalität des Euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers Beweisen.

Das hier habe ich bereits:

Code: Alles auswählen

Fallunterscheidung bei ggT(m, n) und r = m mod n:
r = 0
==> n ist ggT, da es keinen größeren Teiler für n als n selbst gibt und n | m.

r != 0
==> ggT(n, r) ist ggT, denn ...

Aber ich verstehe einfach nicht warum der letzte Fall eigentlich gilt. Ich weiß dass es gilt, aber nicht warum.

Ich hätte in so einem Fall einfach k = 1 bis n durchgetestet und den letzten Wert, der m und n teilt genommen.
Ich habe es auch schon über das abziehen versucht irgendwie zu beweisen, aber ich lande immer in einer Sackgasse:

Code: Alles auswählen

r = m mod n = m - n * k ; n * (k + 1) > m, n * k < m, k in N

Warum muss ich dann nurnoch mit n und ausgerechnet dem Divisionsrest suchen?

[Kaeru Gaman]

mal ganz ins blaue....

check mal die alte Faustregel für den ggT...
(summe aller gemeinsamen primfaktorpotenzen mit dem niedrigsten exponenten oder irgendwie so was)

dieses
> dann nurnoch mit n und ausgerechnet dem Divisionsrest suchen
könnte mit diesen primfaktorgeschichten zusammenhängen...

[DarkDragon]

mal ganz ins blaue....

check mal die alte Faustregel für den ggT...
(summe aller gemeinsamen primfaktorpotenzen mit dem niedrigsten exponenten oder irgendwie so was)

dieses
> dann nurnoch mit n und ausgerechnet dem Divisionsrest suchen
könnte mit diesen primfaktorgeschichten zusammenhängen...

Euh, 6. oder 7. Klasse. Ich werd glaub schon vergesslich. Graue Haare hab ich ja schon. Danke, aber für heute mach ich schluss.

[EDIT]
Hab doch noch etwas weitergemacht:
m = p * q
n = p * r
p = primfaktoren die gemeinsam sind
q, r = unterschiedliche primfaktoren

m / n = q / r
m mod n = m - int(m / n) * n = p * q - int(q / r) * p * r

Doch jetzt weiß ich wieder nicht weiter. Ich kanns noch zu einer riesigen Kette umformen, aber wirklich weiterbringen tut mich das leider nicht.

[gnasen]

hmm genau bei dem Beweis hat unser Prof letzte Stunde aufgehört, weil die Zeit um war.
Nach der nächsten Analysis Sitzung (Freitag) kann ich dir da vllt was zu erzählen.

[DarkDragon]

hmm genau bei dem Beweis hat unser Prof letzte Stunde aufgehört, weil die Zeit um war.
Nach der nächsten Analysis Sitzung (Freitag) kann ich dir da vllt was zu erzählen.

Das wär nicht schlecht, danke.

Aber erkennt man jetzt wenigstens wo ich immer hänge bei den Beweisen?

[alter Mann]

geg.: m,n
r=mod(m,n)
x=int(m/n)
p=GGT(m,n)

m=x*n+r

Wenn die Summe m den Teiler p hat und ein Summand (x*n) den Teiler p hat, dann muss auch der Zweite Summand r den Teiler p haben.

[DarkDragon]

geg.: m,n
r=mod(m,n)
x=int(m/n)
p=GGT(m,n)

m=x*n+r

Wenn die Summe m den Teiler p hat und ein Summand (x*n) den Teiler p hat, dann muss auch der Zweite Summand r den Teiler p haben.

Hmm echt? Gibts dazu ein Mathematisches Gesetz?

[EDIT]
Achja stimmt, bei Bruchrechnung kann das gleiche gekürzt werden von Summanden, durchs Ausfaktorisieren.

Danke, das hilft mir sehr. Aber wie merkt man sich denn das ganze Zeug wenn man so sehr vergesslich ist?

[alter Mann]

Vergesslich ist man ja nur bei Sachen, die einen nicht besonders interessieren. Also vergessen. Und wenn man es mal wieder braucht, jemanden fragen, oder wissen, wo man nachschlagen kann. Beweise führen braucht man im späteren (Berufs-)Leben so gut wie nie (wenn man nich Mathematikforschung o.ä betreibt).

[Karl]

Hallo,

der Beweis zur Injektivität unter Komposition lässt sich über die Definition der Injektivität selbst beweisen:

all(y1,y2) (y1=y2=>x1=x2)

Hier setzt man die beiden Funktion nacheinander ein. Fertig.

Wichtige Beweisverfahren sind

vollständige Induktion (gerade bei Mengen)
direkter Beweis
indirekter Beweis

Beim indirekten Beweis darf man etwas zusätzlich etwas annehmen (dessen Unrichtigkeit man durch Widerspruch zeigt).

Wichtiges Hilfsmittel ist weiterhin die Kontrapositionsregel:

A=>B äquivalent zu -B=>-A

Mengen werden meist über eine charakteristische Funktion definiert (jedenfalls in der theoretischen Informatik).

Das Problem bei Beweis ist, dass man zum Teil "kreativ" sein muss.

Gruß

Der Karl