Remainder of exponential expression divided by 13

CAT 2024 Slot 3 · Quantitative Ability · Easy · Number Systems

If 106810^{68} is divided by 13, the remainder is

  1. A.

    8

  2. B.

    9

  3. C.

    4

  4. D.

    5

Answer

B

Explanation

By Fermat's Little Theorem, 1012≡1(mod13)10^{12} \equiv 1 \pmod{13}.

68=12×5+868 = 12 \times 5 + 8, so: 1068=(1012)5⋅108≡15⋅108≡108(mod13)10^{68} = (10^{12})^5 \cdot 10^8 \equiv 1^5 \cdot 10^8 \equiv 10^8 \pmod{13}

Since 10≡−3(mod13)10 \equiv -3 \pmod{13}: 108≡(−3)8=38(mod13)10^8 \equiv (-3)^8 = 3^8 \pmod{13}

Notice 33=27≡1(mod13)3^3 = 27 \equiv 1 \pmod{13}. Thus, 38=(33)2⋅32≡(1)2⋅9=9(mod13)3^8 = (3^3)^2 \cdot 3^2 \equiv (1)^2 \cdot 9 = 9 \pmod{13}.

So the remainder is 9.

Related Number Systems questions

Practise this under exam conditions

Sign in to solve it with a live timer, the on-screen CAT calculator, and streak and accuracy tracking across every question you attempt.

Solve in the workspace