Finden Sie a, b ∈ ℤ, sodass 1= 50a + 13b

Question

bei dieser Aufgabe habe ich leider noch Probleme. Durch "naives Rechnen", das in der Klausur allerdings keine Punkte geben würde, habe ich herausgefunden das a = 6 und b = -23 ist. Ich schreibe euch zuerst mal auf, was ich schon habe, vielleicht könnt ihr mir bei dem letzten Schritt noch helfen =?

50= 3.13 + 11
<=> 11 = 50 – 3*13

13 = 1*11 + 2
<=> 2 = 13 – 1 * 11 = 13 – 1*(50 – 3*1)

11 = 5 * 2 + 1
<=> 1 = 11 - 5 * 2 =

2 = 2 * 1 + 0

Leider weiß ich nicht, wie ich jetzt auf a = 6 und b = -23 kommen soll.

Comments

https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

Answer 1

  Es gibt einen Algoritmus; starte das KI Programm " lineare diophantische Gleichungen " von ===>  Arndt Brünner.   Mal sehen, ob du dann immer noch Lust hast ...

Answer 2

Aus 1=50a+13b folgt a=(1-13b)/50 und es gibt unendlich viele Paare (a,b) die diese Gleichung erfüllen aber sicher nicht a = 6 und b = -23.

Comments

Aus 1=50a+13b folgt a=(1-13b)/50 und es gibt unendlich viele Paare (a,b) die diese Gleichung erfüllen aber sicher nicht a = 6 und b = -23.

Verstehe ich nicht. Es gilt doch

1=6*50-23*13

---

Du hast recht. Aber dann gibt es noch unendlich viele weitere Zahlenpaare (a|b) die 1=50a+13b erfüllen

---

Kennt man eines, kennt man alle:

1=50*(6+k*13)+13*(-23-k*50)

zum Beispiel für k=-1:

1=50*(-7)+13*27

Eindeutigkeit wurde aber auch nicht unterstellt und alle Lösungspaare waren auch nicht gesucht.

Answer 3

50 = 3*13 + 1 
13 = 1*11 + 2 
11 = 5* 2 + 1
 5 = 5* 1 + 0 

1 = 11 - 5*2 
  = 11 - 5*(13 - 1*11) 
  = -5*13 + 6*11 
  = -5*13 + 6*(50 - 3*13) 
  =  6*50 - 23*13

Diese Variante des erweiterten euklidischen Algorithmus wäre ein möglicher Rechenweg. Wie habt ihr solche Rechnungen denn in der Vorlesung gehandhabt?