Lösung d. Gleichung: 6=a30+b42 < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:20 Mo 12.05.2008 | | Autor: | Casy |
| Aufgabe | Finden Sie ganze Zahlen a, [mm] b\in\IZ, [/mm] sodass 6=a*30+b*42 ist, und zwar ohne Raten / Ausprobieren!
HINWEIS: Satz aus Skript: Seien p, q zwei positive ganze Zahlen und [mm] d\in\IN [/mm] ihr größter gemeinsamer Teiler. Dann gibt es a, [mm] b\in\IZ, [/mm] sodass
ap+bq=d ist.
Der Beweis des Satzes soll zur Hilfe genommen werden. |
Hallo!
Ich habe einen Ansatz, komme aber ab einem gewissen Punkt nicht weiter:
p und q aus dem Satu sind hier p=42 und q=30, d=6.
Aus dem Beweis habe ich:
q lässt sich mit Rest durch p teilen, d.h. es gibt z, [mm] r\in\IZ; 0\lez, [/mm] r mit r<p:
q=pz+r (...OK, kann ich halbwegs nachvollziehen)
Außerdem:
d teilt p undq, also auch r=q-pz, also ist d auch Teiler von r.
Eingesetzt: r=30-42z.
Also setze ich das in die Behauptung ein und erhalte:
6 = xr+y42 mit [mm] x,y\in\IZ
[/mm]
[mm] \gdw [/mm] 6 = x(30-42z)+y42
[mm] \gdw [/mm] 6 = x30-x42z+y42
[mm] \gdw [/mm] 6 = x30+(y-xz)42
Das entspricht der Behauptung mit a=x und b=y-xz.
Jetzt habe ich, wie gefordert, den Beweis verwendet, kann aber damit nichts anfangen, da ich viele Unbekannte habe, aber viele zu wenige Gleichungen, in die ich einsetzen kann, um a und b zu erhalten.
Ein Versuch war (obiges verwendet):
6 = xr+y42
[mm] \gdw [/mm] 6 = ar+(b+az)42, da b=y-xz und a=x
[mm] \gdw [/mm] 6 = a(30-42z)+(b+az)42
[mm] \gdw [/mm] 6 = a(30-42z)+(1/7-5/7a+az)42 (1/7-5/7a=b, aus Gleichung in Aufgabenstellung)
[mm] \gdw [/mm] 6 = a(30-42z)+6-a(-30+42z)
....so habe ich immerhin eine Gleichung mit zwei Unbekannten.
Leider komme ich hier überhaupt nicht weiter, ich bin auch nicht überzeugt, dass der Ansatz stimmt!
Es wäre toll, wenn mir jemand auf die Sprümge helfen könnte.
Danke und Gruß!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:48 Mo 12.05.2008 | | Autor: | leduart |
Hallo
Ich machs dir an nem anderen beispiel vor: 9=a*45+b*27
45=1*27+18
27=1*18+9
18=2*9+0
jetzt rückwärts: 9=27-1*18, (18=45-1*27 einsetzen )
9=27-1*(45-27)
9=2*27-1*45
d.h. erst zerlegen , bis du bei d bist, dann alles rückwärts, bis du bei den Ausgangswerten bist.
Dass die Zerlegung hier in nur 3 Schritten geht muss nicht sein, das ganze kann natürlich auch mehr als 3 Schritte vorwärts und rückwärts brauchen.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:04 Mo 12.05.2008 | | Autor: | Casy |
Toll!
Habs grad auf dem Papier nachgerechnet, und es funktioniert!
dann komm ich auf6=3*30-2*42.
Andere Frage:
Wie kommt man denn auf Sowas? Auf diese Lösung wäre ich nie alleine gekommen!
Gruß und vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:55 Mo 12.05.2008 | | Autor: | leduart |
Hallo
Das entspricht genau eurem Beweis, du kannst es nachlesen unter "euklidscher Algorithmus!
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:21 Mo 12.05.2008 | | Autor: | Casy |
...ja, das stimmt; wenn ich mir den Beweis nochmal in Ruhe anschaue....
Super, Danke!
|
|
|
|
