Restklassenring < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:43 Sa 15.12.2012 | | Autor: | Coup |
| Aufgabe | | Berechne [mm] \overline{2}^{15} [/mm] in [mm] \IZ [/mm] / 31 [mm] \IZ [/mm] |
Hallo.
Also ich kenne denke ich die Vorgehensweise.
Begonnen :
1) [mm] 2^1 [/mm] = 2 [mm] \equiv [/mm] 2 denn 2 mod 31 = 2
2) [mm] 2^2 [/mm] = 4 [mm] \equiv [/mm] 4
3) [mm] 4^2 [/mm] = 16 [mm] \equiv [/mm] 16
[mm] 4)16^2 [/mm] = 256 [mm] \equiv [/mm] 8
5) [mm] 8^2 [/mm] = 64 [mm] \equiv [/mm] 2
Nun betrachte ich mir den Exponenten 15 als Binärzahl : 01111
Da ich ja von rechts nach links lese rechne ich
2*4*16*8 = 1024 mod 31 = 1
Sofern das richtig ist frage ich mich
1. Warum wird die ganze Zeit quadriert ?
2. Warum muss ich den Exponenten als Basis 10 darstellen und nur die 1er multiplizieren ? Ich verstehe also nicht recht was ich hier eigentlich ausgerechnet habe. Das Schema reicht mir ohne Verständnis zu meiner Befriedigung nicht.
lg
Micha
|
|
| |
|
> Berechne [mm]\overline{2}^{15}[/mm] in [mm]\IZ[/mm] / 31 [mm]\IZ[/mm]
Hallo,
Dein Ergebnis stimmt, die Vorghensweise finde ich nicht so überzeugend - aber Du hast nichts Falsches getan.
Ich zeig Dir, wie ich es machen würde
[mm] 2\eqiv [/mm] 2
[mm] 2^2\eqiv [/mm] 4
[mm] 2^3\eqiv [/mm] 8
[mm] 2^4\eqiv [/mm] 16
[mm] 2^5\eqiv [/mm] 1
Mit [mm] 2^5=1 [/mm] mod 31 kann ich etwas anfangen:
[mm] 2^{15}=2^{5}*2^{5}*2^{5}\eqiv [/mm] 1*1*1 = 1.
Ich greife noch kurz Dein Vorgehen auf:
Du hast
[mm] 2^{1}\equiv [/mm] 2
[mm] 2^{2^{1}}\equiv [/mm] 4
[mm] 2^{2^{2}}\equiv [/mm] 16
[mm] 2^{2^{3}}\ [/mm] equiv 8
Du hast 15 geschrieben als [mm] 1+2^{1}+2^{2}+2^{3},
[/mm]
also ist [mm] 2^{15}=2^{1+2^{1}+2^{2}+2^{3}}=2^{1}*2^{2}*2^{4}*2^{8}=2*4*16*8=2*16*4*8=32*32=\equiv [/mm] 1*1=1
LG Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:07 So 16.12.2012 | | Autor: | felixf |
Moin!
> Sofern das richtig ist frage ich mich
> 1. Warum wird die ganze Zeit quadriert ?
> 2. Warum muss ich den Exponenten als Basis 10 darstellen
> und nur die 1er multiplizieren ? Ich verstehe also nicht
> recht was ich hier eigentlich ausgerechnet habe. Das Schema
> reicht mir ohne Verständnis zu meiner Befriedigung nicht.
![[]](/images/popup.gif) Hier wird das Verfahren ausfuehrlich beschrieben. Es ist eins der (asymptotisch) effizientesten Verfahren um grosse Potenzen auszurechnen.
In diesem Fall haettest du aber auch nutzen koennen, dass das Inverse von 2 einfach anzugeben ist: $2 [mm] \cdot [/mm] 16 = 32 [mm] \equiv [/mm] 1 [mm] \pmod{31}$, [/mm] und damit ist [mm] $2^{15} \equiv 2^{16} \cdot [/mm] 16 [mm] \pmod{31}$. [/mm] Und [mm] $2^{16}$ [/mm] kannst du durch's Quadrieren ausrechnen. Damit hast du dir das Zusammenmultiplizieren der Zweierpotenzen gespart (und musst nur mit dem Inversen von 2 multiplizieren).
LG Felix
|
|
|
|
