heureka

avatar
Benutzernameheureka
Punkte26387
Membership
Stats
Fragen 17
Antworten 5678

 #2
avatar+26387 
+30

I saw in a magazine that there was a contest or something about determining the 3 last digits of 3^123456, is there anyone that could help with this? 

 

\(\small{ \begin{array}{rcll} 3^{123456} \pmod {1000} & \equiv & ? \\ \end{array} }\)

 

\(\boxed{~ \small{ \begin{array}{rcll} a^{\varphi{(m)}} &= 1 \pmod {m}, \qquad \text{ if } gcd(a,m) = 1 \end{array} } ~}\)

 

\(\small{a = 3}\)

\(\small{m = 1000 = 2^3 \cdot 5^3}\)

 

1.)  \(\small{ gcd(3,1000) = 1 }\)

 

2.)

 \(\small{ \begin{array}{rcll} \varphi{(1000)} &=& 1000 \cdot \left( 1-\frac{1}{2} \right)\cdot \left( 1-\frac{1}{5} \right) \\ \varphi{(1000)} &=& 1000 \cdot \left( \frac12 \right)\cdot \left( \frac{4}{5} \right) \\ \varphi{(1000)} &=& 400 \\ \end{array} }\)

 

3.)  \(\small{ \begin{array}{rcll} 3^{400} &= 1 \pmod {1000} \\ \end{array} }\)

 

4. Split 123456 in units of 400

\(\small{ \begin{array}{rcll} 123456 &=& 400 \cdot 308 + 256 \\ 3^{123456} \pmod {1000} &=& 3^{400 \cdot 308 + 256} \pmod {1000} \\ &=& 3^{400 \cdot 308} \cdot 3^{256} \pmod {1000} \\ &=& ( \underbrace{3^{400}}_{=1\pmod {1000} } )^{308} \cdot 3^{256} \pmod {1000} \\ &=& 1^{308} \cdot 3^{256} \pmod {1000} \\ &=& 1 \cdot 3^{256} \pmod {1000} \\ &=& 3^{256} \pmod {1000} \qquad | \qquad 3^{10} = 49 \pmod {1000}\\ &=& 3^{10\cdot 25+6} \pmod {1000}\\ &=& 3^{10\cdot 25} \cdot 3^6 \pmod {1000}\\ &=& (3^{10})^{25} \cdot 3^6 \pmod {1000}\\ &=& (49)^{25} \cdot 3^6 \pmod {1000}\\ \end{array} } \)

 

 

\(\small{ = 1311081016089963454886184368275274375604160521\pmod {1000}\\ = 521 }\)

 

 

laugh

.
15.03.2016