inverse modulo < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | 19^-1 mod 13 = 11? |
hallo kann mir bitte jemand erklären wie ich von 19^-1 mod 13 auf 11?? komme? ich kann diese 11 absolut nicht nachvollziehen. danke
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> 19^-1 mod 13 = 11?
> hallo kann mir bitte jemand erklären wie ich von 19^-1
> mod 13 auf 11?? komme?
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
[mm] 19^{-1} [/mm] ist das Inverse von 19, also die Zahl, die man mit 19 multiplizieren muß, wenn man 1 herausbekommen möchte.
Gucken wir mal:
[mm] 19*11=209\equiv [/mm] 1 mod (13),( denn
209=16*13+1.)
Also ist 11 das Inverse von 19.
Oder anders:
[mm] 19^{-1}=6^{-1} [/mm] (denn [mm] 19\equiv [/mm] 6 mod 13),
und [mm] 6*11\equiv [/mm] 1 mod 13.
Also ist 11 das Inverse von [mm] 6\equiv [/mm] 19 (mod 13).
LG Angela
|
|
|
| |
|
oke, ja das sieht schonmal besser aus, nur wenn die 11 nicht gegeben ist? also ich hab 19^-1 mod 13 = ?
kannst du mir da bitte die normale vorgehensweise angeben? weil alle rechner die ich mir angeschaut habe, nehmen den schritt als gegeben hin und google spuckt sachen aus die damit nichts zu tun haben :(
|
|
|
| |
|
> oke, ja das sieht schonmal besser aus, nur wenn die 11
> nicht gegeben ist? also ich hab 19^-1 mod 13 = ?
>
Hallo,
dann suchst Du (wie zuvor dargestellt) das Inverse von 6, könntest also 6*1, 6*2,..6*12 durchprobieren.
Ich weiß, daß Dir dies nicht gefällt - es ist aber bei kleinen Zahlen (die 13 ist ja noch klein) ein durchaus gangbarer Weg.
> kannst du mir da bitte die normale vorgehensweise angeben?
Man macht das mit dem erweiterten euklidischen Algorithmus, mit welchem man Zahlen s und t bestimmt, so daß 1=19*s+13*t.
Wie der Algorithmus geht, kannst Du in Skript/Literatur/Internet nachlesen.
LG Angela
|
|
|
| |
|
oke ja ausprobieren kommt nicht in frage, ich habe den euklid schon gemacht damit:
das ergebniss wäre bei mir:
1 = 3 * 13 + (-2) * 19
ich verstehe nicht wo ich die 11 hier heraus lesen kann...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:14 Di 06.08.2013 | | Autor: | algieba |
> oke ja ausprobieren kommt nicht in frage, ich habe den
> euklid schon gemacht damit:
>
> das ergebniss wäre bei mir:
>
> 1 = 3 * 13 + (-2) * 19
>
> ich verstehe nicht wo ich die 11 hier heraus lesen kann...
Hallo
die -2 existiert bei Modulo 13 ja eigentlich nicht. Im Prinzip gibt es nur die Zahlen von 0 bis 12. Für die -2 gilt aber $-2 [mm] \equiv [/mm] 11 [mm] \mod [/mm] 13$ denn $-2 = -1 [mm] \cdot [/mm] 13 + 11$. Das bedeutet also dass die -2 und die 11 in der gleichen Äquivalenzklasse liegen, und von daher im Prinzip gleich sind.
Daraus kann man folgern dass -2 auch ein Inverses von der 19 ist (denn es gilt $-2 * 19 = -38 [mm] \equiv [/mm] 1 [mm] \mod [/mm] 13$) jedoch nennt man in diesem Fall die ganze Zahl aus dem Intervall $[0,12]$ als Inverses, da du sonst unendlich viele Inverse finden kannst (..., -15, -2, 11, 24, 37,...)
Viele Grüße
|
|
|
| |
|
oke super also die sache mit den äuivalenzklassen und der 19^-1 mod 13 = 11 verstehe ich, hatte mich nämlich verrechnet und bin zu dem ergebnis -2 mod 13 = 15 gekomm, deshalb habe ich die 11 nie gefunden...
jetzt komme ich allerdings zum kern meines problems, also 19^-1 mod 13 verstehe ich jetzt, aber nur weil ich in dem fall den erweiterten euklid auf (19, 13) anwenden kann, grad der anfang ist jetzt allerdings das problem:
ggt (19, 13), ist einfach zu berechnen...
ggt (13, 19), verstehe ich nicht ganz, weil:
13 = ? * 19 * rest; geht ja nicht ?
weil die frage ist wie komme ich auf 13^-1 mod 19 = 3?
das wäre vorerst mein letztes problem, wäre ganz toll wenn ihr mir die beantworten könnten, bringt mir ein großes stück verständnis beim chin. restsatz... danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:26 Di 06.08.2013 | | Autor: | abakus |
> oke super also die sache mit den äuivalenzklassen und der
> 19^-1 mod 13 = 11 verstehe ich, hatte mich nämlich
> verrechnet und bin zu dem ergebnis -2 mod 13 = 15 gekomm,
> deshalb habe ich die 11 nie gefunden...
>
> jetzt komme ich allerdings zum kern meines problems, also
> 19^-1 mod 13 verstehe ich jetzt, aber nur weil ich in dem
> fall den erweiterten euklid auf (19, 13) anwenden kann,
> grad der anfang ist jetzt allerdings das problem:
>
> ggt (19, 13), ist einfach zu berechnen...
>
> ggt (13, 19), verstehe ich nicht ganz, weil:
>
> 13 = ? * 19 * rest; geht ja nicht ?
Doch. Es gilt
13=0*19 + 13
Gruß Abakus
>
> weil die frage ist wie komme ich auf 13^-1 mod 19 = 3?
>
> das wäre vorerst mein letztes problem, wäre ganz toll
> wenn ihr mir die beantworten könnten, bringt mir ein
> großes stück verständnis beim chin. restsatz... danke
|
|
|
| |
|
| Aufgabe | | 13^-1 mod 19 = 3? Erkläre die "3". |
das hilft mir leider nicht weiter.
letzte zeile vom e-euklid ist dann:
(13,19): 1=2*19+(-3)*13
daraus folgt:
-3 mod 19= 16 und nicht 3, wie in der lösung angegeben.
Also die aufgabe lautet 13^-1 mod 19 = 3, wie kommt ich auf die "3"?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:08 Di 06.08.2013 | | Autor: | abakus |
3> 13^-1 mod 19 = 3? Erkläre die "3".
> das hilft mir leider nicht weiter.
>
>
> letzte zeile vom e-euklid ist dann:
> (13,19): 1=2*19+(-3)*13
> daraus folgt:
>
> -3 mod 19= 16 und nicht 3, wie in der lösung angegeben.
>
> Also die aufgabe lautet 13^-1 mod 19 = 3, wie kommt ich auf
> die "3"?
Gar nicht, das ist ein Fehler in der Aufgabe (wenn sie so gestellt war.
Es gilt NICHT [mm] 13*3$\equiv$ [/mm] 3 mod 19, sondern
[mm] 13*3$\equiv$ [/mm] 1 mod 19.
PS: Du hast schon oben einen Fehler.
> (13,19): 1=2*19+(-3)*13
ist falsch, denn 2*19+(-3)*13 ist nicht 1, sondern -1.
>
|
|
|
| |
|
ja das habe ich falsch gemacht es heißt natürlich:
ausgehend von 13 / 19 bzw. (13,19)
e-euklid:
1= 3*13 + (-2)*19:
also -2 mod 19 = 17 und nicht 3.
also wäre mein ergebnis: 13^-1 mod 19 = 17
lösung: 13^-1 mod 19 = 3 (ist richtig, falls du das meintest... ist von WA)
nochmals bitte, wie komme ich auf die 3?
|
|
|
| |
|
> ja das habe ich falsch gemacht es heißt natürlich:
>
> ausgehend von 13 / 19 bzw. (13,19)
> e-euklid:
>
> 1= [mm] \red{3}*13 [/mm] + (-2)*19:
>
> also -2 mod 19 = 17 und nicht 3.
>
> also wäre mein ergebnis: 13^-1 mod 19 = 17
???
Du hast oben festgestellt: [mm] -2\equiv [/mm] 17 mod 19.
(-2 ist ja das Inverse von 2 bzgl. der Addition, und es ist [mm] 2+17=19\equiv [/mm] 0 mod 19.)
> lösung: 13^-1 mod 19 = 3 (ist richtig, falls du das
> meintest... ist von WA)
> nochmals bitte, wie komme ich auf die 3?
Weil 3*13= [mm] 1+2*19\equiv [/mm] 1 (mod 19).
Hast Du ja auch oben ausgerechnet.
LG Angela
|
|
|
|
