Rechnen mit Restklasse (Modulo)?
Ich habe die Aufgabe:
2/3 = ?? mod 7
diese wird so gelöst:
2/3 = 2 * 3^-1 = ?? mod 7
3^-1 wird dabei durch 5 ersetzt ich verstehe jedoch nicht wie man auf die 5 kommt. Kann das vielleicht jemand erklären?
Danke ^^
2 Antworten
a⁻¹ heißt das Inverse von a, wenn a ⋅ a⁻¹ = a⁻¹ ⋅ a = 1 (wobei 1 das neutrale Element der Multiplikation ist).
Indem Fall ist das neutrale Element der Multiplikation die Restklasse 7ℤ + 1. Gesucht ist also eine Zahl b, sodass 3⋅b in dieser Restklasse liegt. Für b = 5 ist wegen 3 ⋅ 5 = 15 = 2⋅7 + 1 ≡ 1 (mod 15) dies der Fall. Hier kann man die Lösung leicht durch probieren finden. Ansonsten verwendet man den erweiterten euklidischen Algorithmus:
7 - 5 = 2
5 - 2⋅2 = 1
⇒ 5 - 2⋅(7 - 5) = 3⋅5 - 2⋅7 = 1 ⇔ 3⋅5 = 2⋅7 + 1
Du musst dich nur fragen, was "^-1" bedeutet: "3^-1" ist die Zahl, die man mit 3 multiplizieren muss, um auf 1 zu kommen.
Und da 3 * 5 = 15 = 1 mod 7 ist, ist 3^-1 = 5 mod 7.
Woher weiß man, dass es die 5 ist? Im Zweifelsfall durch Ausprobieren, im Restklassenring modulo 7 hast du ja eh nur 7 Zahlen, die du testen könntest ;)
Ahso das ist so einfach danke dir und ich zerbrech mir seit einer halben Stunde den Kopf ^^