www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Invertieren modulo
Invertieren modulo < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Invertieren modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 01:27 Di 23.10.2007
Autor: Snoopymaus

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


        
Bezug
Invertieren modulo: b) als Beispiel
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Invertieren modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 08:41 Di 23.10.2007
Autor: Snoopymaus

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

Bezug
                        
Bezug
Invertieren modulo: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                        
Bezug
Invertieren modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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]Datei-Anhang

Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
Bezug
                
Bezug
Invertieren modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:21 Di 23.10.2007
Autor: Snoopymaus

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.

Bezug
                        
Bezug
Invertieren modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Invertieren modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:34 Di 23.10.2007
Autor: Snoopymaus

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)

Bezug
                                
Bezug
Invertieren modulo: Kompliment
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                        
Bezug
Invertieren modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:53 Di 23.10.2007
Autor: Snoopymaus

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.

Bezug
                                                
Bezug
Invertieren modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                
Bezug
Invertieren modulo: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                        
Bezug
Invertieren modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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 :-(

Bezug
                                
Bezug
Invertieren modulo: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Invertieren modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:46 Di 23.10.2007
Autor: Snoopymaus

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]
Bezug
                        
Bezug
Invertieren modulo: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Invertieren modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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)




Bezug
                                        
Bezug
Invertieren modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 03:02 Mi 24.10.2007
Autor: Snoopymaus

(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

Bezug
                                                
Bezug
Invertieren modulo: und e)?
Status: (Antwort) fertig Status 
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

Bezug
                                                        
Bezug
Invertieren modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:47 Mi 24.10.2007
Autor: Snoopymaus

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



Bezug
                                                                
Bezug
Invertieren modulo: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                        
Bezug
Invertieren modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                                                
Bezug
Invertieren modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de