Größter gemeinsamer Teiler (ggT) Koeffizienten eindeutig bestimmen

Question

Aufgabe:

Berechnen Sie jeweils den größten gemeinsamen Teiler \(d\) der beiden Zahlen \(a,b∈\mathbb{N}\). Bestimmen Sie ferner Zahlen \(λ,μ∈\mathbb{Z}\) mit $$λ⋅a+μ⋅b=d$$. Damit die Antwort eindeutig wird, sind \(λ,μ\) so zu finden, dass $$0≤λ<\frac{b}{d}$$

Problem/Ansatz:

Ich weiß, wie man den ggT bestimmt. Ich weiß auch, wie man die Koeffizienten findet. Allerdings soll \(0≤λ<\frac{b}{d}\) gelten. Mein Ansatz war, mit einer künstlichen 0 zu addieren, doch damit kam ich nicht weiter.

Was kann ich tun, um \(λ\) so zu bestimmen, dass es die Bedingung erfüllt?

Comments

Und dabei hast du keine Zahlen a und b gegeben und sollst das allgemein mit Buchstaben machen?

---

Doch natürlich sind auch Zahlen gegeben, z.b. a=348 und b=552, aber ich wollte eine allgemeine Herangehensweise wissen

Answer 1

Ist \((\lambda,\mu)\) ein Paar ganzer Zahlen, so dass

\(\lambda\cdot a+\mu \cdot b=d\quad (*)\) ist, so rechnet man

leicht nach, dass dann auch für jede ganze Zahl \(z\)

das Paar \((\lambda+\frac{b}{d}\cdot z,\; \mu-\frac{a}{d}\cdot z)\)

ebenfalls \((*)\) erfüllt, d.h. man kann \(\lambda\) modulo \(\frac{b}{d}\)

abändern und erhält wieder ein Lösungspaar für \((*)\).

Daher kann man \(\lambda\) als kleinsten nichtnegativen Rest mod \(\frac{b}{d}\)

wählen.

Answer 2

Allgemeine Herangehensweise:

Du berechnest den ggT mit dem euklidischen Algorithmus.

Mit dem erweiterten euklidischen Algorithmus bestimmst du dann die die Parameter λ und μ.