how to find out remainder of $3^{256}$ divided by $13$
A comment below the question hints that OP might not be aware of this notation. So, I'll add some information to assist the OP.
Firstly, this is merely a convenient notation. Nothing more nothing less.
We write $a \mid b$ iff $a$ divides $b$. That is, $\exists l \in \Bbb Z$ such that $b=al$. To be more precise, $a$ is a divisor of $b$.
Let $0<k \in \Bbb N$. We say that $a \equiv b \mod k$ if and only if $k \mid a-b$.
I'll leave it to you to argue that, an equivalent version of $(2)$ above is, $a \equiv b \mod k$ if and only if $a$ and $b$ leave the same remainder $\mod k$.
Some properties. (Some benefits you get for using this notation)
Let $a_i,b_i \in \Bbb Z,k \in \Bbb N$. Also, let $a_i \equiv b_i\mod k$. Then,
- $\sum_ia_i\equiv \sum_i b_i \mod k$
- $a_i−a_j≡b_i−b_j\mod k$
- $\prod_i a_i\equiv \prod_i b_i \mod k$
- $a^n_i \equiv b^n_i\mod k$ for $n \in \Bbb N.$
Note that, I have kept quite about division. Something like division makes sense in some cases.
Suggested Reading:
This link looks good to me although I haven't read it myself. If you are still interested in more, ask Prof. Google about the search term "Modular Arithmetic".
The key ingredient in solving the problem is that $3^3=27$ is $1 \mod 13$.
It helps in the following manner:
$$\begin{align}3^3&\equiv1 \mod13\\3^6&\equiv1 \mod13\\&\vdots\\3^{3k}&\equiv 1 \mod13\end{align}$$
So, you now know, $3^{255} \equiv 1 \mod 13$ by plugging in $k=85$ above. This means, $$\boxed{3^{256}\equiv3\mod 13}$$ which is what you wanted!
Hint $\rm\ mod\ 13\!:\ \ 3^{\large \color{#C00}3} \equiv 1\ \Rightarrow \ 3^{\large 1+\color{#C00}3n}\equiv 3 (3^{\large \color{#C00}3})^{\large n}\equiv 3(1)^{\large n}\!\equiv 3,\:$ and $\rm\:mod\ \color{#c00}3\!:\ 256\equiv 2\!+\!5\!+\!6\equiv 1$.
Alternatively, as above $\rm\:c^{\large \color{#C00}3}\! \equiv 1\ \Rightarrow\ c^{\large k}\! \equiv c^{\large k\ mod\ \color{#C00}3},\:$ i.e. for elements of order $\color{#C00}3$ we may reduce their exponents mod $\color{#C00}3.\,$ This makes repeated squaring very easy, which yields another proof:
$$\rm\ c^{\large 3}\! \equiv 1\ \Rightarrow\ c^{\large 2^{\Large N}}\!\! \equiv\ c^{\large \!\:(-1)^{\Large N}}\!\equiv \:\begin{cases} c &\rm if\ \ N\ \ is\ even \\ \rm c^{\large -1}\! \equiv\: c^{\large 2} &\rm if \ \ N\ \ is\ odd\end{cases}$$
Alternatively, if congruence arithmetic is unfamiliar, here is another method.
$\qquad 26 = 27-1$ divides $\rm\:27^{\large n}-1 = 3^{\large 3n}-1,\:$ so $\:26\:$ divides $\:3\:$ times it $\rm\:=\: 3^{\large 3n+1} - 3$
So $\rm\:3^{\large 3n+1}\! - 3\ =\ 26\,k,\:$ i.e. $\rm\:3^{\large 3n+1} = 3 + 13\, (2k),\:$ so $\rm\:3^{\large 3n+1}\div 13\,$ leaves remainder $3$.
Finally, note $\,256\,$ has form $\rm\:3n+1\:$ (for $\rm\rm\:n = 85),\:$ a fact which I verified more quickly above by casting nines, which implies that an integer is congruent to its digit sum (mod $9$), so also (mod $3$), because $\:10\equiv 1\:$ $\Rightarrow$ $\rm\:abc_{\!\ 10} = a\:10^{2} + b\:10 + c\:\equiv\: a\cdot 1^2 + b\cdot 1 + c\:\equiv\: a+b+c$.
Kannappan and Bill have noticed a useful shortcut. Fermat's little theorem can also be used to get a slightly slower shortcut.
But when such clever shortcuts are not available, the usual way to proceed is by exponentiation by squaring. The grand principle of modular arithmetic is that $(a\times b)\bmod 13$ is the same as $((a\bmod 13)\times(b\bmod 13))\bmod 13$.
Apply this to $a=b=3^{128}$ and we get $$3^{256}\bmod 13 = (3^{128} \bmod 13)^2 \bmod 13$$ We can do the same thing again with $a=b=3^{64}$ to get an expression for $3^{128}\bmod 13$, so $$3^{256}\bmod 13 = ((3^{64} \bmod 13)^2 \bmod 13)^2 \bmod 13$$ After a series of such reductions, because $256=2^8$ we arrive at the following procedure:
- Set $a_0=3$.
- Set $a_1 = a_0^2\bmod 13$.
- Set $a_2 = a_1^2\bmod 13$.
and so forth until we reach $a_8$. Each $a_i$ is then $3^{2^i}\bmod 13$. Actually executing this, we quickly notice that the $a_i$s alternate between $3$ and $9$, so $a_8$ must be $3$, which is the answer.