# 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

-
The answers below, by Bill Dubuque and Kannappan Sampath completely answer the question, if you know how to use them. –  Michael Hardy Mar 3 '12 at 21:17
To help you read the answers below, please note that $27 \equiv 1 \bmod 13$ means that the remainder of $\dfrac{27}{13}$ is $1.$ –  user2468 Mar 3 '12 at 21:25

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.

1. 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$.

2. 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,

1. $\sum_ia_i\equiv \sum_i b_i \mod k$
2. $a_i−a_j≡b_i−b_j\mod k$
3. $\prod_i a_i\equiv \prod_i b_i \mod k$
4. $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.

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^\color{#C00}3 \equiv 1\ \Rightarrow \ 3^{1+\color{#C00}3n}\equiv 3\: (3^\color{#C00}3)^n\equiv 3\cdot 1^n\equiv 3,\:$ and $\rm\:mod\ 3\!:\ 256\equiv 2+5+6\equiv 1$.

Alternatively, as above $\rm\:c^\color{#C00}3 \equiv 1\ \Rightarrow\ c^k \equiv c^{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^3 \equiv 1\ \ \Rightarrow\ \ c^{2^{\!\:N}} \equiv\ c^{\!\:(-1)^N}\equiv \:\begin{cases} c &\rm if\ \ N\ \ is\ even \\ \rm c^{-1}\! \equiv\: c^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^n-1 = 3^{3n}-1,\:$ so $\:26\:$ divides $\:3\:$ times it $\rm\:=\: 3^{3n+1} - 3$

So $\rm\:3^{3n+1} - 3\ =\ 26\:n,\:$ i.e. $\rm\:3^{3n+1} = 3 + 13\: (2n),\:$ so dividing $\rm\:3^{3n+1}$ by $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$.

-
can u explain a bit more... –  Jay Mar 3 '12 at 21:22
@Jay Sure. Which part(s) aren't clear? Do you know modular (congruence) arithmetic? –  Bill Dubuque Mar 3 '12 at 21:35
thnks its now clear after kannappan explained it above –  Jay Mar 3 '12 at 21:40
@Jay I added a simpler method. –  Bill Dubuque Mar 3 '12 at 22:02

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:

1. Set $a_0=3$.
2. Set $a_1 = a_0^2\bmod 13$.
3. 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.

-
+1 Nice Answer! –  user21436 Mar 3 '12 at 21:28

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)$$

-
Looks to me like you're implicitly using modular arithmetic each time you silently drop a $13$ from your expressions. –  Henning Makholm Mar 3 '12 at 22:21
I have upvoted your answer. You may like to declare that the solution uses Binomial Theorem and edit the array of equations into something more fleshy (padding with words here and there[note the plural form]). –  user21436 Mar 3 '12 at 22:24

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}$

-

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.

-