Kongruenz mit hoher Potenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:51 Fr 10.05.2013 | | Autor: | Rubix |
| Aufgabe | | [mm] 13^{64} [/mm] (mod 61) und [mm] 15^{92} [/mm] (mod 65). |
Hallo,
es geht eigentlich nur um zwei Kongruenzen. Finde aber keinen sinnvollen Ansatz zur Lösung. Das Problem ist, dass ich den Satz von Euler oder Ähnliches nicht verwenden darf. Es gibt vermutlich irgendwelche Zerlegungen der Zahlen die einem das Leben einfacher machen.
Wäre für eine Lösungsidee sehr dankbar.
Gruß Rubix
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Rubix,
> [mm]13^{64}[/mm] (mod 61) und [mm]15^{92}[/mm] (mod 65).
> Hallo,
>
> es geht eigentlich nur um zwei Kongruenzen. Finde aber
> keinen sinnvollen Ansatz zur Lösung. Das Problem ist, dass
> ich den Satz von Euler oder Ähnliches nicht verwenden
> darf. Es gibt vermutlich irgendwelche Zerlegungen der
> Zahlen die einem das Leben einfacher machen.
Zerlege die Potenzen sinnvoll.
Es ist etwa [mm]13^3=2197 \ \equiv \ 1 \ \mod(61)[/mm]
Denn [mm]2197=36\cdot{}61+1[/mm]
Kommst du damit weiter?
>
> Wäre für eine Lösungsidee sehr dankbar.
>
> Gruß Rubix
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:57 Fr 10.05.2013 | | Autor: | Rubix |
Hallo,
vielen Dank. Ja das hilft mir weiter.
Gruß
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:51 Fr 10.05.2013 | | Autor: | abakus |
> [mm]13^{64}[/mm] (mod 61) und [mm]15^{92}[/mm] (mod 65).
> Hallo,
>
> es geht eigentlich nur um zwei Kongruenzen. Finde aber
> keinen sinnvollen Ansatz zur Lösung. Das Problem ist, dass
> ich den Satz von Euler oder Ähnliches nicht verwenden
> darf. Es gibt vermutlich irgendwelche Zerlegungen der
> Zahlen die einem das Leben einfacher machen.
>
> Wäre für eine Lösungsidee sehr dankbar.
Hallo,
auf [mm] $13^{60}$ [/mm] könnte man schon mal den kleinen Fermat loslassen...
Gruß Abakus
>
> Gruß Rubix
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
Hallo Rubix,
bei der anderen Aufgabe geht es ähnlich, allerdings...
> [mm]13^{64}[/mm] (mod 61) und [mm]15^{92}[/mm] (mod 65).
> Hallo,
>
> es geht eigentlich nur um zwei Kongruenzen. Finde aber
> keinen sinnvollen Ansatz zur Lösung. Das Problem ist, dass
> ich den Satz von Euler oder Ähnliches
Was heißt denn "Ähnliches"? Wie ist es denn z.B. mit dem kleinen Fermat?
> nicht verwenden
> darf. Es gibt vermutlich irgendwelche Zerlegungen der
> Zahlen die einem das Leben einfacher machen.
Um [mm] 15^{92}\mod{65} [/mm] zu bestimmen, würde ich hier auf jeden Fall den chinesischen Restsatz benutzen und getrennt voneinander [mm] 15^{92}\mod{5} [/mm] und [mm] 15^{92}\mod{13} [/mm] bestimmen. Dabei ist es z.B. nützlich, möglich schnell [mm] 2^6\equiv-1\mod{13} [/mm] zu finden...
Im übrigen gehen beide Aufgaben auch ziemlich schnell händisch mit der "square and multiply"-Methode zu lösen; die klappt immer und ohne großes Nachdenken. Wenn Ihr das noch nicht hattet, schlags mal nach.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:30 Sa 11.05.2013 | | Autor: | Rubix |
Hallo ihr beiden,
diese Sätze sind mir eigentlich weitestgehend bekannt. Sie wurden allerdings alle noch nicht in der Vorlesung behandelt die ich besuche. Wobei ich mich da frage, worin dann der Sinn einer solchen Aufgabe bestehen soll .
Danke jedenfalls für den Hinweis mit der Square and Multiply-Methode. Das werde ich dann eben nun so machen.
Gruß Rubix
|
|
|
|
