7
$\begingroup$

here is a question that about finding the remainder when dividing $3^{256}$ divided by $13$. Can anyone suggest how to find the solution

  • 1
    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.$2012-03-03

8 Answers 8

14

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

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!

8

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

  • 0
    @Jay I added a simpler method.2012-03-03
5

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.

3

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

  • 1
    I have upvoted your answer. You may li$k$e to $d$eclare that the solution uses Binomial Theorem an$d$ edit the array of equations into something more fleshy (padding with _words_ here and there[note the plural form]).2012-03-03
1

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

0

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.