Modulo-Rechnung & sq./mult. < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | [Dateianhang nicht öffentlich] |
Hallo!
Bei obiger Aufgabe habe ich so meine Probleme. Ich weiß nicht genau, wie ich vorgehen muss, und aus den Vorlesungsmitschriften werde ich nicht schlau.
Der erste Schritt für (a).(i) wäre wahrscheinlich
[mm] 43^{50} [/mm] = [mm] 43^{32+16+2} [/mm] = [mm] 43^{(2^{5})}*43^{(2^{4})}*43^{(2^{1})}
[/mm]
Nun weiß ich aber nicht, wie ich weiter vorgehen muss! Kann mir das bitte jemand erklären?
Danke für Eure Mühe,
Stefan.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:37 Do 20.11.2008 | | Autor: | rainerS |
Hallo!
Da die Aufgabenstellung fehlt, können wir dir nicht so recht helfen.
Ich vermute mal, du sollst eine Potenz modulo einer Zahl per Square-and-multiply berechnen. Dabei solltest du in jedem Multiplikationsschritt die modulo-Operation ausführen, um die Zwischenergebnisse halbwegs klein zu halten.
Viele Grüße
Rainer
|
|
|
| |
|
Exponent zerlegen: 50 = 2 * 5 * 5
[mm] 43^{2} \equiv [/mm] 40 mod 67
[mm] 40^{5} \equiv [/mm] 14 mod 67
[mm] 14^{5} \equiv [/mm] ? mod 67
analog andere Aufgaben
z.B. [mm] 24^{43} [/mm] = 24 * [mm] 24^{2*3*7} \equiv 2*2^{2*3*7} \equiv 2*4^{3*7} \equiv 2*5^{7} \equiv 2*5*5^{2}*5^{4} \equiv [/mm] 10*3*9 [mm] \equiv [/mm] 6 mod 11
für mögliche Rechenfehler keine Haftung
|
|
|
| |
|
> Exponent zerlegen: 50 = 2 * 5 * 5
> [mm]43^{2} \equiv[/mm] 40 mod 67
> [mm]40^{5} \equiv[/mm] 14 mod 67
> [mm]14^{5} \equiv[/mm] ? mod 67
>
> analog andere Aufgaben
>
> z.B. [mm]24^{43}[/mm] = 24 * [mm]24^{2*3*7} \equiv 2*2^{2*3*7} \equiv 2*4^{3*7} \equiv 2*5^{7} \equiv 2*5*5^{2}*5^{4} \equiv[/mm]
> 10*3*9 [mm]\equiv[/mm] 6 mod 11
>
> für mögliche Rechenfehler keine Haftung
Hallo!
Danke für deine Antwort! Ich muss also immer "diese Produktregel" ausnutzen...
Einige Fragen habe ich aber:
- Wie hast du [mm] 43^{2} [/mm] berechnet? Unsere Vorlesung ist nämlich ziemlich darauf spezialisiert, mit mehr oder weniger kleinen Zahlen zu arbeiten, und hier müsste ich ja erst die Zahl ausrechnen - da führt kein Weg dran vorbei?
- [mm] 2*4^{3*7} \equiv 2*5^{7} [/mm] mod 11 stimmt glaub ich nicht, oder?
Stefan.
|
|
|
| |
|
Hallo steppenhahn,
> > Exponent zerlegen: 50 = 2 * 5 * 5
> > [mm]43^{2} \equiv[/mm] 40 mod 67
> > [mm]40^{5} \equiv[/mm] 14 mod 67
> > [mm]14^{5} \equiv[/mm] ? mod 67
> >
> > analog andere Aufgaben
> >
> > z.B. [mm]24^{43}[/mm] = 24 * [mm]24^{2*3*7} \equiv 2*2^{2*3*7} \equiv 2*4^{3*7} \equiv 2*5^{7} \equiv 2*5*5^{2}*5^{4} \equiv[/mm]
> > 10*3*9 [mm]\equiv[/mm] 6 mod 11
> >
> > für mögliche Rechenfehler keine Haftung
>
> Hallo!
>
> Danke für deine Antwort! Ich muss also immer "diese
> Produktregel" ausnutzen...
> Einige Fragen habe ich aber:
>
> - Wie hast du [mm]43^{2}[/mm] berechnet? Unsere Vorlesung ist
> nämlich ziemlich darauf spezialisiert, mit mehr oder
> weniger kleinen Zahlen zu arbeiten, und hier müsste ich ja
> erst die Zahl ausrechnen - da führt kein Weg dran vorbei?
Ich zeige Dir das am Beispiel von [mm]40^{5} \equiv 14 \ \left(67\right)[/mm]:
Zunächst zerlege ich den Exponenten in 2er-Potenzen:
[mm]5=1*2^{2}+0*2^{1}+1*2^{0}[/mm]
Dann berechne ich
[mm]40^{1} \equiv 40 \ \left(67\right)[/mm]
[mm]40^{2} \equiv 40 * 40 \equiv 1600 \equiv 59 \ \left(67\right)[/mm]
[mm]40^{4} \equiv 59 * 59 \equiv 3481 \equiv 64 \ \left(67\right)[/mm]
Dann ist
[mm] 40^{5} \equiv 40^{4}*40^{1} \equiv 64*40 \equiv 2560 \equiv 14 \ \left(67\right)[/mm]
>
> - [mm]2*4^{3*7} \equiv 2*5^{7}[/mm] mod 11 stimmt glaub ich nicht,
> oder?
Ja, das stimmt nicht.
>
> Stefan.
Gruß
MathePower
|
|
|
| |
|
Hallo!
Danke für die bisherige Hilfe! Ich versuche mich gerade an den anderen Aufgaben, scheitere aber gerade ein wenig an mir selbst...
(a).(iv):
[mm] 19^{289} [/mm] mod 21
[mm] 19^{289}\equiv 19^{(17^{2})} [/mm] mod 21
Ich dachte, diese Umformung könnte ganz nützlich sein, aber auch hier ist mir wieder nicht richtig klar wie ich weitermachen könnte. Kann man das Quadrat im Exponenten irgendwie ausnutzen?
Mein zweiter Ansatz wäre
[mm] 19^{289} \equiv 19^{256 + 32 + 1} \equiv 19^{(2^{8})}*19^{(2^{5})} *19^{(2^{0})} [/mm] mod 21
Muss ich jetzt wirklich rechnen:
[mm] 19^{(2^{0})} \equiv [/mm] 19 mod 21
[mm] 19^{(2^{1})} \equiv [/mm] 19*19 [mm] \equiv [/mm] 361 [mm] \equiv [/mm] 4 mod 21
[mm] 19^{(2^{2})} \equiv [/mm] 4*4 [mm] \equiv [/mm] 16 mod 21
[mm] 19^{(2^{3})} \equiv [/mm] 16*16 [mm] \equiv [/mm] 256 [mm] \equiv [/mm] 4 mod 21
[mm] 19^{(2^{4})} \equiv [/mm] 4*4 [mm] \equiv [/mm] 16 mod 21
[mm] 19^{(2^{5})} \equiv [/mm] 16*16 [mm] \equiv [/mm] 256 [mm] \equiv [/mm] 4 mod 21
[mm] 19^{(2^{6})} \equiv [/mm] 4*4 [mm] \equiv [/mm] 16 mod 21
[mm] 19^{(2^{7})} \equiv [/mm] 16*16 [mm] \equiv [/mm] 256 [mm] \equiv [/mm] 4 mod 21
[mm] 19^{(2^{8})} \equiv [/mm] 4*4 [mm] \equiv [/mm] 16 mod 21
D.h.
[mm] 19^{289} \equiv 19^{(2^{8})}*19^{(2^{5})} *19^{(2^{0})} \equiv [/mm] 16*4*19 [mm] \equiv [/mm] 64*19 [mm] \equiv [/mm] 19 mod 21
Ich frage das, weil mir das ziemlich viel Rechenaufwand erscheint? Ist es Zufall, dass wieder 19 rauskommt oder hat das einen bestimmten Grund?
(a).(v)
[mm] 2^{45} [/mm] mod 100
Mit dieser Aufgabe berechnet man doch praktisch die letzten beiden Ziffern von [mm] 2^{45}, [/mm] oder? Muss man hier wieder so vorgehen:
[mm] 2^{45} [/mm] = [mm] 2^{32 + 8 + 4 + 1} [/mm] = [mm] 2^{(2^{5})}*2^{(2^{3})}*2^{(2^{2})}*2^{(2^{0})}, [/mm] also
[mm] 2^{2^{0}} \equiv [/mm] 2 mod 100
[mm] 2^{2^{1}} \equiv [/mm] 2*2 [mm] \equiv [/mm] 4 mod 100
[mm] 2^{2^{2}} \equiv [/mm] 4*4 [mm] \equiv [/mm] 16 mod 100
[mm] 2^{2^{3}} \equiv [/mm] 16*16 [mm] \equiv [/mm] 256 [mm] \equiv [/mm] 56 mod 100
[mm] 2^{2^{4}} \equiv [/mm] 56*56 [mm] \equiv [/mm] 3136 [mm] \equiv [/mm] 36 mod 100
[mm] 2^{2^{5}} \equiv [/mm] 36*36 [mm] \equiv [/mm] 1296 [mm] \equiv [/mm] 96 mod 100
d.h.
[mm] 2^{45} \equiv 2^{(2^{5})}*2^{(2^{3})}*2^{(2^{2})}*2^{(2^{0})} \equiv [/mm] 96*56*16*2 [mm] \equiv [/mm] 96*12*16 [mm] \equiv [/mm] 96*92 [mm] \equiv [/mm] 8832 [mm] \equiv [/mm] 32 mod 100.
Lohnt es sich vielleicht manchmal, andere Potenzen als die 2 zu benutzen oder das ganz anders anzugehen?
Vielen Dank für Eure Mühe,
Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:21 Fr 21.11.2008 | | Autor: | leduart |
Hallo
erst mal zu der 19 mod 21
hier ist alles viel schneller wenn du schreibst 19=-2mod21
2. dass [mm] 2^{10}=1024 [/mm] also 24mod 10 ist weiss man im Zeitalter der bits. oder [mm] 2^9=12 [/mm] mod100 also nur noch 12^5mod100 usw.
oft ist es auch nuetzlich mit kleinen neg. Zahlen zu rechnen
Gruss leduart
|
|
|
|
