$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.
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$.
@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$
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$
@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
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.
@Ahwan
so your answer means a^n mod p == (a^i mod p)^j mod p if n==i*j ??????
$\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.$
@Fyse
Sorry for that i did mistake
Now i correct it
please see my above comment.
Using this calculator :
https://www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html
or
by directly googling the equation I get the answer to be 88.
Do you have a method to solve these type of question?
@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.
64.3k questions
77.9k answers
244k comments
80.0k users