Startseite » Forum » multiplikative Inverse modulo

multiplikative Inverse modulo

Universität / Fachhochschule

15:24 Uhr, 25.04.2016

Hallo!

ich habe eine Aufgabe, wo ich leider nicht weiterkomme.

die aufgabe lautet "Berechne das multiplikative inverse Element zu

5 mod 13

.

gut ich weiß dass ich das als diophantische Gleichung aufstellen kann:

5 x + 13 y = 1

nun berechne ich

x_{0}

und

y_{0}

mit dem erweiterten euklidischen Algorithmus, dann hab ich:

5 \cdot (- 5) + 13 \cdot (2) = 1

aber nun weiß ich nicht, wie ich auf die Inverse komme.

Ich hab da mal die Lösung von dem skript, da steht:
Für

x

erhalten wir also

- 5

. Wir reduzieren

- 5

modulo

13

und erhalten

- 5

kongruent

8 mod 13

. Somit ist also die Restklasse von 8 das multipl. inverse Element zur Restlasse 5 modulo

13

1)

ist immer

x

meine Lösung, bzw muss ich mich immer an

x

orienteiren (wie in diesem Beispiel "für

x

erhalten wir

- 5

. wir reduzieren...)

2)

wie komm ich auf 8? ich weiß, dass

- 5

und 8 bei division durch

13

denselben rest lassen, aber wie kommt man da auf 8 ? ist 8 die multiplikative inverse weil bei

- 5 mod 13.8

rest heraus kommt?

17:28 Uhr, 25.04.2016

Hallo
da

5 \cdot x = 1 mod 13

also

5 \cdot x = y \cdot 13 + 1

ist wäre besser gleich die Gleichung

5 \cdot x - 13 \cdot y = 1

zu lösen, die direkt

x = 8 y = 3

ergibt
aber auch mit

- 5

geht es, denn

- 5

ist das additive Inverse zu 5 also

5 - 5 = 0; - 5 = 0 - 5 = 13 - 5 = 8

alles

mod 13

das gilt für alle negativen Zahlen

- a = 0 - a = 13 - a

Gruß ledum

18:43 Uhr, 25.04.2016

Danke!

LG

1303485

1303419

	Status: nicht eingeloggt	Noch nicht registriert?