TheCATExam
Sign in

CAT 2024 Slot 3 — QA Question 5

Remainder of a to the power n, divided by b.Easy

If 1068 is divided by 13, the remainder is

Answer & solution

  • 9

  • B

    8

  • C

    4

  • D

    5

Solution

Easy

Find the remainder of 106810^{68} on division by 1313 using modular arithmetic. Look for a small power of 1010 that is congruent to ±1(mod13)\pm 1 \pmod{13} to create a cycle.

1

Find a short cycle. Compute powers of 1010 modulo 1313.

101≡10⇒ 102≡100≡9(mod13)(100−91)⇒ 103≡9⋅10≡90≡−1(mod13)(90−91)\begin{aligned} &10^1\equiv 10\\ &\Rightarrow\ 10^2\equiv 100\equiv 9\pmod{13}\quad\text{(}100-91\text{)}\\ &\Rightarrow\ 10^3\equiv 9\cdot 10\equiv 90\equiv -1\pmod{13}\quad\text{(}90-91\text{)} \end{aligned}
2

Use the cycle. Since 103≡−110^3\equiv -1, we get 106≡110^6\equiv 1. Write 68=6⋅11+268=6\cdot 11+2.

1068=(106)11⋅102⇒ 1068≡111⋅102(mod13)(106≡1)⇒ 1068≡9(mod13)(from step 1)\begin{aligned} &10^{68}=\left(10^{6}\right)^{11}\cdot 10^{2}\\ &\Rightarrow\ 10^{68}\equiv 1^{11}\cdot 10^{2}\pmod{13}\quad\text{(}10^6\equiv1\text{)}\\ &\Rightarrow\ 10^{68}\equiv 9\pmod{13}\quad\text{(from step 1)} \end{aligned}
remainder=9\text{remainder}=9
CAT 2024 Slot 3 QA Q5: If 10 68 is divided by 13, the remainder is — Solution | TheCATExam