Remainder of exponential expression divided by 13

CAT 2024 Slot 3 · QA · 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, 10121(mod13)10^{12} \equiv 1 \pmod{13}.

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

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

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

So the remainder is 9.

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