Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode.

Question

wie funktioniert diese Aufgabe?

a) Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0. Der erweiterte Euklidische Algorithmus berechnet α, β ∈ Z, so
dass ggT(x, y) = α·x+β · y.

Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode.
Benutzen Sie dazu:

• die Operatoren div und mod,
• eine Laufvariable i,
• a_i, b_i ∈ N mit a₀ = x und b₀ = y,
• die Ergebnisse q_i, r_i ∈ Z von div bzw. mod,
• gewisse Faktoren α_i, β_i ∈ Z, mit welchen am Ende des Algorithmus α und β bestimmt werden.

Hinweis: Es bietet sich an, dass der Algorithmus bei r_i = 0 abgebrochen wird, so dass ggT(x, y) = r_i−1
ist. Dann können α_i und β_i so berechnet werden, dass α = α_i−1 und β = β_i−1. Zur Berechnung von α_i
müssen α_i−1 und α_i−2 benutzt werden, zur Berechnung von β_i müssen β_i−1 und β_i−2 benutzt werden. Die
initialen Werte müssen daher gesetzt werden: man kann α₋₂, α₋₁, β₋₂, β₋₁ geschickt wählen.

b) Überprüfen Sie den Algorithmus anhand des Beispiels x = 23 und y = 13

Comments

Vom Duplikat:

Titel: Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0. ... Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode.

Stichworte: euklidischer,algorithmus,ggt,code

Wie funktioniert diese Aufgabe?

Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0. Der erweiterte Euklidische Algorithmus berechnet α, β ∈ ℤ, so dass ggT(x,y) = α*x + β*y. Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode. Benutzen Sie dazu die Operatoren div und mod.

Dankeschön

---

Vom Duplikat:

Titel: Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0.

Stichworte: euklidischer,algorithmus,ggt,code

Wie funktioniert diese Aufgabe?

Seien x, y, ∈ ℕ mit x ≠ y, x ≠ 0, y ≠ 0. Der erweiterte Euklidische Algorithmus berechnet α, β ∈ ℤ, so dass ggT(x,y) = α*x + β*y. Beschreiben Sie den erweiterten Euklidischen Algorithmus mit Pseudocode. Benutzen Sie dazu die Operatoren div und mod.

Dankeschön

---

Studiere mal die Rechnung hier: https://www.mathelounge.de/420132/verstandnisprobleme-erweiterten-euklidischen-algorithmus Vielleicht habt ihr da so behandelt.

Answer 1

siehe dort:

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