mod effizient per Hand berechnen - Euler’schem Theorem

Question

Aufgabe:

Hallo Leute, könnt ihr mir sagen wie man am besten folgende Aufgaben mit dem

Euler’schem Theorem lösen könnte?

a) Berechnen Sie per Hand möglichst effizient 10^146 mod 21.
b) Berechnen Sie per Hand die beiden letzten Dezimalstellen von 3^854

danke für eure Hilfe

Comments

Satz von Euler sagt \( 10^{12} \equiv 1\mod(21)\), also ist

$$10^{146} \equiv (10^{12})^{12}\cdot 10^2 \equiv 1^{12} \cdot 10^2  \equiv 10^2 \mod(21)$$

Außerdem \( 3^{40} \equiv 1 \mod(100) \) deshalb

$$ 3^{857} \equiv (3^{40})^{21} \cdot 3^{14}\equiv1^{21} \cdot3^{14} \equiv 3^{14}\mod (100) $$

Answer 1

Hallo

 100=-5mod21

100^2=25mod21=4

10^6=100^3=-5*4=-20mod 21=1 mod 21 10^146=10^144*10^2

also 1*-5 also 10^146=-5mod 21

die letzen 2 Stellen sind 3^854 mod 100, oder 9^427 mod 100

das mach jetzt ähnlich

Gruß lul