Anwendung des Chin. Restsatzes < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | 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
>
|
|
|
|
