Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Inverses einer Restklasse

Inverses einer Restklasse

Universität / Fachhochschule

Algebraische Zahlentheorie

Analytische Zahlentheorie

Elementare Zahlentheorie

Primzahlen

Teilbarkeit

Tags: Algebraische Zahlentheorie, Analytische Zahlentheorie, Elementare Zahlentheorie, inverse Elemente, Kongruenz, Primzahl, Restklasse, Teilbarkeit

Kali13 aktiv_icon

19:35 Uhr, 24.06.2013

Hallo,
es geht um die Aufgabe:

Bestimme alle

x \in ℕ

für die gilt:

15 x \equiv 2 (mod 23)

Also mit Restklassen hieße das dann:

{[15]}_{23} \cdot {[x]}_{23} = {[2]}_{23}

Kann ich um

[x]

herauszufinden jetzt einfach das inverse von

{[15]}_{23}

ausrechnen? Wenn ja, wie mache ich das?

Ich weiß, dass ich irgendwie den Euklidschen Algorithmus brauche. Den würde ich so anfangen:

23 = 1 \cdot 15 + 8

15 = 1 \cdot 8 + 7

8 = 1 \cdot 7 + 1

Dann nach 1 umstellen

1 = 8 - 1 \cdot 7

Die 7 ersetzen

1 = 8 - 1 \cdot (15 - 1 \cdot 8)

Die 8 ersetzen

1 = 8 - 1 \cdot (15 - 1 \cdot (23 - 1 \cdot 15))

Jetzt weiß ich nicht wirklich weiter. Muss ich den Algorithmus immer komplett zurück rechnen? Also bis ich wieder oben angekommen bin

(\in

dem Fall die 8 ersetzt habe)? Wie muss ich jetzt weiter machen?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Dreiecke und Kongruenz
Teilbarkeit natürlicher Zahlen

pwmeyer aktiv_icon

19:43 Uhr, 24.06.2013

Hallo,

Du musst die 8 überall ersetzen.

Am Ende hast Du eine Gleichung der Art

1 = s \cdot 15 + t \cdot 23,

die besagt, dass

s

das Inverse von

15

ist. Dann berechnest Du

x = {[2 \cdot s]}_{23}

Kali13 aktiv_icon

19:53 Uhr, 24.06.2013

Also steht dann da

1 = (23 - 1 \cdot 15) - 1 \cdot (15 - 1 \cdot (23 - 1 \cdot 15))

1 = . .

.

Ich stehe irgendwie ziemlich auf dem Schlauch. Wenn ich das jetzt ausrechne kommt da doch irgendwas ganz anderes aus.
Wie klammere ich das denn aus? Ich glaube da liegt mein Fehler, dass ich hier nicht weiter komme.

Kali13 aktiv_icon

20:06 Uhr, 24.06.2013

Ich glaube ich habs.
Bei mir kommt dann

1 = 2 \cdot 23 - 3 \cdot 15

raus

also ist das inverse von

15 = 2 \cdot - 3 = - 6

?
Wieso rechnet man

- 3 \cdot 2

?

Was mache ich nun weiter?

michaL aktiv_icon

20:11 Uhr, 24.06.2013

Hallo,

betrachte doch die Gleichung

1 = 2 \cdot 23 - 3 \cdot 15

mal modulo 23!

-6 ist jedenfalls nicht korrekt.

Mfg Michael

Kali13 aktiv_icon

20:19 Uhr, 24.06.2013

Ich weiß nicht wie du das meinst.

Die Gleichung

1 = 2 \cdot 23 - 3 \cdot 15

ist aber soweit richtig ja?

Wie soll ich die Gleichung modulo

23

betrachten?

michaL aktiv_icon

20:24 Uhr, 24.06.2013

Hallo,

ja, die Gleichung ist korrekt (aber das kannst du ja schlimmstenfalls mit dem Taschenrechner überprüfen, oder?).

Modulo 23 bedeutet, dass 23 als Null betrachtet wird.

Mfg Michael

Kali13 aktiv_icon

22:07 Uhr, 24.06.2013

Dann würde rauskommen

1 = - 45

ist

- 45

das inverse von

15

michaL aktiv_icon

22:43 Uhr, 24.06.2013

Hallo,

oh, mann...

1 = 2 \cdot 23 - 3 \cdot 15

. In einem Universum, in dem

23 \equiv 0

gilt, würde diese Gleichung

1 \equiv - 3 \cdot 15

bedeuten, d.h. das Inverse von 15 ist -3 mod 23.

Mfg Michael

PS: Unzählige threads zu dem Thema finden sich sowohl hier in diesem Forum als auch bei youtube und vielen anderen.

EDIT: TYPO

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1103130

1103079

	Status: nicht eingeloggt	Noch nicht registriert?