| Autor |
Beitrag |
    
Simone
| | Veröffentlicht am Montag, den 17. Dezember, 2001 - 09:33: | 
|
Folgende Aufgabe macht mir Probleme:
Seien a,b,c Elemente aus N. Man zeige, dass die Gleichung ax+by=c genau dann eine Lösung (x0,y0) mit x0,y0 Element Z hat, falls c ein Vielfaches von ggT(a,b) ist.
Wer kann mir helfen? |
cornelius
| | Veröffentlicht am Dienstag, den 18. Dezember, 2001 - 11:33: |
|
so, mir fällt dazu spontan ein:
eine richtung des beweises:
sei (x0,y0) eine lösung und sei d:=ggt(a,b). dann gilt d|a und d|b und damit natürlich auch d|ax und d|ay, also auch d|ax+ay => es muss gelten d|c => c ist vielfaches von d.
andere richtung:
wieder ist d:=ggt(a,b) und nun gelte c=d*e mit geeignetem e. also kann man ja nun die gleichung durch d teilen und erhält:
(a/d)x+(b/d)y=e, dabei ist nun ggt((a/d),(b/d))=1, da d gerade der ggt von a und b war.
nun betrachten wir die gleichung mx+ny=1 - für die gibt es immer eine lösung, wenn ggt(m,n)=1 ist (ist das einfach einzusehen? ich denke schon - zb beim verfahren um den ggt zu berechnen, kommt auf das x und y, sollte also für jede gleichung mx+ny=ggt(m,n) genauso sein)
jedenfalls nimmst du nun m=a/d und n=b/d und mußt nur noch die gleichung mit e multiplizieren um deine gesuchte lösung zu bekommen.
also wenn (x1,y1) die lösung für (a/d)x+(b/d)y=1 ist, dann ist (x1*e,y1*e) die lösung für (a/d)x+(b/d)y=e, also auch für ax+by=de=c
hoffe, geholfen zu haben
gruß, cornelius |
|
