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" - Anwendung des Chin. Restsatzes
Anwendung des Chin. Restsatzes < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Anwendung des Chin. Restsatzes: Berechnung mod p,q mit p,q tf
Status: (Frage) beantwortet Status 
Datum: 01:19 Di 29.11.2016
Autor: Marcel

Aufgabe
Zu berechnen ist [mm] $24^{95}$ [/mm] mod $323$ (beachte $323=17*19$)



Hallo,

ich habe in einem Buch das Ergebnis [mm] $24^{95} \equiv [/mm] 294$ mod 323
gesehen, wobei die Rechnung dahingehend fehlt. Ich habe mir nun folgende
Rechnung überlegt, und die Frage ist, ob diese korrekt ist, und ob man
sie vielleicht sogar auf Primfaktorzerlegungen einer Zahl n übertragen kann,
um große Zahlen modulo n mithilfe eines Kongruenzsystems mit kleineren
Modulen "elegant" zu berechnen.

Und zwar gilt ja, dass wenn $x [mm] \equiv [/mm] a$ mod n und $t [mm] \mid [/mm] n$ ist, dass dann
auch $x [mm] \equiv [/mm] a$ mod t ist. Weiterhin wende ich den kleinen Fermat und
bekannte Rechenregeln für Kongruenzen an und bemühe den erweiterten
euklidischen Algorithmus für eine Hilfsrechnung:
Ich setze [mm] $x=24^{95}$. [/mm]

Dann gilt bzgl. des Moduls 17 (es ist $17 [mm] \mid [/mm] 323$)

    [mm] $x=24^{95} \equiv 7^{95} \equiv (7^{16})*7^{15} \equiv 7^{15}$ [/mm]
    $= [mm] 7*7^{14} \equiv 7*15^7=105*(15^2)^3 \equiv 3*4^3 \equiv [/mm] 5$ mod 17.

Weiter gilt bzgl. des Moduls 19 (es ist $323/17=19$)

    [mm] $x=24^{95} \equiv 5^{95} \equiv (5^{18})^5*5^5 \equiv [/mm] 5*6*6$
    [mm] $\equiv [/mm] 5*17=85=4*19+9 [mm] \equiv [/mm] 9$ mod 19.

Offensichtlich ist ggT(17,19)=1 und etwa mit dem erweiterten euklidischen
Algorithmus ergibt sich (ich habe erstmal einfach nur den Vorfaktor bei der
19 berechnet)

    $-8*19+y*17=1$ und damit [mm] $y=\red{9}\,.$ [/mm]

Nach der 1. Version des Chinesischen Restsatzes (s.u.) aus dem Buch "Elementare
und algebraische Zahlentheorie" von Müller-Stach/Piontkowski (dort steht
auch die obige Kongruenz) gilt dann, dass das System

    $x [mm] \equiv \green{5}$ [/mm] mod 17, $x [mm] \equiv \blue{9}$ [/mm] mod 19

gleichwertig ist zu

    $x [mm] \equiv \green{5}-\red{9}*17*(\green{5}-\blue{9})/1$ [/mm] mod $17*19/1$,

also

    [mm] $x=24^{95} \equiv [/mm] 617 [mm] \equiv [/mm] 617-323=294$ mod $323$.

Ergänzung:

In dem Buch steht der genannte Chinesische Restsatz sinngemäß wie
folgt:
Das System der Kongruenzen $x [mm] \equiv [/mm] a$ mod n und $x [mm] \equiv [/mm] b$ mod m
ist genau dann lösbar, wenn [mm] $\ggT(m,n) [/mm] | (a-b)$, und im Falle der Lösbarkeit
gilt mit [mm] $d:=\ggT(n,m)=yn+zm$ [/mm] mit geeigneten $y,z [mm] \in \IZ$ [/mm] dann, dass das obige
System gleichwertig ist zu

    $x [mm] \equiv [/mm] a-yn(a-b)/d$ mod $mn/d$.

P.S. Die Rechnung oben ist zwar sicher nicht die schönste, aber in einem
gewissen Sinne hat sie doch ihre Eleganz. Vielleicht habe ich es mir aber
doch zu kompliziert gemacht und es gibt noch einen schöneren Weg?

Klar ist natürlich, dass man ziemlich elementar auch "einfach" mit dem Modul
323 rechnen kann

    [mm] $24^{95}= 24*(24^2)^{47} \equiv 24*(253)^47=(24*253)*(253^2)^{23}$ [/mm]
    [mm] $\equiv 258*55^{23}=(258*55)*(55^2)^{11} \equiv 301*118^{11}$ [/mm]
    [mm] $=(310*118)*(118^2)^5 \equiv (311*35)*(35^2)^2 \equiv 226*256^2 \equiv [/mm] 226*290 [mm] \equiv [/mm] 294$ mod 323.


Den obigen Weg finde ich aber schöner, weil man mit Fermat rechnen kann
und dadurch auch "Zahlen schneller kleingeprügelt" bekommt.

Btw.: Natürlich habe ich oben zudem meinen Taschenrechner als Hilfe
benutzt. ;-)

P.P.S. Wenn oben [mm] $24^{95}$ [/mm] mod [mm] $17^2*19$ [/mm] zu berechnen gewesen wäre,
so hätte ich analoges doch sicher auch mit einem System, dass aus einer
Kongruenz mit dem Modul [mm] $17^{\red{2}}$ [/mm] und einer Kongruenz mit dem Modul
19 machen können. Könnte man das vielleicht aber sogar noch auf ein
System nur mit dem Modul 17 und dem Modul 19 reduzieren? Das erscheint
mir nämlich nicht möglich.

Sofern meine Überlegungen oben korrekt sind und ich nicht doch irgendwo
einem Trugschluss unterliege und das richtige Ergebnis dummerweise
einfach nur durch Zufall stimmt (was ich allerdings nicht wirklich glaube ;-) ).

Gruß,
  Marcel

        
Bezug
Anwendung des Chin. Restsatzes: Antwort
Status: (Antwort) fertig Status 
Datum: 13:45 Sa 03.12.2016
Autor: donquijote

Hallo,
deine Überlegungen scheinen mir korrekt und du hast es ja eigentlich auch selbst begründet. Grundsätzlich kannst du im Fall ggT(m,n)=1 jede Rechnung modulo [mm]m*n[/mm] getrennt modulo m und modulo n durchführen und das Ergebnis dann mit dem chinesischen Restsatz "zusammensetzen". Damit lässt sich in vielen Fällen der Rechenaufwand signifikant verringern, wie dein Beispiel zeigt.
Im allgemeinen Fall eines Moduls [mm]n=p_1^{r_1}*..*p_{k}^{r_k}[/mm] heißt das, dass du für jeden Primfaktor modulo [mm]p_i^{r_i}[/mm] rechnen kannst und daraus das Ergebnis modulo n bekommst.

> Zu berechnen ist [mm]24^{95}[/mm] mod [mm]323[/mm] (beachte [mm]323=17*19[/mm])
>  
>
> Hallo,
>  
> ich habe in einem Buch das Ergebnis [mm]24^{95} \equiv 294[/mm] mod
> 323
>  gesehen, wobei die Rechnung dahingehend fehlt. Ich habe
> mir nun folgende
>  Rechnung überlegt, und die Frage ist, ob diese korrekt
> ist, und ob man
> sie vielleicht sogar auf Primfaktorzerlegungen einer Zahl n
> übertragen kann,
> um große Zahlen modulo n mithilfe eines Kongruenzsystems
> mit kleineren
>  Modulen "elegant" zu berechnen.
>  
> Und zwar gilt ja, dass wenn [mm]x \equiv a[/mm] mod n und [mm]t \mid n[/mm]
> ist, dass dann
>  auch [mm]x \equiv a[/mm] mod t ist. Weiterhin wende ich den kleinen
> Fermat und
>  bekannte Rechenregeln für Kongruenzen an und bemühe den
> erweiterten
>  euklidischen Algorithmus für eine Hilfsrechnung:
>  Ich setze [mm]x=24^{95}[/mm].
>  
> Dann gilt bzgl. des Moduls 17 (es ist [mm]17 \mid 323[/mm])
>  
> [mm]x=24^{95} \equiv 7^{95} \equiv (7^{16})*7^{15} \equiv 7^{15}[/mm]
>  
>     [mm]= 7*7^{14} \equiv 7*15^7=105*(15^2)^3 \equiv 3*4^3 \equiv 5[/mm]
> mod 17.
>  
> Weiter gilt bzgl. des Moduls 19 (es ist [mm]323/17=19[/mm])
>  
> [mm]x=24^{95} \equiv 5^{95} \equiv (5^{18})^5*5^5 \equiv 5*6*6[/mm]
>  
>     [mm]\equiv 5*17=85=4*19+9 \equiv 9[/mm] mod 19.
>  
> Offensichtlich ist ggT(17,19)=1 und etwa mit dem
> erweiterten euklidischen
>  Algorithmus ergibt sich (ich habe erstmal einfach nur den
> Vorfaktor bei der
>  19 berechnet)
>  
> [mm]-8*19+y*17=1[/mm] und damit [mm]y=\red{9}\,.[/mm]
>  
> Nach der 1. Version des Chinesischen Restsatzes (s.u.) aus
> dem Buch "Elementare
>  und algebraische Zahlentheorie" von
> Müller-Stach/Piontkowski (dort steht
>  auch die obige Kongruenz) gilt dann, dass das System
>  
> [mm]x \equiv \green{5}[/mm] mod 17, [mm]x \equiv \blue{9}[/mm] mod 19
>  
> gleichwertig ist zu
>  
> [mm]x \equiv \green{5}-\red{9}*17*(\green{5}-\blue{9})/1[/mm] mod
> [mm]17*19/1[/mm],
>  
> also
>  
> [mm]x=24^{95} \equiv 617 \equiv 617-323=294[/mm] mod [mm]323[/mm].
>  
> Ergänzung:
>  
> In dem Buch steht der genannte Chinesische Restsatz
> sinngemäß wie
> folgt:
>  Das System der Kongruenzen [mm]x \equiv a[/mm] mod n und [mm]x \equiv b[/mm]
> mod m
>  ist genau dann lösbar, wenn [mm]\ggT(m,n) | (a-b)[/mm], und im
> Falle der Lösbarkeit
>  gilt mit [mm]d:=\ggT(n,m)=yn+zm[/mm] mit geeigneten [mm]y,z \in \IZ[/mm]
> dann, dass das obige
>  System gleichwertig ist zu
>  
> [mm]x \equiv a-yn(a-b)/d[/mm] mod [mm]mn/d[/mm].
>  
> P.S. Die Rechnung oben ist zwar sicher nicht die schönste,
> aber in einem
>  gewissen Sinne hat sie doch ihre Eleganz. Vielleicht habe
> ich es mir aber
>  doch zu kompliziert gemacht und es gibt noch einen
> schöneren Weg?
>  
> Klar ist natürlich, dass man ziemlich elementar auch
> "einfach" mit dem Modul
>  323 rechnen kann
>  
> [mm]24^{95}= 24*(24^2)^{47} \equiv 24*(253)^47=(24*253)*(253^2)^{23}[/mm]
>  
>     [mm]\equiv 258*55^{23}=(258*55)*(55^2)^{11} \equiv 301*118^{11}[/mm]
>  
>     [mm]=(310*118)*(118^2)^5 \equiv (311*35)*(35^2)^2 \equiv 226*256^2 \equiv 226*290 \equiv 294[/mm]
> mod 323.
>  
>
> Den obigen Weg finde ich aber schöner, weil man mit Fermat
> rechnen kann
>  und dadurch auch "Zahlen schneller kleingeprügelt"
> bekommt.
>  
> Btw.: Natürlich habe ich oben zudem meinen Taschenrechner
> als Hilfe
> benutzt. ;-)
>  
> P.P.S. Wenn oben [mm]24^{95}[/mm] mod [mm]17^2*19[/mm] zu berechnen gewesen
> wäre,
>  so hätte ich analoges doch sicher auch mit einem System,
> dass aus einer
>  Kongruenz mit dem Modul [mm]17^{\red{2}}[/mm] und einer Kongruenz
> mit dem Modul
>  19 machen können.

Ja, das stimmt.

> Könnte man das vielleicht aber sogar
> noch auf ein
>  System nur mit dem Modul 17 und dem Modul 19 reduzieren?
> Das erscheint
>  mir nämlich nicht möglich.

Auch da stimme ich dir zu. Eine Zahl modulo 289 ist nicht eindeutig bestimmt, wenn du sie modulo 17 kennst.

>  
> Sofern meine Überlegungen oben korrekt sind und ich nicht
> doch irgendwo
>  einem Trugschluss unterliege und das richtige Ergebnis
> dummerweise
> einfach nur durch Zufall stimmt (was ich allerdings nicht
> wirklich glaube ;-) ).
>
> Gruß,
>    Marcel


Bezug
                
Bezug
Anwendung des Chin. Restsatzes: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:45 Mo 19.12.2016
Autor: Marcel

Hallo,

> Hallo,
>  deine Überlegungen scheinen mir korrekt und du hast es ja
> eigentlich auch selbst begründet. Grundsätzlich kannst du
> im Fall ggT(m,n)=1 jede Rechnung modulo [mm]m*n[/mm] getrennt modulo
> m und modulo n durchführen und das Ergebnis dann mit dem
> chinesischen Restsatz "zusammensetzen". Damit lässt sich
> in vielen Fällen der Rechenaufwand signifikant verringern,
> wie dein Beispiel zeigt.
>  Im allgemeinen Fall eines Moduls
> [mm]n=p_1^{r_1}*..*p_{k}^{r_k}[/mm] heißt das, dass du für jeden
> Primfaktor modulo [mm]p_i^{r_i}[/mm] rechnen kannst und daraus das
> Ergebnis modulo n bekommst.


Danke für die Kontrolle; das ist sehr schön, zu wissen. :-)
  
Gruß,
  Marcel

> > Zu berechnen ist [mm]24^{95}[/mm] mod [mm]323[/mm] (beachte [mm]323=17*19[/mm])
>  >  
> >
> > Hallo,
>  >  
> > ich habe in einem Buch das Ergebnis [mm]24^{95} \equiv 294[/mm] mod
> > 323
>  >  gesehen, wobei die Rechnung dahingehend fehlt. Ich habe
> > mir nun folgende
>  >  Rechnung überlegt, und die Frage ist, ob diese korrekt
> > ist, und ob man
> > sie vielleicht sogar auf Primfaktorzerlegungen einer Zahl n
> > übertragen kann,
> > um große Zahlen modulo n mithilfe eines Kongruenzsystems
> > mit kleineren
>  >  Modulen "elegant" zu berechnen.
>  >  
> > Und zwar gilt ja, dass wenn [mm]x \equiv a[/mm] mod n und [mm]t \mid n[/mm]
> > ist, dass dann
>  >  auch [mm]x \equiv a[/mm] mod t ist. Weiterhin wende ich den
> kleinen
> > Fermat und
>  >  bekannte Rechenregeln für Kongruenzen an und bemühe
> den
> > erweiterten
>  >  euklidischen Algorithmus für eine Hilfsrechnung:
>  >  Ich setze [mm]x=24^{95}[/mm].
>  >  
> > Dann gilt bzgl. des Moduls 17 (es ist [mm]17 \mid 323[/mm])
>  >  
> > [mm]x=24^{95} \equiv 7^{95} \equiv (7^{16})*7^{15} \equiv 7^{15}[/mm]
>  
> >  

> >     [mm]= 7*7^{14} \equiv 7*15^7=105*(15^2)^3 \equiv 3*4^3 \equiv 5[/mm]

> > mod 17.
>  >  
> > Weiter gilt bzgl. des Moduls 19 (es ist [mm]323/17=19[/mm])
>  >  
> > [mm]x=24^{95} \equiv 5^{95} \equiv (5^{18})^5*5^5 \equiv 5*6*6[/mm]
>  
> >  

> >     [mm]\equiv 5*17=85=4*19+9 \equiv 9[/mm] mod 19.

>  >  
> > Offensichtlich ist ggT(17,19)=1 und etwa mit dem
> > erweiterten euklidischen
>  >  Algorithmus ergibt sich (ich habe erstmal einfach nur
> den
> > Vorfaktor bei der
>  >  19 berechnet)
>  >  
> > [mm]-8*19+y*17=1[/mm] und damit [mm]y=\red{9}\,.[/mm]
>  >  
> > Nach der 1. Version des Chinesischen Restsatzes (s.u.) aus
> > dem Buch "Elementare
>  >  und algebraische Zahlentheorie" von
> > Müller-Stach/Piontkowski (dort steht
>  >  auch die obige Kongruenz) gilt dann, dass das System
>  >  
> > [mm]x \equiv \green{5}[/mm] mod 17, [mm]x \equiv \blue{9}[/mm] mod 19
>  >  
> > gleichwertig ist zu
>  >  
> > [mm]x \equiv \green{5}-\red{9}*17*(\green{5}-\blue{9})/1[/mm] mod
> > [mm]17*19/1[/mm],
>  >  
> > also
>  >  
> > [mm]x=24^{95} \equiv 617 \equiv 617-323=294[/mm] mod [mm]323[/mm].
>  >  
> > Ergänzung:
>  >  
> > In dem Buch steht der genannte Chinesische Restsatz
> > sinngemäß wie
> > folgt:
>  >  Das System der Kongruenzen [mm]x \equiv a[/mm] mod n und [mm]x \equiv b[/mm]
> > mod m
>  >  ist genau dann lösbar, wenn [mm]\ggT(m,n) | (a-b)[/mm], und im
> > Falle der Lösbarkeit
>  >  gilt mit [mm]d:=\ggT(n,m)=yn+zm[/mm] mit geeigneten [mm]y,z \in \IZ[/mm]
> > dann, dass das obige
>  >  System gleichwertig ist zu
>  >  
> > [mm]x \equiv a-yn(a-b)/d[/mm] mod [mm]mn/d[/mm].
>  >  
> > P.S. Die Rechnung oben ist zwar sicher nicht die schönste,
> > aber in einem
>  >  gewissen Sinne hat sie doch ihre Eleganz. Vielleicht
> habe
> > ich es mir aber
>  >  doch zu kompliziert gemacht und es gibt noch einen
> > schöneren Weg?
>  >  
> > Klar ist natürlich, dass man ziemlich elementar auch
> > "einfach" mit dem Modul
>  >  323 rechnen kann
>  >  
> > [mm]24^{95}= 24*(24^2)^{47} \equiv 24*(253)^47=(24*253)*(253^2)^{23}[/mm]
>  
> >  

> >     [mm]\equiv 258*55^{23}=(258*55)*(55^2)^{11} \equiv 301*118^{11}[/mm]

>  
> >  

> >     [mm]=(310*118)*(118^2)^5 \equiv (311*35)*(35^2)^2 \equiv 226*256^2 \equiv 226*290 \equiv 294[/mm]

> > mod 323.
>  >  
> >
> > Den obigen Weg finde ich aber schöner, weil man mit Fermat
> > rechnen kann
>  >  und dadurch auch "Zahlen schneller kleingeprügelt"
> > bekommt.
>  >  
> > Btw.: Natürlich habe ich oben zudem meinen Taschenrechner
> > als Hilfe
> > benutzt. ;-)
>  >  
> > P.P.S. Wenn oben [mm]24^{95}[/mm] mod [mm]17^2*19[/mm] zu berechnen gewesen
> > wäre,
>  >  so hätte ich analoges doch sicher auch mit einem
> System,
> > dass aus einer
>  >  Kongruenz mit dem Modul [mm]17^{\red{2}}[/mm] und einer
> Kongruenz
> > mit dem Modul
>  >  19 machen können.
>
> Ja, das stimmt.
>  
> > Könnte man das vielleicht aber sogar
> > noch auf ein
>  >  System nur mit dem Modul 17 und dem Modul 19
> reduzieren?
> > Das erscheint
>  >  mir nämlich nicht möglich.
>  
> Auch da stimme ich dir zu. Eine Zahl modulo 289 ist nicht
> eindeutig bestimmt, wenn du sie modulo 17 kennst.
>  
> >  

> > Sofern meine Überlegungen oben korrekt sind und ich nicht
> > doch irgendwo
>  >  einem Trugschluss unterliege und das richtige Ergebnis
> > dummerweise
> > einfach nur durch Zufall stimmt (was ich allerdings nicht
> > wirklich glaube ;-) ).
> >
> > Gruß,
>  >    Marcel
>  


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


^ Seitenanfang ^
www.vorhilfe.de