The Gateway to Computer Science Excellence
0 votes
The remainder when 3^37 is divided by 79 is

A. 78

B. 1

C. 2

D. 35
in Numerical Ability by (5 points) | 216 views

2 Answers

+1 vote

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.



by Active (3.6k points)
0 votes

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,

by Active (3.7k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,381 users