how to find out remainder of $3^{256}$ divided by $13$ here is a question that about finding the remainder when dividing $3^{256}$ divided by $13$.  Can anyone suggest how to find the solution
 A: 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$.
A: 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.
A: Some hints...(without usage modular arithmetic) 
$$3^{256}=9^{128}=(13-4)^{128}$$
so...
$$4^{128}=(16)^{64}=(13+3)^{64}$$
and we left with:
$$3^{64}=9^{32}=(13-4)^{32}$$
again:
$$4^{32}=16^{16}=(13+3)^{16}$$
and again:
$$3^{16}=9^8=(13-4)^8$$
and...
$$4^8=16^4=(13+3)^4$$
and we left with:
$$3^4=81$$
$$81:3=6(3)$$
A: 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!
A: As $\phi(13)=12,$  by Fermat's little theorem, $3^{12}≡1\pmod{13}$
and as  $256≡4\pmod{12},3^{256}\equiv3^4\pmod{13}$

Alternatively, $3^3=27\equiv1\pmod{13}\implies 3^{256}=(3^3)^{85}\cdot3\equiv1^{85}\cdot3\pmod{13}$
A: By Euler's Totient, we have $\phi(13)=12$, so $$3^{12}\equiv 1\pmod{13},$$ so $$3^{256}\equiv 3^4\equiv \boxed{3}\pmod{13}.$$ Fermat's Theorem is a specialized version of Euler's Totient: $$a^{p-1}\equiv 1\pmod{p}.$$
A: We can go by binomial expansion. 3^256= 3*3^255. I need to divide this number by 13. First, let us divide 3^255. 3^255 is nothing but (3^3)^85, which will give me remainder 1 if divided by 13. This will give us 27^85 = (26+1)^85. The result when divided by 13 will be 1 remainder. Now multiply this remainder by 3 which we left out from the calculations earlier. Please let me know if any confusion.
A: In general when the modulus $m$ is small, you can check the successive powers $x^r$ modulo $m$, the remainders will cycle quickly.
For instance let's examine $4^r\pmod 7$
$\begin{cases}
4^0\equiv 1\pmod 7\\
4^1\equiv 4\pmod 7\\
4^2\equiv 16\equiv 2\pmod 7\\
4^3\equiv 4^2\times 4\equiv 2\times 4\equiv 8\equiv 1\pmod 7\\
4^4\equiv 4^3\times 4\equiv 1\times 4\equiv 4\pmod 7\\
\cdots
\end{cases}$
You can see the remainders will always be $1,2,4,1,2,4,1,\cdots$
Thus the result depends of the divisibility of $r$ by $3$. 


*

*If $r=3k$ then $4^r$ will be the same as $4^0\equiv 1\pmod 7$

*If $r=3k+1$ then $4^r$ will be the same as $4^1\equiv 4\pmod 7$

*If $r=3k+2$ then $4^r$ will be the same as $4^2\equiv 2\pmod 7$
For instance $4^{857}\equiv 4^{(857\bmod 3)}\equiv 4^2\equiv 2\pmod 7$

Of course with another base, the cycle may be shorter or longer (e.g. $3^r\pmod 7$ leads to remainders $1,3,2,6,5,4,1,\cdots$
And this time $3^r\equiv 3^{(r\bmod 6)}\pmod 7$
This technique works very well for small modulus, however when $m$ becomes larger the cycle length may grow as well. In some cases, depending on the base, the cycle can still be short, but in general the method become less applicable.
So for bigger modulus, you need to uses more advanced stuff, like little Fermat theorem or Euler's totient function, both allow to reduce the exponent $r$ when $m$ is a prime number (or a power of a prime).
When $m$ is a composed number (of $n$ primes), Chinese remainder theorem, allows to transform the problem into $n$ smaller problems where only primes modulus are involved.

Applying to your problem $3^r\equiv 1,3,9,1,\cdots \pmod{13}$ the cycle is only $3$ steps short.
Thus $3^{256}\equiv 3^{(256\bmod 3)}\equiv 3^1\equiv 3\pmod{13}$
