+0  
 
0
1038
2
avatar

mod(3^111,13)

 06.10.2015

Beste Antwort 

 #2
avatar+26364 
+35

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

laugh

 07.10.2015
 #1
avatar
0

3^111mod13=1

 06.10.2015
 #2
avatar+26364 
+35
Beste Antwort

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

laugh

heureka 07.10.2015

1 Benutzer online