Invertierbarkeit von Zahlen in Z

01.12.2010, 01:02

minizicke1306

Invertierbarkeit von Zahlen in Z

Hey Leute,

Ich habe folgende Aufgabe, wo ich leider keine Ahnung habe, was damit überhaupt gemeint ist:
Prüfen Sie, ob 221 in $\begin{eqnarray*} \mathbb Z_{643} \end{eqnarray*}$ invertierbar ist, und bestimmen Sie gegebenenfalls das Inverse.

Leider habe ich keine Ideen, da ich nicht weiß, was genau $\begin{eqnarray*} \mathbb Z_{643} \end{eqnarray*}$ ist.
Ich hoffe ihr könnt mir ein paar Tipps geben.
Vielen Dank schonmal

01.12.2010, 01:06

lgrizu

Auf diesen Beitrag antworten »

RE: Invertierbarkeit von Zahlen in Z
$\begin{eqnarray*} \mathbb Z_{643} \end{eqnarray*}$ ist der Restklassenring der ganzen Zahlen modulo 643.

Da 643 eine Primzahl ist, ist dieser Ring sogar ein Körper.

Diese Informationen sind schon fast eine Komplettlösung Augenzwinkern

01.12.2010, 04:40

minizicke1306

Auf diesen Beitrag antworten »

Hey Igrizu,
erstmal danke für die Antwort.

Okay, also ich hoffe ich habe das richtig verstanden:
Eine Zahl x ist invertierbar, wenn sie mit $\begin{eqnarray*} y\in \left\{0,1,2,...,n-1\right\} \end{eqnarray*}$ multipliziert, den Rest 1 bei der Division durch n hat.

In meiner Aufgabe muss ich also eine Zahl x finden, so dass gilt:
$\begin{eqnarray*} 221y=643a+1 \end{eqnarray*}$
$\begin{eqnarray*} =>221y-643a=1 \end{eqnarray*}$
Da 643 aber eine Primzahl ist, kann ich nichts ausklammern und somit besitzt 221 ein Inverses für das die Gleichung erfüllt ist.

Soweit, so gut. Aber wie finde ich dieses y nun? Ich habe zuerst 221 ausprobiert, aber $\begin{eqnarray*} (221*221)-1 \end{eqnarray*}$ ist nicht durch 643 teilbar?! Was mache ich jetzt?? Alle zahlen durchprobieren??

Achja, andere Frage dazu. Kann ich die Aufgabe rein theoretisch auch mit Multiplikationstabelle/Additionstabelle lösen? Wenn ja wie würde das in der Theorie aussehen??

01.12.2010, 05:15

minizicke1306

Auf diesen Beitrag antworten »

okay, ich habe jetzt auch das inverse, indem ich einfach nach y aufgelöst habe und ausprobiert habe für welches a mein $\begin{eqnarray*} y\in \mathbb Z \end{eqnarray*}$ ist.
Dabei habe ich für $\begin{eqnarray*} a=210 \end{eqnarray*}$ und somit ist mein Inverses $\begin{eqnarray*} y=611 \end{eqnarray*}$ .
$\begin{eqnarray*} => 221*611=135031=643*210+1 \end{eqnarray*}$

Stimmt also, aber das ist echt mühsam. Hoffe es gibt da ne schnellere Methode, ohne ausprobieren ;-)

01.12.2010, 05:41

minizicke1306

Auf diesen Beitrag antworten »

Zitat:

Original von minizicke1306
okay, ich habe jetzt auch das inverse, indem ich einfach nach y aufgelöst habe und ausprobiert habe für welches a mein $\begin{eqnarray*} y\in \mathbb Z \end{eqnarray*}$ ist.
Dabei habe ich für $\begin{eqnarray*} a=210 \end{eqnarray*}$ und somit ist mein Inverses $\begin{eqnarray*} y=611 \end{eqnarray*}$ .
$\begin{eqnarray*} => 221*611=135031=643*210+1 \end{eqnarray*}$

Stimmt also, aber das ist echt mühsam. Hoffe es gibt da ne schnellere Methode, ohne ausprobieren ;-)

Das ist totaler Humbuck Big Laugh

Ich habe gerade herausgefunden, dass ich ja $\begin{eqnarray*} ggt(221,643)=1=a*221+b*643 \end{eqnarray*}$ und damit a und b bestimme und dann habe ich mein inverses zu 221, nämlich 32 Big Laugh

tataaaaa....

war ja doch nicht so schwer Hammer

01.12.2010, 06:54

minizicke1306

Auf diesen Beitrag antworten »

Erstmal sorry, dass ich noch eine Antwort erstellen muss smile

Ich hatte ja raus $\begin{eqnarray*} -32*221+11*643=1 \end{eqnarray*}$ Muss ich dann die -32 noch umwandeln ins positive?? Oder reicht es wenn ich das umforme nach $\begin{eqnarray*} 32*221=11*643-1 \end{eqnarray*}$ ??
Wenn das reicht, habe ich 32 als inverse. Wenn das nicht reicht ist ja doch 643-32=611 mein inverses?!??

Jetzt bin ich echt total verwirrt

01.12.2010, 07:43

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von minizicke1306
Stimmt also, aber das ist echt mühsam. Hoffe es gibt da ne schnellere Methode, ohne ausprobieren ;-)

Das Stichwort dazu ist Erweiterter Euklidischer Algorithmus (EEA), z.B. hier schön als Webseite demonstriert:

http://www.mirsky.de/ggt.php

01.12.2010, 08:28

minizicke1306

Auf diesen Beitrag antworten »

Zitat:

Das Stichwort dazu ist Erweiterter Euklidischer Algorithmus (EEA)

Ja, das hatte ich ja auch nachher rausgefunden, aber wie ist das jetzt mit der -32?? kann ich das als inverses stehen lassen (ist ja auch in Z) oder muss ich das positiv machen, dann wäre das in dem Restklassenring ja 643-32=611?!??

01.12.2010, 09:44

lgrizu

Auf diesen Beitrag antworten »

-32 liegt in der gleichen Restklasse modulo 643 wie -32+643=611.

Also ist deine Antwort im letzten Post richtig.

Du hättest auch argumentieren können, dass 643 eine Primzahl ist, also ist der Restklassenring mod 643 ein Körper und in Körpern hat jedes Element ein multiplikativ Inverses.

Dann Euklidscher Algorithmus und den ggT mit Bezout darstellen, noch den kleinsten positiven Repräsentanten der Restklasse bestimmen und fertig, aber das hast du dann ja auch gemacht.

01.12.2010, 10:09

minizicke1306

Auf diesen Beitrag antworten »

Zitat:

noch den kleinsten positiven Repräsentanten der Restklasse bestimmen und fertig, aber das hast du dann ja auch gemacht.

Das verwirrt mich jetzt.. Ich habe zwar den kleinsten Repräsentanten bestimmt, aber der ist bei mir nicht positiv (es ist ja -32)!!
Oder habe ich jetzt was durcheinander geworfen??

01.12.2010, 10:11

lgrizu

Auf diesen Beitrag antworten »

(-32) ist der betragskleinste Repräsentant, 611 ist der kleinste positive Repräsentant der gleichen Restklasse modulo 643. Augenzwinkern

01.12.2010, 14:06

minizicke1306

Auf diesen Beitrag antworten »

also lass ich jetzt einfach -32 da stehen smile

Vielen Vielen Dank Igrizu, ich habs verstanden ;-)

Neue Frage »

Antworten »

Invertierbarkeit von Zahlen in Z

Verwandte Themen