GATE CSE 2016 Set 2 | Question: 29

Question

The value of the expression $13^{99}\pmod{17}$ in the range $0$ to $16$, is ________.

Comments

$13^{99}\ mod\ 17\ =\  \frac{13^{96}*13^3}{17}$

$13^4\ mod\ 17\ =\ 1$

$So, 13^{96}\ mod\ 17\ =\ {(13^{4}})^{24}\ mod\ 17\ =\ 1$

$It\ boils\ down\ to\ \frac{1*13^3}{17}\ =\ 4$

I have taken the fraction representation for ease of understanding. It actually denotes MOD.

---

$(13)^{99}mod 17$

= $(-4)^{99}mod 17$  ( NOTE : $-4 \equiv (13)mod 17 $)

= $-(4)(4^2)^{49}mod 17$

= $-(4)(-1)^{49}mod 17$ = 4 ( NOTE : $-1 \equiv (16)mod 17 $)

---

Thanks for taking care of people's mistakes.

You really deserve love.

Answer 1

Alternatively,

$13*(13^{2})^{49}(mod \space 17) = 13*169^{49} (mod \space 16) = 13 * (-1)^{49} (mod\space 17) = -13 (mod\space 17) = 4$

Comments

best answer.

Answer 2

I'm using Extended euclidean algorithm , Ans => 4

Algorithm =>

Computing answer =>

Comments

Mod gives remainder right ? Please explain what is the difference between mod and % ?

---

Hey buddy seems you wrote different and feels amazing . Can you explain in detail I'll appreciate you forever for this.

Answer 3

Modular Arithmetic:

$a \equiv b(mod n)$ (i.e,. a and b leaves same remainder when divided by n), then

$a^k \equiv b^k(mod n)$, where k be any non-negative integer

Division Algorithm: 

$dividend = divisor * quotient + remainder$

---

Let's find out the number which is modulo congruent to 13

$13 = 17 * 1 + (-4)$ 

Therefore, $13 \equiv (-4)  mod 17$ 

which implies $13^{99} \equiv (-4)^{99} mod 17$ 

$13^{99} \equiv (-4)*((-4)^2)^{49} mod 17$

Value of $16 mod 17 = -1$ which means $16 \equiv -1(modn)$ so that we can replace 16 with -1 in the above which makes our calculation easy

$13^{99} \equiv (-4)*(-1)^{49} mod 17$

$13^{99} \equiv (-4)*(-1)mod 17$ 

$13^{99} \equiv 4 mod 17$

Therefore, the value of $13^{99} mod 17$ is 4

---

References:

Modular Arithmetic Wikipedia

Answer 4

13^99 mod 17= (13^2^49) .13=((170-1)^49).13 mod 17=( -1.13) mod 17=4