Kann mir jemand bei Euklidischen Algorithmus helfen?

... komplette Frage anzeigen

2 Antworten

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?

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Siarzewski
11.06.2016, 16:06

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.

1

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

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Siarzewski
11.06.2016, 15:34

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!

0

Was möchtest Du wissen?