Knobelaufgabe Algebra und Zahlentheorie

Neue Frage »

Studi23 Auf diesen Beitrag antworten »
Knobelaufgabe Algebra und Zahlentheorie
Ich knobel seit einiger Zeit an einer Aufgabe und komme nicht weiter. Hier ist sie erstmal:

Angenommen es gäbe nur noch 161er Euro Scheine und 190er Euro Scheine, keine Münzen oder anderes. Wie kann ich damit etwas zu 1 Euro bezahlen ohne, dass ich mit Karte bezahle oder noch etwas dazu kaufe?


Ich hab mir überlegt, dass es ja eine Zahl x geben muss, die durch 161, 190 oder eine Kombination daraus teilbar ist. x-1 muss dann aber auch durch 161, 190 oder eine Kombination teilbar sein. Und da liegt mein Knackpunkt wo ich nicht weiter komme. Ich hab schon versucht Gleichungen aufzustellen, hab das kgV gebildet, aber seh noch nicht wie es weiter gehen könnte.

Ich wär über nen kleinen Tipp dankbar, der mir vielleicht etwas weiterhilft. Verratet noch nicht die ganze Lösung, ein bisschen knobeln möcht ich auch noch ;-)
kiste Auf diesen Beitrag antworten »

Hallo,

betrachte den ggt von 161 und 190. Dann gibt es einen schönen Satz zum ggt smile
 
 
Studi23 Auf diesen Beitrag antworten »

Also, der ggT(161, 191) ist 1.

Jetzt hab ich mich auf die Suche nach nem hilfreichen Satz gemacht. Wenn ich nen ggT von 1 habe, dann ex. x_0 und y_0 mit x_0*a+y_0*b = 1, es gilt also

(161,190) = x_0*161+y_0*190

Hm... das hilft mir noch nicht wirklich...
kiste Auf diesen Beitrag antworten »

genau, das ganze ist bekannt als Lemma von Bezout. Die Bezout-Koeffizienten (x0,y0) berechnet man mit Hilfe des euklidischen Algorithmus. Wenn dir das nichts sagt kannst du ja mal bei Wikipedia dazu nachschauen.
Studi23 Auf diesen Beitrag antworten »

Habs geschafft!!! Vielen Dank! smile

Die gleiche Aufgabe soll ich noch für die Zahlen 190 und 209 lösen. Da ist das kgV 19. Hmm... wie geh ich denn hier vor?
kiste Auf diesen Beitrag antworten »

Hallo, meiner Meinung nach ist dies nicht möglich. Die Gleichung


also
.
Mit ein bisschen Gruppentheorie kannst du jetzt zeigen das die Gleichung nicht lösbar ist
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »