Question

Find the remainder when $3^{247}$ is divided by 17 is:
$\left(1\right)11$
$\left(2\right)8$
$\left(3\right)13$

Answer 1

Hint: We need to find the remainder obtained when we divide the given raised power of 3 by 17. For this, we will not calculate the actual value of $3^{247}$. We would rather see the remainder obtained when we solve the small powers of 3 and see the remainder. And then we will do multiplication in the power to obtain the remainder for the bigger exponent powers of 3. We will also use the concept of “mod”.

Complete step by step answer:
Observe that the following holds true:
$3^6= 17\times 43-2$
Now we dissociate the power of 247 as follows:
$3^{247}=3\times\left(3^6\right)^{41}$
$\implies 3^{247}=3\times\left(17\times43-2\right)^{41}$
Now, see that each of the terms is divisible by 17 except the term $\left(-2\right)^{41}$
So, the ones which are divisible by 17 will get cancelled out and the remainder obtained will be the same as that obtained when $3\times\left(-2\right)^{41}$ is divided by 17. Now, we apply the same trick on this one too. Observe that the following holds true:
$\left(-2\right)^4=16=17-1$
Hence, the following holds true too:
$3\times\left(-2\right)^{41}=3\times -2\times \left(-2\right)^{40}$
$\implies 3\times\left(-2\right)^{41} = 3\times -2\times \left(17-1\right)^{10} $
Now again, the terms are divisible by 17 so they will leave the remainder as 0 except the term $-3\times 2=-6$. Now we just need to know what the remainder will be if we divide –6 by 17. We see that:
$-6=17\times -1+11$
Hence, $-6=11\left(mod17\right)$
Therefore, the remainder obtained will be 11.
So, option $\left(1\right)11$ is correct.

Note: Do not solve the actual value of $3^{247}$ to solve this otherwise you will get stuck. Try to simplify the expression as much as possible. Always make sure that the remainder is not negative because that would be an incorrect answer.