multiplikative inverse < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:24 So 15.05.2011 | | Autor: | emulb |
| Aufgabe | Bestimme die multiplikativen Inversen von
i) 7 mod 31
ii)26 mod 109 |
ich hab so keine ahnung wie man das rechnet. kann mir jemand die rechenschritte für i) sagen damit ich ii) selbstständig rechnen kann.
ich hab auch viele erklärungen gelesen aber ich versteh das ganze einfach nicht. :/
|
|
| |
|
> Bestimme die multiplikativen Inversen von
>
> i) 7 mod 31
> ii)26 mod 109
> ich hab so keine ahnung wie man das rechnet. kann mir
> jemand die rechenschritte für i) sagen damit ich ii)
> selbstständig rechnen kann.
>
> ich hab auch viele erklärungen gelesen aber ich versteh
> das ganze einfach nicht. :/
Hallo,
ein wenig schade ist es, daß Du uns nicht sagst, was Du gelesen hast und was Du daran nicht verstehst. Dann hätten wir nämlich einen konkreten Anhaltspunkt für unsere Hilfe.
Für die Bestimmung des mult. modularen Inversen verwendet man den erweiterten euklidischen Algorithmus.
![[]](/images/popup.gif) Hier ist ein Beispiel vorgerechnet.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:25 So 15.05.2011 | | Autor: | emulb |
die seite hat mir weitergeholfen aber es klemmt trotzdem
hier mein anfang:
7=0*31+7
31=4*7+3
7=2*3+1
3=3*1+0
umkehrung:
1=8-1*7
7=38-1*31
31=66-5*7
7=7-0*31
bei der substitution weiß ich zwar das ich dann die 7 substituiren muss aber woher weiß ich welche zahlen ich da verwende. dürfen das einfach irgendwelche beliebiegen sein??
|
|
|
| |
|
Hallo emulb,
> die seite hat mir weitergeholfen aber es klemmt trotzdem
> hier mein anfang:
>
> 7=0*31+7
kannst du weglassen und direkt mit der größeren Zahl beginnen ...
> 31=4*7+3
> 7=2*3+1
> 3=3*1+0 ![[ok]](/images/smileys/ok.gif "[ok]")
>
> umkehrung:
> 1=8-1*7
> 7=38-1*31
> 31=66-5*7
> 7=7-0*31
Du darfst die Klammern nicht ausrechnen ...
Oben im eukl. Algo. von unten nach oben:
[mm]1=7-2\cdot{}3=7-2\cdot{}(31-4\cdot{}7)=7-2\cdot{}31+8\cdot{}7=9\cdot{}7-2\cdot{}31[/mm]
Damit musst du lösen [mm]7\cdot{}x \ \equiv \ 1 \ \operatorname{mod}(31)[/mm]
Das bedeutet ja [mm]x[/mm] ist multiplikativ invers zu 7 modulo 31
Also [mm]7\cdot{}x \ \equiv \ 1 \ \equiv \ 9\cdot{}7-2\cdot{}31 \ \equiv \ 9\cdot{}7 \ \operatorname{mod}(31)[/mm]
Nun kannst du auf beiden Seiten "gefahrlos" durch 7 teilen (beachte [mm]\operatorname{ggT}(7,31)=1[/mm])
>
> bei der substitution weiß ich zwar das ich dann die 7
> substituiren muss aber woher weiß ich welche zahlen ich da
> verwende. dürfen das einfach irgendwelche beliebiegen
> sein??
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:02 So 15.05.2011 | | Autor: | emulb |
ok danke..hier meine Lösung zu ii)
109=4*26+5
26=5*5+1
5=5*1+0
von unten:
1=26-5*5=26-5(109-4*26)=26-5*109+20*26=21*26-5*109
26x [mm] \equiv [/mm] 1 mod (109)
26x [mm] \equiv [/mm] 1 [mm] \equiv21*26-5*109 \equiv [/mm] 21*26 mod (109)
ich hab ein gutes gefühl ;)
sieht mal richtig aus :)
|
|
|
| |
|
Hallo emulb,
> ok danke..hier meine Lösung zu ii)
>
> 109=4*26+5
> 26=5*5+1
> 5=5*1+0
>
> von unten:
>
> 1=26-5*5=26-5(109-4*26)=26-5*109+20*26=21*26-5*109
>
> 26x [mm]\equiv[/mm] 1 mod (109)
> 26x [mm]\equiv[/mm] 1 [mm]\equiv21*26-5*109 \equiv[/mm] 21*26 mod (109)
>
> ich hab ein gutes gefühl ;)
>
> sieht mal richtig aus :)
Das ist auch richtig.
Gruss
MathePower
|
|
|
| |
|
> Bestimme die multiplikativen Inversen von
>
> i) 7 mod 31
> ii)26 mod 109
> ich hab so keine ahnung wie man das rechnet. kann mir
> jemand die rechenschritte für i) sagen damit ich ii)
> selbstständig rechnen kann.
Hallo emulb,
ich versuche eine Erklärung, die ohne große Theorie
auskommt.
Bei der ersten Aufgabe ist diejenige ganze Zahl x
im Bereich [mm] 0\le{x}\le30 [/mm] gesucht, für welche
$\ 7*x\ =\ r*31+1$
gilt (für eine noch zu findende ganze Zahl r).
Wäre dies eine "gewöhnliche" Gleichung für eine
rationale (oder reelle) Zahl x, würden wir einfach
durch 7 teilen und hätten das Ergebnis.
In der vorliegenden Situation tun wir das "Best-
mögliche", indem wir die Gleichung zuerst um-
schreiben:
$\ 7*x\ =\ r*(28+3)+1\ =\ [mm] 28\,r+3\,r+1$
[/mm]
(28 ist dasjenige ganzzahlige Vielfache von 7,
welches knapp unter 31 liegt)
Nun teilen wir durch 7 und haben:
$\ x\ =\ [mm] 4\,r+\underbrace{\frac{3\,r+1}{7}}_s$
[/mm]
Natürlich geht dies im Bereich der erlaubten
Zahlen nur dann, wenn der Term s eine ganze
Zahl darstellt.
Damit haben wir eine analoge Frage wie am Anfang:
für welche ganzen Zahlen r und s gilt die Gleichung
$\ s\ =\ [mm] \frac{3\,r+1}{7}$
[/mm]
bzw. $\ [mm] 3\,r\ [/mm] =\ [mm] 7\,s-1$
[/mm]
Hier zerlegt man die 7 (wie vorher die 31) in 7=6+1 und
hat:
$\ [mm] 3\,r\ [/mm] =\ [mm] 6\,s+s-1$
[/mm]
Durch 3 geteilt:
$\ r\ =\ [mm] 2\,s+\underbrace{\frac{s-1}{3}}_t$
[/mm]
Wieder soll t eine ganze Zahl sein. Nun ist es aber
trivial, so eine Zahl anzugeben, nämlich t:=0 (für
s=1), und durch Einsetzen in die früheren
Gleichungen erhält man:
$\ [mm] r=2\,s+t=2$
[/mm]
$\ [mm] x=4\,r+s=9$
[/mm]
Kontrolle: $\ [mm] 7*9=63=2*31+1\equiv{1}$ [/mm] (mod 31)
Damit ist die Zahl 9 das gesuchte inverse Element
zu 7 in Bezug auf den Modul 31.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:38 So 15.05.2011 | | Autor: | emulb |
wooow danke...musste mich sehr darauf konzentrieren aber so gehts auch...ich finde es komplizierter. aber trotzdem danke iich glaub ich habs nur sollte jemand das kontrollieren :)
|
|
|
| |
|
> wooow danke...musste mich sehr darauf konzentrieren aber so
> gehts auch...ich finde es komplizierter.
Nun ja, was ich geschrieben habe, ist eben nicht
nur ein Rezept, das man auswendig lernen kann und
bei Gelegenheit zwangsläufig wieder vergisst,
sondern ein Text, der die Grundidee hinter der
Methode so erklärt, dass man die ganze Sache
auch verstehen kann.
> aber trotzdem
> danke iich glaub ich habs nur sollte jemand das
> kontrollieren :)
Deine Lösung [mm] 26^{-1}=21 [/mm] (modulo 109) ist korrekt !
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:43 So 15.05.2011 | | Autor: | emulb |
| Aufgabe | | Bestimme mit Hilfe der Aussage 5*1280-79*81 = ggT(1280,81) das multiplikative Inverse von 81 mod 1280. |
ich hab die zusatzaufgabe vergessen.
irgendwie ist die aufgabe komisch weil, da steht ggt(1280,81) aber es heißt 81 mod 1280.
ist das nicht irgendwie verkehrt??
|
|
|
| |
|
> Bestimme mit Hilfe der Aussage 5*1280-79*81 = ggT(1280,81)
> das multiplikative Inverse von 81 mod 1280.
> ich hab die zusatzaufgabe vergessen.
>
> irgendwie ist die aufgabe komisch weil, da steht
> ggt(1280,81) aber es heißt 81 mod 1280.
>
> ist das nicht irgendwie verkehrt??
Was findest du verkehrt ?
Ich habe allerdings eine gewisse Kritik an den Schreib-
weisen in der Aufgabenstellung. Da zum Beispiel die
Schreibweisen 17 mod 5 = 2 oder mod(17,5) = 2
für die gleichwertige Aussage [mm] 17\equiv{2} [/mm] (mod 5)
gang und gäbe sind, ist die Frage nach dem "Inversen
von 81 mod 1280" missverständlich oder wenigstens
nicht ganz eindeutig formuliert.
Zur Aufgabe:
Es ist leicht festzustellen, dass ggT(1280,81)=1 ist
(die Zahlen 1280 und 81 sind teilerfremd, da 81 nur
den Primfaktor 3 enthält und 1280 nicht durch 3
teilbar ist).
Mit der angegebenen Zerlegung haben wir also:
$\ 1\ =\ 5*1280-79*81$
Modulo 1280 wird aus dieser Gleichung:
$\ 1\ =\ 5*1280-79*81\ [mm] \equiv\ [/mm] -79*81$
Daraus ist sofort ersichtlich, dass die Zahlen -79 und 81
bezüglich des Moduls 1280 invers sind. Es ist also
$\ [mm] 81^{-1}\ [/mm] =\ -79$ (modulo 1280)
Will man negative Zahlenwerte vermeiden, so nimmt
man anstatt -79 die Zahl -79+1280 = 1201 .
Also:
$\ [mm] 81^{-1}\ [/mm] =\ 1201$ (modulo 1280)
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 19:27 So 15.05.2011 | | Autor: | emulb |
ich hab hier eine lösung:
da 5*1280-79*81 = 1 geh ich davon aus das ggT(1280,81)=1
somit kann ich direkt die umkehrfunktion berechnen.
1=1280-79*16,18987
=1280-79(81-0,05063*1280)
=1280-79*81+4*1280
=5*1280-79*81
1280x [mm] \equiv [/mm] 1 mod (81)
1280x [mm] \equiv [/mm] 5*1280-79*81 [mm] \equiv [/mm] 5*1280 mod (81)
ist das ausreichend??
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:21 Di 17.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
