The Gateway to Computer Science Excellence
+5 votes
3.1k views
The value of $3^{51} \text{ mod } 5$ is _____
in Combinatory by Veteran (422k points)
edited by | 3.1k views

10 Answers

+12 votes
Best answer
$3^{51} \text{ mod } \: 5 = (3^3)^{17} \: \text{ mod } \: 5 = (27)^{17} \: \text{ mod } \: 5 = (27 \text{ mod } 5)^{17} \text{ mod } 5 = 2^{17} \text{ mod } 5 = 131072 \: \text{ mod } 5 = 2$
by Active (2.5k points)
edited by
+7
It might sound Complete NonSense but i calculated this using GATE Calculator.
+2

@SomeEarth

Fortunately, this question gives correct result !

But it always does not give correct results ! WHY ?

if number of digits in scientific calculator are less than our value than it evaluates it as e power something, this lead to loss some precision.

0
same here
+26 votes

By using Fermat's Little Theorem, if $p$ is a prime number, then

$a^{p-1} \equiv 1 \text{ mod } p$.

$a^{p-1} \text {mod}  p=1$

So, $3^{4} \text{ mod } 5 = 1 $.

$3^{48} \text{ mod } 5 = 3^{12 \times 4} \text{ mod } 5 =1 $.

Now $3^{51} \text{ mod } 5 = (3^{48} \text{ mod } 5) \times (3^3 \text{ mod } 5 )= 3^3 \text{ mod } 5 = 27 \text{ mod } 5= 2$

by Boss (23.7k points)
edited by
+5 votes

Using Remainder theorem:

Euler totient number $\phi (5)=4$

Given $\frac{3^{51}}{5}$, now $\frac{3^{51 mod 4}}{5}= \frac{3^{3}}{5}$

Given number is reduced to $\frac{27}{5}=2(rem)$

Hence 2 is correct answer

by Boss (15.5k points)
0
This should be the best answer here.
+4 votes
$3^{51}\ mod\ 5$

= $3^{(4*12)+3}\ mod\ 5$

= $(3^{(4*12)} * 3 ^ 3)\ mod\ 5$

=$(3^{(4*12)}\ mod\ 5 )* (3 ^ 3\ mod\ 5) $

=$(3^{4}\ mod\ 5 )^{12}* (3 ^ 3\ mod\ 5) $

=$(81\ mod\ 5 )^{12}* (27\ mod\ 5) $

=$1^{12}*2$

=$2$
by Boss (20.5k points)
edited by
+3 votes
$3^{51}\; mod\; 5$

$=3\times (3^2)^{25}\;mod\;5$

$=3\times (10-1)^{25}\;mod\;5$

$=3\times (-1)^{25}\; mod\;5$

$=-3\; mod\; 5$

$=2$
by Boss (11k points)
+2 votes

$3^{1}$ mod $5 = 3$

$3^{2}$ mod $5 = 4$

$3^{3}$ mod $5 = 2$

$3^{4}$ mod $5 = 1$

Now, $3^{51}$ mod $5 = \bigg[\big(3^{4}\big)^{12}\times 3^{3}\bigg]$ mod $5$

$\implies \bigg[\big((3^{4})^{12}$ mod $5\big)\times \big(3^{3}$ mod $5\big)\bigg]$ mod $5$

$\implies \bigg[\bigg(\big(3^{4}$ mod $5\big)^{12}$ mod  $ 5\bigg)\times \big(3^{3}$ mod $5\big)\bigg]$ mod $5$

$\implies \bigg[\bigg(\big(1\big)^{12} $ mod $5\bigg)\times \big(2\big)\bigg]$ mod $5$

$\implies \bigg[\bigg(1$  mod $5\bigg) \times 2 \bigg]$ mod $5$

$\implies 2$ mod $5\equiv 2$

So, the correct answer is $2$.

References:

by Veteran (52.9k points)
+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. Although here, $3$ and $5$ are co-prime, I'm going to use repeated squaring method as it's the generalized one. For example, if the question asked $12^{100} \mathrm{~mod~}30$, Fermat's last theorem or Euler's Totient function $\varphi$ would not work. Therefore, Repeated Squaring method is the safest and the faster one in generalized case.

$3^{51} \mathrm{~mod~} 5\equiv 3\left(3^{25}\right)^2\mathrm{~mod~} 5 \tag{1}$

$3^{25} \mathrm{~mod~} 5\equiv 3\left(3^{12}\right)^2\mathrm{~mod~} 5  \tag{2}$

$3^{12} \mathrm{~mod~} 5\equiv \left(3^{6}\right)^2\mathrm{~mod~} 5  \tag{3}$

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

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

$3^{1} \mathrm{~mod~} 5\equiv 3\mathrm{~mod~} 5 \tag{6}$

Now evaluating in a bottom-up fashion,

no$(6)$ $\Rightarrow 3^{1} \equiv 3$

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

no$(4)$ $\Rightarrow 3^{6} \equiv \left(2\right)^2\equiv4$

no$(3)$ $\Rightarrow 3^{12} \equiv \left(4\right)^2\equiv16\equiv1$

no$(2)$ $\Rightarrow 3^{25} \equiv 3\left(1\right)^2\equiv3$

no$(1)$ $\Rightarrow 3^{51} \equiv 3\left(3\right)^2\equiv3\times9\equiv3\times4\equiv12\equiv2$

 

$\therefore 3^{51} \mathrm{~mod~} 5\equiv2$

Note: Here $\equiv$ means modular equivalence.

by Active (2.5k points)
0 votes
Since we get all the numbers which are less than 5 when we perform  --->>>  ( 3^x mod 5 )  when x is any positive integer so it satisfies the property of group which gets repeated after every multiple of 5.

so 3^51 mod 5  ==  (3^ (51 mod 5)) mod 5 ==  (3^1)mod 5 == 3 mod 5 = 2 , So 2 is correct ans , Unfortunately My anxiety eat that mod 5 from 3 mod 5 and I wrote 3 .
by (41 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,666 questions
56,154 answers
193,759 comments
93,729 users