6.5k views
The value of $3^{51} \text{ mod } 5$ is _____

edited | 6.5k views
0

$51: 00110011=2^5+2^4+2^1+2^0$

$(3^{32}\times 3^{16}\times 3^2\times 3^1)mod 5$

$3mod5=3$

$3^2mod5=4$

For finding $3^{16}mod5$ let's find $3^4mod5$

$3^4mod5=(3^2\times 3^2)mod5=(4\times 4)mod5=16mod5=1$

$3^{16}mod5=(3^4\times 3^4)mod5=(1\times 1)mod5=1mod5=1$

$3^{32}mod5=(3^{16}\times 3^{16})mod5=(1\times 1)mod5=1mod5=1$

$(1\times 1\times 4\times 3)mod 5=12mod5=2$

$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
edited by
+10
It might sound Complete NonSense but i calculated this using GATE Calculator.
+5

@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
0

@SomeEarth

That was really a good click of mind. :D

0
For Calculator in the exam, Number.MAX_SAFE_INTEGER  is $2^{53}-1$.

For numbers above that, floating point arithmetic is used, which will not always guarantee precision in arithmetic operations.

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
edited

Using Remainder theorem:

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

Given $\dfrac{3^{51}}{5}$, now $\dfrac{3^{51\:\text{mod}\: 4}}{5}= \dfrac{3^{3}}{5}$

Given number is reduced to $\dfrac{27}{5}=2\:\text{(remainder)}$

by Boss
edited
0
This should be the best answer here.
$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
edited
$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$

$\textbf{First Method:}$

$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:

_________________________________________________________

$\textbf{Second Method:}$

$\dfrac{3^{1}}{5} \implies \text{Remainder} = 3$

$\dfrac{3^{2}}{5} \implies \text{Remainder} = 4$

$\dfrac{3^{3}}{5} \implies \text{Remainder} = 2$

$\dfrac{3^{4}}{5} \implies \text{Remainder} = 1$

$\implies \dfrac{3^{51}}{5} = \dfrac{(3^{4})^{12}\times 3^{3}}{5} = \dfrac{1\times 2}{5}\implies \text{Remainder} = 2$

So, the correct answer is $2.$

by Veteran
edited

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