0

What is the reminder when $3^{2015}+11^{2014}$ is divided by $61$?

All I can observe in this question is that $3^5=(61*4)-1$ and $11^2=(61*2)-1$. Unable to proceed hereafter. Is there a general method to solve such types of modulus operations?

Tejas
  • 2,082
  • 1
    This observation is good enough, what can you say if you write $2015=5k_1 +u_1$ and $2014= 2 k_2 +u_2$ and substitute to $3^{2015} + 11^{2014}$?. – clark Dec 01 '13 at 02:38
  • Hint: $a \equiv b {\pmod m} \implies a^n \equiv b^n {\pmod m}$ – Macavity Dec 01 '13 at 02:39

2 Answers2

2

Don't think about division: think about modular arithmetic!

The facts you state mean that

$$ 3^5 \equiv -1 \pmod{61} $$ $$ 11^2 \equiv -1 \pmod{61} $$

Also usefully,

$$ 3^{10} \equiv 1 \pmod{61}$$ $$ 11^4 \equiv 1 \pmod{61}$$

Since $3^{10} \equiv 1$, you can pull a lot of factors of $3^{10}$ out of $3^{2015}$ and substitute in $1$. What's left? Similarly for the power of $11$.

Even if you hadn't had your good observation, you can still do arithmetic. Look up either "square-and-multiply" algorithm for computing exponents: you could compute $3^{2015}$ by direct computation using only about 20 multiplications.

Or, it might be fun to work it out yourself: a hint for one version is

$$3^{2015} = \left( 3^{1007} \right)^2 \cdot 3 $$

and for the other version is

$$3^{2015} = 3^{1024} \cdot 3^{991} = 3^{2^{10}} \cdot 3^{991}$$

1

Since $3^5 \equiv -1 \pmod{61}$ from your computation, it follows that

$$3^{2015} = \left(3^5\right)^{403} \equiv (-1)^{403} = -1 \pmod{61}$$

(Alternatively, expand $(61 \cdot 4 - 1)^{403}$ using the binomial theorem, and note that every term except the very last one has a factor of $61$.)

An identical computation works for the power of $11$.