Es sei a:=40273 und b:=16031. Bestimmen Sie x ∈ ℤ derart, dass...

Question

1. Aufgabe:
Es sei a:=40273 und b:=16031. Bestimmen Sie x ∈ ℤ derart, dass ein y ∈ [ 0,  a/ ( gcd(a,b) ) - 1 ] existiert mit
gcd(a, b)= xa + yb.

2. Aufgabe:
Es sei a:=10711759 und b:=6049229. Bestimmen Sie x ∈ [ 0,  b/ ( gcd(a,b) ) - 1 ] derart, dass ein y ∈ ℤ existiert mit gcd(a, b)= xa + yb.

Hinweise zur Verständlichkeit:
→ gcd(a, b) steht für den größten gemeinsamen Teiler von a und b
→ die Zahl -1 zwischen den beiden eckigen Klammern steht nicht im Nenner, sondern nach dem Bruch
→ beide Aufgaben sollen unabhängig voneinander gelöst werden

Ich bitte um Hilfe und (Es wäre sehr nett, wenn ich eine schnelle Antwort bekomme:)

Answer 1

Beim euklidischen Algorithmus wird in aufeinanderfolgenden Schritten jeweils eine Division mit Rest durchgeführt, wobei der Rest im nächsten Schritt zum neuen Divisor wird. Der Divisor, bei dem sich Rest 0 ergibt, ist der größte gemeinsame Teiler der Ausgangszahlen.

Quelle:

https://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler

Comments

Danke, dass du mir erklärt hast, wie man den Größten gemeinsamen Teiler ausrechnet, aber das war leider nicht meine Frage.

---

... aber immerhin die Voraussetzung, um überhaupt weitermachen zu können, oder?

---

Ich hoffe, dass du mich nicht falsch verstanden hast...Den größten gemeinsamen Teiler muss man bestimmen..dafür habe ich mich auch bedankt:)..Um überhaupt auf das Ergebnis zu kommen, braucht man etwas mehr als nur den größten gemeinsamen Teiler zu bestimmen. Also war deine Antwort genau der richtige Ansatz.

---

Ich habe dich falsch verstanden - macht aber nix.

Hast du den ggT raus und die obere Grenze auch ?

Wenn wir die Zahlen haben, muss man etwas tüfteln - oft gehts auch überhaupt nicht, dann muss bewiesen werden, weshalb es nicht gehen kann.

---

In dem Fall geht es. Ich muss es mir aber noch einmal angucken, damit ich es besser verstehe. Danke für deine Mühe.