Modulo und Euklidischer Algorithmus

Question

Ich verstehe das nicht. Kann mir das bitte jemand erklären:

a) Verwenden Sie den euklidischen Algorithmus, um den größten gemeinsamen Teiler von 63 und 47 zu bestimmen.
b) Ermitteln Sie x,y ∈ ℤ mit 63x+47y = ggT(63, 47).
c) Bestimmen Sie ein Element z ∈ ℤ_{63}, für das z •_{63} 47 = 1 erfüllt ist.
d) Berechnen Sie ein Element t ∈ ℤ_{63}, welches t •_{63} 47 = 5 erfüllt.

Answer 1

Zu a) Der euklidische Algorithmus: 63-47=16; 47-16=31; 31-6=35; 31-16=15, 16-15=1. immer die kleinste von der zweitkleinsten subtrahieren. Das ist hier aber umständlich. Wenn eine der beiden Zahlen Primzahl ist, die nicht Teiler der anderen ist, dann ist der ggT 1.

Zu b) x=3, y=-4

Comments

Hm... ist a) nicht eher so gemeint:

63 = 1*47 + 16 
47 = 2*16 + 15
16 = 1*15 +  1 [=ggT(63,47)]

Das wird dann rückwärts aufgerollt für b).

---

Habe meinen Rechenfehler korrigiert.

---

die a und b kann ich nur verstehe ich die c nicht mit dem modulo:(

---

In c) ist das multiplikative Inverse zu 47 (mod 63) gesucht. Das lässt sich leicht im Kopf ermitteln, vermutlich zielt die Aufgabe aber darauf ab, es irgendwie mit b) zu bestimmen.

---

Hallo

c) lässt sich mit b) lösen, z=-4=59 mod 63

d)t=5*z

Gruß lul

---

Jetzt habe ich es denke ich verstanden vieeelen Dank nochmal!!

Answer 2

Hallo

Euklidischer Alg

63=1*47+16

47=2*16+15

16=1*15+1

ggt(63,27)=1

jetzt den Alg rückwärts: 1=16-15=16-(47-2*16)=-47+3*16=-47+3*(63-47)=3*63-4*47

1=3*63-4*47

DAS GESUCHTE ERGEBNIS.

jetzt sollten die 2 nächsten kein Problem mehr sein!

allerdings sooo spät mit Klausurvorbereitungen zu sitzen, lässt schwarz sehen, trozdem viel Erfolg morgen

Gruß lul