ein multiplikativ inverses Element bestimmen

Question

Aufgabe
(a) Bestimmen Sie, für \( m=1973 \), in dem Restklassenring \( \mathbb{Z} / m \mathbb{Z} \) ein multiplikativ inverses Element zu \( \overline{410}=410+m \mathbb{Z} \).

Hallo, hat jemand einen Ansatz für die Aufgabe?

Comments

Was ist die Gleichung, die dieses inverse Element erfüllen muss. Was hat diese Gleichung mit dem erweiterten Euklidischen Algorithmus zu tun?

Answer 1

Also bin mir nicht zu 100% sicher, aber habe die selbe Aufgabe so bearbeitet:

1. Größten gemeinsamen Teiler mit euklidischem Algorithmus bestimmen:

1973 = 410*4 + 333

410 = 333*1 + 77

...

Und das solange bis du etwas in der Form a = b*c + 0, also Rest 0 erhälts. Damit solltest du auf einen ggT von 1 kommen.

(2 = 1*2 + 0)

Dann 2. Bézout-Koeffizienten mit dem erweiterten euklidischen Algorithmus bestimmen:

1 = 25 - 12*2

1 = 25-12*(77-25*3) = 37*25 - 12*77

1 = 37*(333-77*4) - 12*77 = 37*333 - 160*410

... (Vorgang ist auf der Wikipedia Seite gut beschrieben und macht erst Sinn wenn du Schritt 1 gemacht hast)

Damit solltest du auf die Koeffizienten s = 197 und t = -948 kommen, damit 1 = 1973*s + 410*t .

Dann ist das Multiplikative Inverse in \( \mathbb{Z} / m \mathbb{Z} \) 1973-948 = 1025.

Hoffe das hilft.

LG

Tom