# What will be the remainder?

I'm stuck with this problem I'm trying to solve from about an hour. Here's the question.

What is the remainder when (3^202)+137 is divided by 101?

There are 4 options -> 36, 45, 56, 11

I want to know the answer of the question with proper and possibly easiest method to solve the problem.

-

I think Chandru1 is correct. The answer is 45.

How did I get it?

1) The remainder of 3^30 / 101 = 6
2) 6^6 = 46656.
3) 46656 * (The remainder of 3^22 / 101) = 2286144.
4) 2286144 + 137 = 2286281
5) The remainder of 2286281 / 101 = 45


Note in step 2 and 3 that 30 * 6 = 180. And 180 + 22 = 202

A simpler example: The reaminder when (2^10)+7 is divided by 6 (the answer is 5).

1) The reaminder of 2^4 / 6 = 4
2) 4^2 = 16
3) 16 * (The remainder of 2^2 / 6) = 64
4) 64 + 7 = 71
5) The remainder of 71 / 6 = 5

-
Thanks a lot mate. :) – Electrifyings Nov 17 '10 at 14:59

HINT $\ 101\$ is prime so a little Fermat $\rm\ \Rightarrow\ \ 3^{101}\ \equiv\ 3\ \ \Rightarrow\ \ 3^{202}\ \equiv\ \ldots\ (mod\ 101)$

Since your comment reveals you are not familiar with modular arithmetic, here is an alternative.

By Fermat's little theorem $101$ divides $\: 3^{101}-3\:$ so it also divides $\rm\ (3^{101}-3)\ (3^{101}+3)\ =\ 3^{202}-9$

-
Thanks for answering, but my little brain can't handle mod thingy. LOL xD – Electrifyings Nov 17 '10 at 15:00
@chiaotzu: I edited my answer to give a non-mod approach. – Bill Dubuque Nov 17 '10 at 17:01

HINT: Fermat's Little Theorem, which says that $a^{p-1} \equiv 1 \ (\text{mod} \ p)$ , where $p$ is a prime and $101$ is a prime. Remainder should be $45$

-
Thank you mate. :D – Electrifyings Nov 17 '10 at 15:00