+26319 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
+26319 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
