Modulo rechnen < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:39 Do 14.04.2016 | | Autor: | JXner |
| Aufgabe | a) 2^512 mod 124
b) 3^723 mod 141
c) 4^983 mod 131
d) 5^676 mod 111
e) 6^205 mod 136 |
Guten Abend ^^
ich bräuchte hilfestellung zu den obigen Aufgaben.
Bisher habe ich das wie folgt gerechnet, aber dieser Ansatz scheint hier nicht mehr zu funktionieren:
Bsp.: [mm] 2^{272} [/mm] mod 131
=> [mm] 2^{12} [/mm] = 4096
=> 4096 mod 131 = 31
Würde mich freuen, wenn jemand eine Teilaufgabe vorrechnen könnte, sodass ich ein Anschauungsbeispiel habe.
Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:16 Do 14.04.2016 | | Autor: | abakus |
> a) 2^512 mod 124
> b) 3^723 mod 141
> c) 4^983 mod 131
> d) 5^676 mod 111
> e) 6^205 mod 136
> Guten Abend ^^
>
> ich bräuchte hilfestellung zu den obigen Aufgaben.
> Bisher habe ich das wie folgt gerechnet, aber dieser
> Ansatz scheint hier nicht mehr zu funktionieren:
>
> Bsp.: [mm]2^{272}[/mm] mod 131
> => [mm]2^{12}[/mm] = 4096
> => 4096 mod 131 = 31
>
> Würde mich freuen, wenn jemand eine Teilaufgabe vorrechnen
> könnte, sodass ich ein Anschauungsbeispiel habe.
>
> Grüße
124 liegt in der Nähe der Zweierpotenz [mm] 128=$2^7$.
[/mm]
Es gilt
[mm] $2^7$=128$\equiv$ [/mm] 4 mod 124, also [mm] $2^7$$\equiv$ $2^2$ [/mm] mod 124.
Nun ist 511=73*7, also ist [mm] $2^{511}=(2^7)^{73}$.
[/mm]
Das ist dann also kongruent zu [mm] $(2^2)^{73}$...
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:30 Do 14.04.2016 | | Autor: | JXner |
Kann deinem Gedankengang nicht folgen.
[mm] (2^2)^73 [/mm] = 18 mod 124 ?
Und in wie fern bringt mich so etwas weiter?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:36 Do 14.04.2016 | | Autor: | JXner |
Ich sitze etwas auf dem Schlauch ...
warum löst du das ganze nach [mm] (2^2)^73 [/mm] auf?
|
|
|
| |
|
> warum löst du das ganze nach $ [mm] (2^2)^{73} [/mm] $ auf?
Das tut man lediglich um die Potenz erstmal zu verringern.
Wie abakus darauf kommt, hat er erklärt.
Auf eine ähnliche Art reduziert man die Potenz immer weiter, bis man das Ergebnis schließlich ablesen kann.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:57 Do 14.04.2016 | | Autor: | JXner |
Ich wäre über einen vollständigen Lösungsweg ziemlich dankbar.
Es liegt mir besser Sachen nachzuvollziehen und das ganze dann durch weitere Aufgaben zu vertiefen.
|
|
|
| |
|
Moin,
guck:
[mm] 2^{512} [/mm] (mod 124)=???
Jetzt überlege ich mir: "2 hoch was ist in der Nähe von 124?"
Antwort: es ist [mm] 2^7=128\equiv [/mm] 4 (mod 124).
Also
[mm] 2^{512 } =2^{7*73+1}=(2^7)^{73}*2\equiv 4^{73}*2
[/mm]
[mm] =2^{146}*2=2^{7*20+6}*2=(2^7)^{20}*2^6*2 =(2^7)^{20}*2^7\equiv 4^{20}*4
[/mm]
[mm] =4^{21}=2^{42}=2^{7*4}=(2^7)^4\equiv 4^4 [/mm]
=128 [mm] \equiv [/mm] 4 (mod 124)
LG Angela
|
|
|
|
