GATE CSE 2019 | Question: 21

Question

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

Comments

@KUSHAGRA गुप्ता How did you took 51’s binary form and took it to 3’s power? can you explain why that works?

---

This is the same calculator btw. For this specific question we can get the answer. 

---

Perfect use of brain 🧠

Answer 1

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

Comments

can we use cyclicity concept here? cz m getting same ans from there too

---

@MANSI_SOMANI Anything that works for you given that it is correct

---

@Aditya_Ok ,thanks for confirmation 

Answer 2

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$

Answer 3

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)}$

Hence 2 is correct answer

Comments

This should be the best answer here.

Answer 4

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