Bestimmen Sie den größten gemeinsamen Teiler von ganzen Zahlen

Question

Aufgabe:

a) Bestimmen Sie den größten gemeinsamen Teiler

gcd(666, 936) der ganzen Zahlen 666 und 936

sowie Zahlen s, t ∈ Z mit gcd(666, 936) = 666s + 936t.

b) Berechnen Sie mithilfe des euklidischen Algorithmus das (multiplikative) Inverse von
[419]₁₁₃₇ ∈  ℤ₁₁₃₇.

Problem/Ansatz:

Kann mir jemand bei den Aufgaben helfen bitte?

Answer 1

gcd(666, 936) mit euklidischem Algorithmus 7

(siehe etwa https://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Beispiel )

und beginne mit 936 statt 1071  und 666 statt 462, also

936 =  ? * 462 + ?

Dann ist das 1. ? eine 2 und das zweite 12.

Also 936=2*462+12

Dann weiter mit

462 =  ? * 12 + ?

solange bis das 2. ? eine 0 ergibt.

gcd(666, 936) = 666s + 936t mit dem erweiterten euklid. Alg.

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

multiplik. Inverses von [419]₁₁₃₇ ∈  ℤ₁₁₃₇.

bedeutet 419 * x ≡ 1   mod 1137

<=>      419*x + 1137*y = 1

Und hier wie bei https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

vorgehen.

Comments

und wie genau funktioniert das mit dem erweiterten euklidischen Algorithmus?

---

siehe dazu den Link

---

Danke mathef ich versuche es mal

Answer 2

666= 2*333= 2*3*3*111 = 2*3*3*37=2*3^2*37

936 = 2*468 = 2^2*234= 2^2*3*3*26= 2^3*3^2*13

ggT = 2^2*3^2 = 36

Comments

Danke dir auch!