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

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

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

So, $13^{16} \equiv 1 \text{ mod } 17$.

And, $13^{96} = 13^{16 \times 6} \equiv 1 \text{ mod } 17$.

We are left with $13^{99} = 13^{96} \times 13^3 \equiv 13^3 \text{ mod } 17 \equiv 2197 \text{ mod } 17$ which is $4$.

Comments

@PRK

 working link  :)

https://www3.nd.edu/~sevens/13187unit14.pdf

---

Fermat's little theorem is a nice way to tackle $\checkmark$

One more way:

$99: 01100011: 2^6+2^5+2^1+2^0:64+32+2+1$

$(13^{64}\times 13^{32}\times 13^{2}\times 13^{1})mod\ 17$

$13^1mod17=13$

$13^2mod17=16$

Before finding $13^{32}mod17=?$ which is a big number. Try to find something simpler which will be helpful in finding $13^{32}$

So let's take $13^4mod17=1\ (amazing)$

Now it will be very easy:

$13^{32}mod17=(13^4*13^4*13^4*13^4*13^4*13^4*13^4*13^4)mod17=1$

Similarly:

$13^{64}mod17=(13^{32}*13^{32})mod17=1$

---

$(1*1*16*13)mod17=208\ mod17=4$

---

Is this portion present in GATE 2021 syllabus ?

Answer 2

The remainder cycle is $13, 16, 4, 1.$

$13^{99}\text{mod}\;17 = 13^3 \text{mod}\;17 = 4$

Note:

for remainder cycle ,$13\;\text{mod}\;17 = 13,\quad 13^2\;\text{mod}\;17 = 16,\quad 13^3\;\text{mod}\;17 = 4,\quad 13^4\;\text{mod}\;17 = 1$

Comments

@Arjun Sir,  we can use calculator too.. but not directly.
13^99 =  (13 ^11) ^9

So find reminder for    13^11.
(13 ^11) mod 17 =   4   ..     (Using Calculator)
now    reminder for (13 ^99) =   (4^9)  mod 17 =   (4^9) mod 17 = 4

---

He picked 4 not only because cycle repeats after remainders 13,16,4 and 1 but also because every multiple of power of 3 will also give same remainder as power of 3. As 99 is also a multiple of 3, the remainder is same as that of 13^3. It is better to use Fermat's theorem for such questions as computing mod, even on a calculator, is time consuming. But in case if the power is in the multiple of 3 then you can check with this method. 

Reference: https://math.stackexchange.com/questions/735217/what-is-the-remainder-when-4-to-the-power-1000-is-divided-by-7

---

this is given in help section of calculator..

Modulus (mod) operation performed on decimal numbers with 15 digits would not be precise.

Use mod operation only if the number comprises of less than 15 digits i.e. mod operation provides best results for smaller numbers.

Answer 3

There is an easy trick for this using calculator. Yes, Calculator will give wrong answer if you will directly calculate such a huge number.

How to use calculator for this ?
 13^99 =  (13 ^11) ^9 

So find reminder for    13^11.
(13 ^11) mod 17 =   4   ..     (Using Calculator)
now    reminder for (4 ^9) mod 17   = 4  (Using Calculator) (ANS)
You can select any number to spilt it. Just make sure you are not using large numbers.

Comments

@Ahwan

so your answer means

a^n mod p == (a^i mod p)^j mod p

if n==i*j ??????

---

Yes

---

This method will fail if the power is a prime number.

Answer 4

$\textbf{First Method:}$

$13^{99}$ mod $17 = ?$

Find the  Euler's totient function of $17$

If $'n'$ is prime number

$\phi(n)=n\left(1-\frac{1}{n}\right)$

$\phi(17)=17(1-\frac{1}{17})=16$

Find $99$ mod $16\equiv3$

Now find $13^{3}$ mod  $17\equiv2197$ mod $17\equiv4$

__________________________________________________

$\textbf{Second Method:}$

$\dfrac{13^{1}}{17}\implies \text{Remander} = 13$

$\dfrac{13^{2}}{17} \implies \text{Remander} = 16$

$\dfrac{13^{3}}{17}\implies \text{Remander}  = 4$

$\dfrac{13^{4}}{17}  \implies \text{Remander} = 1$

$\implies \dfrac{13^{99}}{17} = \dfrac{(13^{4})^{24}\times 13^{3}}{17} = \dfrac{1\times 13^{13}}{17} = \dfrac{13^{3}}{17}  \implies \text{Remander} = 4$

So, the correct answer is $4.$

Comments

Thanks

---

@Fyse Any restriction or constraint while splitting though i checked for 2-3 combination and getting same result?

@Lakshman Patel RJIT Any limiting case of your mentioned method i did using it and got 22

---

@Abhisek Tiwari 4

You can split in any way. But while splitting, make sure that the number you get after split is not too big such that it gives a wrong result in the calculator (which we may fail to detect) while computing modulus. To be on safer side, take smaller values.