0 Daumen
786 Aufrufe

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.

Avatar von

2 Antworten

0 Daumen

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

Avatar von 123 k 🚀

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!!

0 Daumen

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

Avatar von 106 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community