modulo

mod(3^111,13)

$3^{111} \pmod {13} = \ ?$

SATZ von Euler/Fermat (Euler, 1760)

Für $n \in N \text{ und } a \in Z \text{ mit } ggT( a, n ) = 1 \text{ gilt: }\\ a^{\varphi(n)} \equiv 1 \pmod n$

a = 3 und n = 13. ggT(3,13) = 1. Das heißt 3 und 13 sind relativ prim.

Somit können wir berechnen da 13 eine Primzahl ist $\varphi(p) = p-1.\qquad \varphi(13) = 12$

Somit gilt nun auch $3^{\varphi(13)} \equiv 1 \pmod {13}\\ 3^{12} \equiv 1 \pmod {13}$

3 hoch 12 geteilt durch 13 ergibt den Rest 1!

Nun rechnen wir weiter.

Wir zerlegen den Exponenten 111 = 12 * 9 + 3, damit wir die Zahl 12 in den Exponenten bekommen.

$\begin{array}{rcl} 3^{111} \pmod {13} \\ & \equiv & 3^{12\cdot 9 + 3}\pmod {13} \\ & \equiv & 3^{12\cdot 9}\cdot 3^3\pmod {13} \\ & \equiv & (\underbrace{3^{12}}_{=1 \pmod {13}} )^9\cdot 3^3\pmod {13} \\ & \equiv & 1^9 \cdot 3^3\pmod {13} \\ & \equiv & 3^3\pmod {13} \\ & \equiv & 27\pmod {13} \\ & \equiv & 1\pmod {13} \\ \mathbf{3^{111} \pmod {13} }& \mathbf{ \equiv } & \mathbf{1\pmod {13}} \end{array}$

mod(3^111,13) = 1

3^111mod13=1