Test of Mathematics at 10+2 Level

Question

The remainder when 3^37 is divided by 79 is

A. 78

B. 1

C. 2

D. 35

Answer 1

Evaluating $a^n \mathrm{~mod~}m$ is easy when $m$ is prime or $a, m$ are co-prime meaning $\gcd(a,m)=1$. But when $a, m$ are not co-prime, it's not easy to solve it. In this case, Repeated Squaring method can resolve it which needs just about $\lceil\log_2{n}\rceil$ steps at most. Although here, $3$ and $79$ are co-prime, we're going to use repeated squaring method as it's the generalized one.

$3^{37} \mathrm{~mod~} 79\equiv 3\left(3^{18}\right)^2\mathrm{~mod~} 79 \tag{1}$

$3^{18} \mathrm{~mod~} 79\equiv \left(3^{9}\right)^2\mathrm{~mod~} 79  \tag{2}$

$3^{9} \mathrm{~mod~} 79\equiv 3\left(3^{4}\right)^2\mathrm{~mod~} 79  \tag{3}$

$3^{4} \mathrm{~mod~} 79\equiv 81\mathrm{~mod~} 79  \tag{4}$

 

Now evaluating in a bottom-up fashion,

no$(4)$ $\Rightarrow 3^{4} \equiv 2$

no$(3)$ $\Rightarrow 3^{9} \equiv 3\left(2\right)^2\equiv3\times4\equiv12$

no$(2)$ $\Rightarrow 3^{18} \equiv \left(12\right)^2\equiv144\equiv 65\equiv-14$

no$(1)$ $\Rightarrow 3^{37} \equiv 3\left(-14\right)^2\equiv3\times196\equiv3\times38\equiv114\equiv35$

 

$\therefore 3^{37} \mathrm{~mod~} 79\equiv35$

 

So the correct answer is D.

Note: Here $\equiv$ means modular equivalence.

 

 

Answer 2

3^37 = (3^4)^9 * 3 = (81)^9 * 3

This above divided by 79 will give 2^9 for the first one.2^9 *3= 512*3 .This one again divided by 79

will give 38*3 divided by 79 = 114 by 79 will give remainder 35.Answer is D. This is remainder theorem very famous in cat and mba exams questions.See the link below,

http://byjus.com/free-cat-prep/concept-of-remainder