Rechen mod n?

Hallo Leute,

Ich habe gerade eine Aufgabe erhalten, für die ich überhaupt keine Idee habe, wie ich vorgehen muss. Ich freue mich auf jede Hilfe.

Aufgabe:

2^41(mod43)

Danke

Answer 1

[FataMorgana2010]

Du kannst das aufspalten.

Du kennst ja sicher ein paar Zweierpotenzen. Da suchst du dir was Passendes heraus, hier bietet sich z. B.

$2^7 = 128$ an, denn 3*43 ist 129. Also ist 128 mod 43 = -1.

Damit kannst du dann schon mal rechnen (immer modulo 43):

$2^{41} = (2^7)^5 * 2^6 = (-1)^5 * 64 = -64 = -21 = 22$

Der Trick ist immer, einen Faktor zu finden, der es ermöglicht mit möglichst kleinen Zahlen weiterzurechnen.

Answer 2

[tomaushamburg]

Nach den Rechenregeln geht Potenz vor Multiplikation vor Addition, also hier zuerst 2^41, und das Ergebnis dann mod 43...

Comments

[FataMorgana2010]

Zum Glück gelten auch für die Modulorechnung mod 43 die Distributivgesetze, man kann das also vereinfachen.