Aptitude Discussion

Q. |
Find the remainder when $3^{164}$ is divided by $162$? |

✖ A. |
0 |

✖ B. |
9 |

✖ C. |
11 |

✔ D. |
81 |

**Solution:**

Option(**D**) is correct

For $x ≥ 4$, Remainder $\dfrac{3^x}{81} =0$

And, Remainder $\dfrac{3^x}{162} = 81$

**Edit:** For an alternative solution, check comment by **Ankit Agrawal.**

**Edit 2:** For yet another alternative solution, check comment by **Sravan Reddy.**

**Rajesh**

*()
*

**Sravan Reddy**

*()
*

$3^4 = 81\text{mod}162$

Multiplying by 9 on both sides,

$3^6 = 729\text{mod}162 = 81\text{mod}162$

Multiplying by 9 on both sides,

$3^8 = 729\text{mod}162 = 81\text{mod}162$

So, doing it many times,

$3^{164} = 81\text{mod}162$

So, answer is 81.

**Avijit**

*()
*

1 will be the ans

**Ankit Agrawal**

*()
*

if you cancel out something from numerator and denominator then you have to multiple by same amount in your answer.

Here we are canceling $3^4$ and getting remainder as 1 so now by multipling $3^4$ you will get the correct answer. :)

**Shrenik**

*()
*

$\dfrac{3^{164}{2*3^4}=\dfac{3^{160}}{2}$

so, the remainder will be 1

Shrenik,

It does not work like that.

Let's say I find remainder for $\dfrac{27}{18}$ which I know is **9**.

But applying your method it would become:

$\dfrac{3^3}{2*3^2}=\dfrac{3}{2}$

So remainder will come out to be **1**, which is incorrect.

The approach, shown in the question is right and the **answer should be 81. **

By Euler's Totient function.:

Let's see a similar question. 11^24 mod 45.

Step 1: 45 = 3^a * 5^b.

Step 2: S(x) = 45 * (1-1/3) * (1-1/5) = 24. ( factors are required not their powers).

S(x) is Euler's function with value 24. So, any prime number less than 45 power S(x) mod 45, the remainder will be 1.

So, 11^24 mod 45 = 1.

Similarly, 3^164 mod 162. S(x) will be 54.

3^54 mod 162 = 1. 54*3 = 162. That leaves 3^2 mod 162. = 9.