PygoscelisPapua 
BlackBoarder
Dabei seit: 20.12.2003
Beiträge: 1.309
Herkunft: Kiel, Schleswig-Holstein, Germany
 |
|
| Euklid und Bezout |
|
Tja, ich hab in Mahte ein Problem. Und zwar gehen wir in Mathe grad die Mengenlehre durch, haben Restklassen gemach und dann Gruppen und sind jetzt bei Restklassengruppen angekommen. Sowohl Restklassen als auch Gruppen hab ich (eigentlich) garkeine Probleme mit...
Für Restklassengruppen hatten wir dann jedoch einen Satz, der besagt:
(Z/m\{[0]m},o) ist genau dann eine Gruppe, wenn m Primzahl ist.
Und um dies zu Zeigen sind wir dann wie folgt vorgegangen:
Knackpunkt ist das finden des Multiplikativen Inversen, so das gilt:
[a*]m o [a]m=[1]m
Dazu haben wir als erstes den Satz von Euklid kennen gelernt, um den ggT von zwei Zahlen zu errechnen:
Seien a,b€|N beliegib und q,r€|N so gewählt, dass
a=q*b+r, 0<=r<b (zwischen 0 und r steht ein Kleiner-Gleich 
)
Dann gilt:
gT(a,b) = gT(b,r)
Das haben wir dann bewiesen, der beweis ist recht einfach und dann haben wir damit gerechnet - auch die Rechnung versteh ich. Aber da wir sie für den zweiten Satz brauchen, schreib ich sie hier nochmal auf:
ggT(1547,560)
1547=2*560+427
560=1*427+133
427=3*133+28
133=4*28+21
28=1*21+7
21=9*7+0
=> ggT(1547,560)=7
So und dann kommt der blöde Satz von Bezout:
Seien a,b€|N beliebige Zahlen, Dann gibt es Zahlen a*,b*€Z
axa* + bxb* = ggT(a,b)
[Anmerkung: das x steht für den Malpunkt - lässt sich hier schlecht darstellen]
Gut, ist so eigentlich auch klar - wenn man zwei Zahlen hat, und eine dritte darauß erzeugen möchte, muss man beide Zahlen mit einem bestimmten Faktor multiplizieren, und die Ergebnisse Addieren und hat dann die dritte Zahl daraus erzeugt. Mehr steht da im Prinzip nicht.
Jetzt haben wir das auf usere Rechnung von oben "angewandt" und dabei ist das hier rausgekommen:
Falls ggT(a,b)=1
[a*]b o [a]b = [1]b
a*,b*€Z
a*x1547+b*x560=7
Berechnung von a* und b* mit dem Euklidischen Altorithmus:
ggT(1547,560)=7
7=28-1*21
7=28-1*(133-4*28)
7=5*28-133
7=5*(427-3*133)-133
7=5*427-16*133
7=5*427-16*(560-427)
7=21*427-16*560
7=21*(1547-2*560)-16*560
7=21*1547-58*560
So und damit sind wir fertig und wissen, dass
1.) 7=21*1547-58*560 die kleinste Lösung ist und
2.) man weitere beliebige Lösungen durch Addition errechnen kann.
Auch das ist mir noch klar, jetzt haben wir den Satz von Bezout:
a*xa+b*xb=ggT(a,b) dort stehen.
Allerdings verstehe ich den zweiten Rechnungsblock nicht. Wie kommt man auf die Zahlen? Unser Professor hat immer gesagt, man wendet den Euklidischen Algorithmus rückwärts an - und für die erste Zeile versteh ich das sogar:
Wir haben bei der ggT-Errechnung als letztes:
28=1*21+7 und 21=9*7+0
Und haben jetzt
7=28-1*21
Aber ab dann verlässt mich alles Verständnis für die Mathematik. Ich weiß nicht, wann man warum wo welche Zahl durch eine Andere ersetzt, und woher man sich diese aus der Hinrechnung zum ggT hohlt, und warum dann diese genommen wird, und keine Andere - und woran ich sehe, wann ich was wo Zusammenfassen darf und wann es als Mathematischer Ausruck so stehen bleiben sollte. Kann mir da jemand helfen?
__________________
There are only two kinds of programming languages: those people always bitch about and those nobody uses.
(Bjarne Stroustrup)
*
Moving on to pastures new
GPG Key
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von PygoscelisPapua: 19.06.2006 11:43.
|
|
