Define the sequence of positive integers a_n recursively by a_1=3 and a_n=3(a_n- 1) for all n> =2. Determine the last two digits of a_{2007}.
+26367 Define the sequence of positive integers \(a_n\) recursively by
\(a_1=3\) and \(a_n=3a_{n- 1}\) for all \(n\ge2\).
Determine the last two digits of \(a_{2007}\).
\(\begin{array}{|rcll|} \hline a_1 &=& 3 \\ a_2 &=& 3*a_1 \\ &=& 3*3 \\ &=& 3^2 \\ a_3 &=& 3 * a_2 \\ &=& 3*3^2 \\ &=& 3^3 \\ \dots \\ \mathbf{ a_{2007} } &=& \mathbf{ 3^{2007} } \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline && 3^{2007} \pmod{100} \\ && \boxed { \text{Euler:}\\ 3^{\phi(100)} \equiv 1 \pmod{100} \quad \phi{100}=100*\left(1-\dfrac12 \right)*\left(1-\dfrac15 \right)\\ \phi{100}=40\\ 3^{40} \equiv 1 \pmod{100} }\\ &\equiv& \left(3^{40}\right)^{50}*3^7 \pmod{100} \\ &\equiv& 1^{50}*3^7 \pmod{100} \\ &\equiv& 3^7 \pmod{100} \\ &\equiv& 2187 \pmod{100} \\ \mathbf{ 3^{2007} \pmod{100} } &\equiv& \mathbf{ 87 \pmod{100} } \\ \hline \end{array}\)
