retagged by
17,953 views
19 votes
19 votes
The value of $3^{51} \text{ mod } 5$ is _____
retagged by

18 Answers

8 votes
8 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$
7 votes
7 votes

$\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.$

edited by
2 votes
2 votes

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.

Answer:

Related questions

24 votes
24 votes
8 answers
2
Arjun asked Feb 7, 2019
17,134 views
The following C program is executed on a Unix/Linux system :#include<unistd.h int main() { int i; for(i=0; i<10; i++) if(i%2 == 0) fork(); return 0; }The total number of ...
13 votes
13 votes
4 answers
3
Arjun asked Feb 7, 2019
9,564 views
Consider the following C program :#include<stdio.h int jumble(int x, int y){ x = 2*x+y; return x; } int main(){ int x=2, y=5; y=jumble(y,x); x=jumble(y,x); printf("%d \n"...
17 votes
17 votes
3 answers
4