1
$\begingroup$

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.

Thanks in advance, waiting for reply. :)

$\endgroup$
1
$\begingroup$

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
$\endgroup$
9
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.