Frage von Siarzewski, 48

Kann mir jemand bei Euklidischen Algorithmus helfen?

Hallo Leute, ich habe eine Gleichung und zwar: 1066x + 819y = c Ich soll hier angeben, für welches c die Gleichung keine Lösungen in Z hoch 2 besitzt. Gibt es da irgendwelche Regeln oder Formeln?

Danke im voraus.

Siarzewski

Antwort
von ralphdieter, 12

Klammere links den größten gemeinsamen Teiler (GGT) aus:

    t·(ax+by) = c

Klar: c muss ein Vielfaches von t sein, sonst gibt's keine Lösung. Den GGT kannst Du mit dem euklidischen Algorithmus berechnen: 1066-819=247 — 819-3·247=78 — 247-3·78=13 — 78-6·13=0.

Für c≠13z gibt es also sicher keine ganzzahlige Lösung.

Umgekehrt ist es etwas schwieriger: Für c=13z kannst Du die Gleichung durch 13 teilen. Und ax+by=z hat für teilerfremde a,b≠0 immer ganzzahlige Lösungen. Musst Du das beweisen?

Kommentar von Siarzewski ,

da steh nur, dass ich es angeben muss. Also keine Berechnungen oder sonst was. Also wäre in den Fall zum Beispiel 14 richtig? fur c=14 gibt es keine Lösungen in Z^2.

Kommentar von ralphdieter ,

c=14 passt:

13·(82x+63y) 14, weil links ein Vielfaches von 13 steht, aber rechts nicht. Daran kann kein x oder y rütteln.

P.S.: Bescheiden wie ich bin hätte ich wohl c=1 genommen. Oder doch besser c=1300000000012 ? Immer diese Entscheidungen...

Antwort
von Melvissimo, 27

Wenn c = 1066x + 819y ist, dann ist c sicher durch ggT(1066,819) teilbar.

Kommentar von Siarzewski ,

ja aber abgesehen von der Formel, ich soll nur ein C finden, was kein Vielfaches von ggT(1066,819) ist.

zb.:  eine Gleichung 99x+78y=3 also ggT(99,78) = 3

hier zb: ist 4 kein Vielfaches von 3!

Kommentar von Melvissimo ,

Wo ist also das Problem? Berechne ggT(1066,819) und such dir ein c aus, das kein Vielfaches davon ist.

Falls nicht gerade ggT(a,b) = 1 ist, kannst du btw einfach immer c = 1 wählen.

Kommentar von Siarzewski ,

ok dann verstehe ich hier wahrscheinlich was falsch ;P ggT(1066,819) = 13

wenn ich jetzt 13! nehme, dann teilt JEDE Zahl die 13!. Oder soll ich einfach nur mal schauen was die 13 teilt und nicht 13! ?

Kommentar von Melvissimo ,

Ok, ganz von vorne, Schritt für Schritt:

Ich soll hier angeben, für welches c die Gleichung 1066x + 819y = c keine Lösungen in Z² besitzt.

So lautet die Aufgabenstellung. Wir wissen bereits aus dem euklidischen Algorithmus: Die Gleichung ist genau dann lösbar, wenn ggT(1066,819) = 13 ein Teiler von c ist.

Also ist die Gleichung genau dann unlösbar, wenn c kein Vielfaches von 13 ist.

D.h. c ist eine der folgenden Zahlen:

1,2,3, ..., 11,12,14,15,16,...,24,25,27,28,......

bzw dasselbe im Negativen.

Kommentar von Siarzewski ,

alles klar. Wieder zu kompliziert gedacht. Vielen Dank :)

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten