remainder of 2^2011/13
\(\begin{array}{rcll} 2^{2011} \pmod {13} &=& \ ? \end{array}\)
\(\small{ \begin{array}{lrcll} 1. & gcd(13,2) &=& 1 \qquad | \qquad 13 \text{ and } 2 \text{ are relatively prim } \\ 2. & 13 \text{ is a prim number } \\ 3. & \phi() \text{ is Euler's totient function, Euler's phi function }\\ & \phi(p) &=& p-1 \qquad p \text{ is a prim number} \\ & \phi(13) &=& {\color{red}12} \\ 4. & 2^{\phi(13)} &\equiv& 1 \pmod{13} \\ & 2^{{\color{red}12}} &\equiv& 1 \pmod{13} \\ \hline &\text{ Let } \phi(n) \text{ denote the totient function. } \\ &\text{Then } a^{\phi(n)} \equiv 1 \pmod {n} \text{ for all } a \text{ relatively prime to } n. \\ \end{array} }\)
\(\begin{array}{rcll} 5. & 2011 &=& {\color{red}12}\cdot 167 + 7 \\ & 2^{2011 } \pmod{13} &=& 2^{ {\color{red}12}\cdot 167 + 7 } \pmod{13} \\ & &=& ( 2^{ {\color{red}12} } )^{167}\cdot 2^{7} \pmod{13} \\ & &\equiv& ( 1 )^{167}\cdot 2^{7} \pmod{13} \\ & &\equiv& 1\cdot 2^{7} \pmod{13} \\ & &\equiv& 2^{7} \pmod{13} \\ & &\equiv& 128 \pmod{13} \\ & &\equiv& 11 \pmod{13} \end{array} \)
The remainder of \(\frac{2^{2011}} {13}\) is \(\mathbf{11}\)