zahlen mit hoher potenz und mod berechnen |
| 24.01.2010, 03:58 | wrock | Auf diesen Beitrag antworten » |
| zahlen mit hoher potenz und mod berechnen 7^47 kann ich mit der Binäre Exponentiation berechnen. Allerdings is dann ja die Zahl trotzdem so imens hoch das man damit nicht wirklich rechnen kann. Wie kann ich sowas lösen? lg lukas |
||
| 24.01.2010, 06:38 | kiste | Auf diesen Beitrag antworten » |
Du kannst auch mod 3 5 und 8 rechnen nach dem chinesischen Restsatz(3*5*8=120) Dort kannst du dann Sätze wie Euler und den kleinen Fermat benutzen um den Exponent zu verkleinern, speziell mod 8(und auch mod 3 etwas ähnliches) kannst du nutzen dass 7 = -1 mod 8 ist |
||
| 24.01.2010, 13:10 | wrock | Auf diesen Beitrag antworten » |
mmm....also wenn ich das richtig verstehe: 120 wird faktorisiert? und dann kann ich einfach eines dieser faktoren nutzen? Und wie verkleinere ich jetzt die Potenz? Satz vnon euler y^(n)=1 mod n unter der bedingung ggT(a, n)=1 also 7= 1 mod 8??? |
||
| 24.01.2010, 13:21 | kiste | Auf diesen Beitrag antworten » |
Du kannst es erst einmal modulo den einzelnen Primfaktorpotenzen rechnen(3,5,8). Dann musst du eben das Gleichungssystem was dabei rauskommt wieder berechnen. Den Satz von Euler hast du falsch angegeben. 7 ist nicht gleich 1 mod 8! |
||
| 24.01.2010, 14:46 | wrock | Auf diesen Beitrag antworten » |
7= -1 mod 8 stimmt aber oder? wäre das in diesem fall auch die Lösung? wenn weis ich noch immer nicht ganz sicher wie ich dahinkomme. 7^47 mod 120 7^47 mod (3,5,8) ////3,5,8 durch die primfaktorzerlegung ("Du kannst es erst einmal modulo den einzelnen Primfaktorpotenzen rechnen. Dann musst du eben das Gleichungssystem was dabei rauskommt wieder berechnen."<---was genau meinst du damit?) bei 7^47 kann ich 47 einfach wegkürzen? thx auf jeden fall für deine hilfe |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
