modulo

11.09.2008, 14:47

digaaan

modulo

he leute, hab hier n kleines problem:

wieso is 2j=1mod3 das gleiche wie j=2mod3 (oder auch 3j=1mod5 das gleich wie j=2mod5)

danke danke für antworten!

11.09.2008, 14:55

Auf diesen Beitrag antworten »

Weil das jeweils die Lösungen dieser linearen Kongruenzen sind - mach doch mal die Probe!

Und $\begin{eqnarray*} ax\equiv b \mod m \end{eqnarray*}$ ist für teilerfremde $\begin{eqnarray*} a,m \end{eqnarray*}$ nun mal eindeutig modulo $\begin{eqnarray*} m \end{eqnarray*}$ lösbar.

11.09.2008, 15:03

digaaan

Auf diesen Beitrag antworten »

wenn ich die probe mache sehe ich das auch... aber wie komme ich darauf? verstehe nicht den schritt der von der einen kongruenz zur anderen führt...

11.09.2008, 15:09

Auf diesen Beitrag antworten »

Das ist ja auch nicht so einfach.

Bei kleineren Modulen ist "Probieren" durchaus das Mittel der Wahl - allen Naserümpfern sei gesagt, dass sie doch bitte was Effizienteres nennen sollen.

Und bei größeren Modulen ist der EEA (=erweiterter euklidischer Algorithmus) angesagt.

11.09.2008, 15:17

digaaan

Auf diesen Beitrag antworten »

den eea also, okay. sagen wir mal, man is nicht der "probier"typ. also wende ich selbst bei den kleinen zahlen den eea an -> dann hab ich:

ggT(3,2) = 1*3 - 1*2 (1. Bsp)
ggT(5,3) = 2*3 - 1*5 (2. Bsp)

mir geht trotzdem kein licht auf... traurig

11.09.2008, 15:23

Auf diesen Beitrag antworten »

Zitat:

Original von digaaan
ggT(3,2) = 1*3 - 1*2 (1. Bsp)

Modulo 3 betrachtet heißt

$\begin{eqnarray*} (-1)\cdot 2 \equiv 1 \mod 3 \end{eqnarray*}$ ,

also ist (-1) das inverse Element zu 2 modulo 3. Also $\begin{eqnarray*} 2^{-1}\equiv -1\equiv 2\mod 3 \end{eqnarray*}$ .

Zitat:

Original von digaaan
ggT(5,3) = 2*3 - 1*5 (2. Bsp)

Ganz genauso: Hier kannst du ablesen $\begin{eqnarray*} 3^{-1}\equiv 2\mod 5 \end{eqnarray*}$ .

11.09.2008, 16:35

digaaan

Auf diesen Beitrag antworten »

kk, letzte frage:

wie kann man dann 97s=194mod11011 vereinfach dass da nur noch steht:
s=?????mod11011
wie wende ich hier eea an, bzw was muss ich da genau ablesen?

11.09.2008, 17:44

Romaxx

Auf diesen Beitrag antworten »

Hallo,

auch hier hilft der erweiterte euklidische Algorithmus:

$\begin{eqnarray*} ggT(97,11011)=1 \end{eqnarray*}$

und die $\begin{eqnarray*} 1 \end{eqnarray*}$ lässt sich sicher als Linearkombination von $\begin{eqnarray*} 97 \end{eqnarray*}$ und $\begin{eqnarray*} 11011 \end{eqnarray*}$ darstellen

$\begin{eqnarray*} 1=a\cdot 97 + b\cdot 11011 \end{eqnarray*}$

Modulo $\begin{eqnarray*} 11011 \end{eqnarray*}$ gerechnet ergibt

$\begin{eqnarray*} 1\equiv a\cdot 97 + b\cdot 11011\equiv a\cdot 97 \mod11011 \end{eqnarray*}$

und jetzt noch die $\begin{eqnarray*} 97 \end{eqnarray*}$ auf die andere Seite bringen

$\begin{eqnarray*} (97)^{-1}\equiv a \mod 11011 \end{eqnarray*}$

und mit diesem Inversen dann die obere Gleichung durchmultiplizieren.

Neue Frage »

Antworten »

modulo

Verwandte Themen