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

I have received a downvote. Please let me know the reason so that I can improve/correct the answer.

---

it think as 99 is not the prime number

---

p refers to 17, and not 99.

---

Best link to solve any such problems

http://www3.nd.edu/~sevens/13150unit14.pdf

---

@rajesh Pradhan the link u provided isn't showing anything ... pls provide link again

---

and if the number is not prime then what we will do ???

---

• For  $a^x  (mod\, c)$ if c is not prime(i.e. composite)

then you can use Euler's Totient Function, if $gcd(c,a) = 1$ i.e c and a are co-prime numbers.

as it satisfies the relation $a^{\phi(c)} \equiv 1 (mod \, c)$ where $\phi(c)$ is the totient function value of $c$.Further here the multiplicative inverse of $a$ will be $a^{\phi(p)-1}$.

• The Euler's Totient function also has another application in calculating the number of co-prime numbers below a given n.
• Check Here : Wikipedia (Euler's Theorem)
• How to calculate Euler's Totient Function

For large power modulo calculation result checking you can use this site : https://www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html

---

thanks bro ..@sourajit

---

one more extra thing that before apply fermat little theorem

1.  p should be prime

2   and p does not divide a

then apply the fermat little theorem

in the above explanation both condition is satisfied so we can apply

---

Link is not working

---

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