Invertieren modulo < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | (b) Invertieren Sie 17 modulo 30 (auch händisch).
(c) Invertieren Sie 1768987 modulo 3000000.
(d) Invertieren Sie 1768989 modulo 3000000.
(e) Lösen Sie die Gleichung 1768989 · x ~ 123 (mod 3000000). |
Ich habe diese Frage bereits in einem anderen Forum gestellt: http://www.uni-protokolle.de/foren/viewt/157699,0.html jedoch konnte mir dort bisher niemand antworten.
ich habe nicht kapiert, was die Aufgabenstellung überhaupt bedeutet und komme mit den wenigen Beschreibungen im Internet auch nicht zurecht. Lediglich auf einer Seite habe ich gefunden, dass man zuerst überprüfen müsse, ob sich das überhaupt invertieren lässt. Dort wurde geprüft, ob der ggt 1 ist und argumentiert deshalb liese es sich invertieren. Mehr habe ich nicht gerafft davon weder was dieses invertieren überhaupt heisst, noch ob sich immer nur dann invertieren lässt, wenn ggt =1.
Wenn mir jemand erklären könnte, wie diese Aufgaben gerechnet werden oder einen geeigneten Link senden könnte, wo ein Beispiel erklärt ist, wäre ich dankbar.
Liebe Grüße
Snoopy
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:33 Di 23.10.2007 | | Autor: | statler |
Guten Morgen Snoopymaus!
> (b) Invertieren Sie 17 modulo 30 (auch händisch).
> (c) Invertieren Sie 1768987 modulo 3000000.
> (d) Invertieren Sie 1768989 modulo 3000000.
> (e) Lösen Sie die Gleichung 1768989 · x ~ 123 (mod
> 3000000).
> ich habe nicht kapiert, was die Aufgabenstellung überhaupt
> bedeutet und komme mit den wenigen Beschreibungen im
> Internet auch nicht zurecht.
Ich befasse mich erstmal nur mit b). Die Aufgabe bedeutet, die Kongruenz 17x [mm] \equiv [/mm] 1 mod 30 zu lösen. Das wiederum bedeutet, eine Zahl y zu finden, für die 17x - 1 = 30y ist.
Das kann man mit dem euklidischen Algorithmus anpacken:
30 = 1*17 + 13
17 = 1*13 + 4
13 = 3*4 + 1
Jetzt rückwärts einsetzen:
1 = 13 - 3*4 = 13 - 3*(17 - 13) = 4*13 - 3*17 = 4*(30 - 17) - 3*17 = 4.30 - 7*17
Also sind wir bei -7*17 = 1 - 4*30 angekommen.
Wir addieren noch 30*17 = 17*30 und erhalten
23*17 = 1 + 13*30
Also können wir x = 23 nehmen.
> Wenn mir jemand erklären könnte, wie diese Aufgaben
> gerechnet werden oder einen geeigneten Link senden könnte,
> wo ein Beispiel erklärt ist, wäre ich dankbar.
Jetzt versuch mal dein Glück mit den anderen.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Hallo Dieter,
erstmal tausend Dank. Noch blicke ich nicht durch bei dem rückwärts einsetzen, aber noch eine kleine Frage für die anderen Aufgaben: Heisst das immer kongruent 1 oder nur dann, wenn der ggt = 1 ist oder wo kommt diese 1 her?
Gruß Snoopy
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:56 Di 23.10.2007 | | Autor: | statler |
Hi!
> erstmal tausend Dank. Noch blicke ich nicht durch bei dem
> rückwärts einsetzen, aber noch eine kleine Frage für die
> anderen Aufgaben: Heisst das immer kongruent 1 oder nur
> dann, wenn der ggt = 1 ist oder wo kommt diese 1 her?
Bei c) und d) heißt das 1, weil das Inverse gesucht ist, und das geht nur, wenn der ggt = 1 ist. Bei e) mußt du dann noch mal durchmultiplizieren: 123 = 123*1
Viel Spaß dabei, ich guck dir zu 
Dieter
>
> Gruß Snoopy
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:59 Di 23.10.2007 | | Autor: | koepper |
Hallo Snoopy,
in der Anlage etwas Lesestoff für dich.
Keine Angst, es sind nur 2 Seiten!
Gruß
Will
![[a]](/images/paperclip.gif "Dateianhänge") Datei-Anhang
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
na dann bin ich ja jetzt im Zugzwang und versuche zuerst mal die
(c) Invertieren Sie 1768987 modulo 3000000
ggt(1768987,3000000) = 1 da 3000000 = [mm] 3*10^6, [/mm] also nur die Primfaktoren 2,3 und 5 hat, die alle nicht in 1768987 enthalten sind (letzte Ziffer nicht gerade, nicht 0 oder 5 und Quersumme nicht durch 3 teilbar)
Also ist 1768987 x ~ 1 (mod 3000000) oder eine Zahl y gesucht für die gilt: 1768987 x -1 = 3000000 y
Nach dem euklid'schen Algorithmus ist:
3 000 000 = 1 * 1 768 987 + 1 231 013
1 768 987 = 1 * 1 231 013 + 537 974
1 231 013 = 2 * 537 974 + 155 065
537 974 = 3 * 155 065 + 72 779
155 065 = 2 * 72 779 + 9 507
72 779 = 7 * 9 507 + 6 230
9 507 = 1 * 6 230 + 3 277
6 230 = 1 * 3 277 + 2 953
3 277 = 1 * 2 953 + 324
2 953 = 9 * 324 + 37
324 = 8 * 37 + 28
37 = 1 * 28 + 9
28 = 3 * 9 + 1
so, nun schicke ich das soweit erst mal weg, bevor mir die kunstvolle Formatierung wieder verlorengeht, hoffe das ist soweit richtig, Rest folgt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:39 Di 23.10.2007 | | Autor: | statler |
Hi, das rechne ich jetzt nicht nach, sieht aber ganz gut aus. Wenn die Zahlen zu groß werden, lassen wir am Ende durch den Besitzer einer leistungsfähigen Software eine Probe machen.
Dieter
|
|
|
| |
|
nun rückwärts einsetzen:
1 = 28 - 3 * 9
= 28 - 3 * (37-28)
= 4 * 28 - 3*37
= 4*(324-8*37)-3*37
= 4*324-35*37
= 4*324-35*(2953-9*324)
= 319*324-35*2953
= 319*(3277-2953)-35*2953
= 319*3277-354*2953
= 319*3277-354*(6230-3277)
= 673*3277-354*6230
= 673*(9507-6230)-354*6230
= 673*9507-1027*6230
= 673*9507-1027*(72779-7*9507)
= 7862*9507-1027*72779
= 7862*(155065-2*72779)-1027*72779
= 7862*155065- 16751*72779
= 7862*155065- 16751*(537974-3*155065)
= 58115*155065-16751*537974
= 58115*(1231013-2*537974)-16751*537974
= 58115*1231013-132981*537974
= 58115*1231013-132981*(1768987-1231013)
= 191096*1231013-132981*1768987
= 191096*(3000000-1768987)-132981*1768987
= 191096*3000000-324077*1768987
So, das ist jetzt garantiert fehlerlos, da ich Zeile für Zeile nachgerechnet habe. Aber ist das wirklich so ausführlich notwenig, oder geht es auch einfacher? (Fortsetzung folgt)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:45 Di 23.10.2007 | | Autor: | statler |
Das ist ganz toll, und ich glaube mal, daß es richtig ist. Bevor du volle Pulle mit d) und e) loslegst: Wie hängen die zusammen? Und hat d) eine Lösung?
Kennst du den Chinesischen Restsatz? Mit dem könnte man hier auch hantieren, aber am Ende hat man trotzdem große Zahlen, das liegt in der Natur der Sache. Euer Prof will ja eine Lösung durch Probieren verhindern, denkichmal.
Bis dann
Dieter
|
|
|
| |
|
nö Dieter und Will, den chinesischen Restsatz kapier ich jetzt nicht wirklich auch noch, scheint aber ganz passabel bei Wikipedia erklärt zu sein. Und den ELBA hab ich auch noch nicht wirklich intus oder versucht.
Habe aber jetzt mit der Darstellung der Lösung auch so meine Probleme, insbesondere bedingt durch das nette Luftpostbriefchen von Will (trotzdem erstmal tausend Dank auch an Dich.) Insbesondere weil dort mod p mit p= Primzahl steht und 3000000 ist ja nun sehr offensichtlich alles andere als eine Primzahl. Kann ich dieses Beispiel trotzdem nehmen, wenn ja wieso oder wie abgewandelt muss meine Lösung dann aussehen?
Dort steht als Beispiel sei 5 (mod 7) zu invertieren:
3*5 + (-2) * 7 = 1, also ist 3 ~ 5 ^(-1) das Inverse zu 5 (mod 7) in {Z7}
also das Inverse zu a (mod p)
es müsse aber gelten, dass a<p und p Primzahl und daraus folgt logisch, dass ggt(a,p)=1. Bei uns ist der ggT auch 1, aber halt p keine Primzahl und das Ergebnis 3 ~ 5^(-1) st mir auch nicht wirklich klar.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:55 Di 23.10.2007 | | Autor: | Snoopymaus |
:-( ich versteh das nicht, in der Vorschau ist immer meine signatur zu sehen und wenn ich abschicke is sie nicht mehr da. Sorry, ich bin nicht wirklich so unhöflich, dass ich keine Grüße drunterschreibe, ich verstehe nicht wieso die Signatur nicht erscheint??
Lieber gruß deshalb hier händisch
Snoopy
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:53 Di 23.10.2007 | | Autor: | koepper |
Hallo Snoopy,
> Insbesondere weil dort mod p mit p= Primzahl
> steht und 3000000 ist ja nun sehr offensichtlich alles
> andere als eine Primzahl. Kann ich dieses Beispiel trotzdem
> nehmen, wenn ja wieso oder wie abgewandelt muss meine
> Lösung dann aussehen?
Dort wird nur der Fall für p=Primzahl behandelt, weil dann praktischerweise alle Elemente invertierbar sind.
Du kannst aber die Schreibweise unverändert auch für diese sogenannten Restklassenringe übernehmen.
> Dort steht als Beispiel sei 5 (mod 7) zu invertieren:
> 3*5 + (-2) * 7 = 1, also ist 3 ~ 5 ^(-1) das Inverse zu 5
> (mod 7) in {Z7}
>
> also das Inverse zu a (mod p)
> es müsse aber gelten, dass a<p und p Primzahl und daraus
> folgt logisch, dass ggt(a,p)=1. Bei uns ist der ggT auch 1,
> aber halt p keine Primzahl
das reicht auch.
> und das Ergebnis 3 ~ 5^(-1) ist mir auch nicht wirklich klar.
warum nicht? rechne nach: 3 * 5 = 15, und 15 ist kongruent zu 1 (mod 7)
Nun aber zum Schluß noch eine Frage an dich:
Was ist denn nun das Inverse zu 1768987 im Restklassenring modulo 3000000 ?
Liebe Grüße
Will
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:00 Di 23.10.2007 | | Autor: | Snoopymaus |
> > und das Ergebnis 3 ~ 5^(-1) ist mir auch nicht wirklich
> klar.
>
> warum nicht?
hm, habsch vielleicht dickes fettes Brett vorm Kopf???
Das Ergebnis lautet doch in Worten: 3 kongruent 5 hoch minus 1??? Oder interpretier ich da ein Zeichen falsch?? Wenn nicht, dann kapier ich nicht woher das kommt und nicht was das heissen soll. Sorry und danke für Eure Mühe, vielleicht holzhammer mitbringen :-(
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:38 Di 23.10.2007 | | Autor: | koepper |
Hallo Snoopy,
ein einfacherer systematischer Weg ist mir nicht bekannt. Natürlich gibt es leicht abgewandelte Schreibweisen, die das ganze etwas übersichtlicher machen (siehe ELBA). In der Praxis überläßt man das idR einem Computeralgebrasystem 
Gruß
Will
|
|
|
| |
|
Also sind wir bei -7*17 = 1 - 4*30 angekommen.
Wir addieren noch 30*17 = 17*30 und erhalten
23*17 = 1 + 13*30
Also können wir x = 23 nehmen.
Ich sehe zwar, dass die Vorzeichen nicht stimmen, aber wie ich darauf komme 17 * 30 zu addieren und ob das immer so ist, das hab ich jetzt auch nicht verstanden. Und in dem briefchen von Will steht das für mich noch unklarer: Wir nehmen diese Gleichung mal modulo p (hier 30)
[Dateianhang nicht öffentlich] Wenn mir das mal jemand kurz nochmal mit anderen Worten erklären könnte, dann könnt ich endlich mal an die nächste Aufgabe gehen
Gruß Snoopy
PS: Hoffe ich habe das mit dem Bild richtig gemacht?
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:56 Di 23.10.2007 | | Autor: | leduart |
Hallo
> Also sind wir bei -7*17 = 1 - 4*30 angekommen.
hier könnt ich auch sagen -7 ist das Inverse von 17 , aber -7=0-7=30-7=23
und da wir gern nur positive Zahlen haben sagt man halt 23 ist das Inverse zu 17 (alles mod(30)
zu der andern Rechnung: um -7*17 positiv zu kriegen, dürfen wir beliebig oft 0=30 addieren. ich addiere 17*30 damit da wieder ein Vielfaches von 17 steht!
> Wir addieren noch 30*17 = 17*30 und erhalten
> 23*17 = 1 + 13*30
> Also können wir x = 23 nehmen.
Aber immer, wenn du ne negative Zahl a mod(p) hast ist p-a der positive Repräsentant.
Das brauchst du auch für deine Rechnung mit den 3000000 uund den 17.....
Da ist dein Ergebnis auch ne negative Zahl, der positive Repräsentant ist dann 3000000- der gefundenen Zahl.
>
> Ich sehe zwar, dass die Vorzeichen nicht stimmen, aber wie
> ich darauf komme 17 * 30 zu addieren und ob das immer so
> ist, das hab ich jetzt auch nicht verstanden. Und in dem
> briefchen von Will steht das für mich noch unklarer: Wir
> nehmen diese Gleichung mal modulo p (hier 30)
> [Dateianhang nicht öffentlich] Wenn mir das mal jemand kurz nochmal mit
> anderen Worten erklären könnte, dann könnt ich endlich mal
> an die nächste Aufgabe gehen
>
zu dem Text: p ist die Zahl die bei dir 30 bzw 3000000 ist, in dem Text ist das ne Primzahl, das muss dich hier nicht kümmern, das hat nur den Vorteil, dass es dann zu jeder Zahl mod(p) ein Inverses gibt.
Du wendest das an für ne beliebige Zahl p, aber dann gibts nur Inverse zu Zahlen a wo ggt(a,p)=1
dann gilt 1=r*a+s*p r>0 und s<0 oder r>0 s<0
deshalb schreib ich um mit positiven Zahlen r,s>0
a)1=r*a-s*p oder b) 1=-ra+sp
a)r*a=1+s*p also r*a=1 modp r ist Inverses zu a oder [mm] r=a^{-1}
[/mm]
b)-r*a=1-s*p ; -ra =1modp (im Text steht einfach :nimm die Gleichung mit mod:
also -r*a modp=1 modp -sp modp wegen s*p=0modp gibt das meine Gleichung.(-p=p(modp=0modp)
so jetzt die 2 Schreibweisen -rist Inverses zu a mod p -r=a^-1 aber auch -r=(-r+p) modp und -r+p ist positiv.
oder du schreibst die ursprüngliche Gleichung um:
-r*a=1-s*p addiere p*a
(p-r)*a=1+(a-s)*p daraus direkt (p-r)*a=1 modp also p-r ist Inverses zu a.
Ich hoffe es ist ein bissel klarer.
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:58 Mi 24.10.2007 | | Autor: | Snoopymaus |
> oder du schreibst die ursprüngliche Gleichung um:
> -r*a=1-s*p addiere p*a
> (p-r)*a=1+(a-s)*p daraus direkt (p-r)*a=1 modp also p-r
> ist Inverses zu a.
Cool, das ist mir wesentlich sympathischer als das mit dem hoch -1, denn das hatte ich jetzt gerade mal verstanden. Tausend Dank.
Also hätte ich jetzt anzubieten als Ergebnis:
1 = 191096*3000000-324077*1768987
-324077*1768987 - 1 = -191096*3000000
ich addiere noch 3000000*1768987
(p-r)*a=1+(a-s)*p daraus direkt (p-r)*a=1 modp also p-r ist Inverses zu a.
(3000000-324077)*1768987 - 1 = (1768987-191096)*3000000
2 675 923 * 1768987 - 1 = 1577891*3000000
also 2 675 923 ist Inverses zu 1768987 (mod 3000000)
Bin ziemlich überzeugt, dass ich das soweit jetzt dank Eurer supertollen Hilfe bis dahin gerafft habe und dass das jetzt korrekt ist.
Tausend Dank mal vorerst
Snoopy
PS (Ich ahne schon dass die letzte keine Lösung hat)
|
|
|
| |
|
(d) Invertieren Sie 1768989 modulo 3000000
ggt(1768989,3000000) > 1, da die Quersumme von beiden Zahlen eine durch 3 teilbare Zahl ist.
Wenn ich alles richtig verstanden habe, dann existiert deshalb kein Inverses zu 1768989 (mod 3000000)
Wär schonmal prima, weil viel Arbeit gespart wegen der großen Zahlen
Ist das korrekt?
gruß Snoopy
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:25 Mi 24.10.2007 | | Autor: | statler |
Guten Morgen Snoopy, ich übernehme jetzt wieder die Frühschicht.
> (d) Invertieren Sie 1768989 modulo 3000000
>
> ggt(1768989,3000000) > 1, da die Quersumme von beiden
> Zahlen eine durch 3 teilbare Zahl ist.
>
> Wenn ich alles richtig verstanden habe, dann existiert
> deshalb kein Inverses zu 1768989 (mod 3000000)
Das ist völlig richtig, ...
> Wär schonmal prima, weil viel Arbeit gespart wegen der
> großen Zahlen
... aber wenn du dich noch mit e) befassen willst/mußt/möchtest, dann steht dir doch noch etwas Gerechne bevor, allerdings mit kleineren Zahlen. Du kannst z. B. damit anfangen, das Inverse von 589663 mod 1000000 zu suchen.
Einen schönen Tag
Dieter
|
|
|
| |
|
| Aufgabe | | Lösen Sie die Gleichung 1768989 · x ~ 123 (mod 3000000). |
das Inverse von 589663 mod 1000000, das heisst also ich kann mit 3 kürzen, hätte ich vermutlich schon gefragt, da ja auch die 123 durch 3 zu kürzen geht. Aber ich kann doch nicht die 123 einfach ignorieren?
na ja, ich mach das jetzt einfach mal so wie Du sagst, vielleicht komm ich ja noch drauf wieso das so vereinfacht geht, wenn nicht wirst Du es mir schon sagen, denk ich mal.
das Inverse von 589663 mod 1000000
Nach dem euklid'schen Algorithmus ist:
1 000 000 = 1 * 589 663 + 410 337
589 663 = 1 * 410 337 + 179 326
410 337 = 2 * 179 326 + 51 685
179 326 = 3 * 51 685 + 24 271
51 685 = 2 * 24 271 + 3 143
24 271 = 7 * 3 143 + 2 270
3 143 = 1 * 2 270 + 873
2 270 = 2 * 873 + 524
873 = 1 * 524 + 349
524 = 1 * 349 + 175
349 = 1 * 175 + 174
175 = 1 * 174 + 1
1 = 175 - 174
= 175 - (349- 175)
= 2 * 175 - 349
= 2 * (524-349)-349
= 2 * 524 - 3(873-524)
= 5 * (2 270-2*873) - 3 * 873
= 5 * 2 270 - 13 * 873
= 5 * 2 270 - 13 * (3 143 - 2 270)
= 18 * 2 270 - 13 * 3 143
= 18 * (24 271 - 7 * 3 143) - 13 * 3 143
= 18 * 24 271 - 139 * 3 143
= 18 * 24 271 - 139 * (51 685 - 2 * 24 271)
= 296 * 24 271 - 139 * 51 685
= 296 * (179 326 - 3 * 51 685) - 139 * 51 685
= 296 * 179 326 - 1027 * 51 685
= 296 * 179 326 - 1027 * (410 337 - 2 * 179 326)
= 2350 * 179 326 - 1027 * 410 337
= 2350 * (589 663 - 410 337) - 1027 * 410 337
= 2350 * 589 663 - 3377 * 410 337
= 2350 * 589 663 - 3377 * (1 000 000 - 589 663)
= 5727 * 589 663 - 3377 * 1 000 000
Jetzt muss ich aber noch die 41 unterbringen?
Und nicht vergessen immer tausend Dank, ihr seid echt spitze.
Gruß Snoopy
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:17 Mi 24.10.2007 | | Autor: | leduart |
Hallo
multiplizier mal deine Gleichung 1=.... mit 3 und danach mit 41, dann siehst du, dass 41*5727 =x deine Gleichung erfüllt.
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:53 Do 25.10.2007 | | Autor: | Snoopymaus |
hm, ja, ich kanns ja gar nicht fassen. Also tausend Dank euch allen, ihr seid echt große Klasse.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:28 Do 25.10.2007 | | Autor: | leduart |
Hallo
Du hast jetzt wohl alle Ergebnisse richtig. aber mich beunruhigt, dass ihr diese Aufgaben mit den riesen Zahlen hattet. gewöhnlich ist es nicht Ziel einer Übung, so Monstren zu rechnen.
Es muss also eine Methode geben, das geschickter zu machen. Ich bin kein Zahlentheoretiker, aber wenn man die Reziproken mod 3, mod 10 mod 100 usw rechnet, muss man eigentlich schneller und einfacher zum Ziel kommen.
Habt ihr dazu nicht irgendwelche nette Sätze in der Vorlesung behandelt?
Wenn eine Zahl mod 30 ein reziprokes hat, dann ist das doc h auch reziprokes mod 3, mod 5, mod 6 usw, also mod aller Teiler. und das muss man irgendwie ausnutzen- aber ich weiss nicht wie-
Aber du hast toll durchgehalten. damit kommst du weit!
Gruss leduart
|
|
|
|
