TheCATExam
Sign in

CAT 2024 Slot 1 — QA Question 10

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

When 10100 is divided by 7, the remainder is

Answer & solution

Correct answer: 4

  • A

    3

  • B

    6

  • C

    1

  • 4

Solution

Easy

Reduce the base mod 77, then exploit the cycle of powers of 33 modulo 77 (it repeats with period 66). Find 100 mod 6100 \bmod 6 to land on the right spot in the cycle.

1

Reduce the base. 10≡3(mod7)10\equiv 3\pmod7, so we need 3100 mod 73^{100}\bmod 7.

10100≡3100(mod7)\begin{aligned} &10^{100}\equiv 3^{100}\pmod 7 \end{aligned}
2

Find the cycle of 3k mod 73^k\bmod7.

31≡3, 32≡2, 33≡6⇒ 34≡4, 35≡5, 36≡1(period 6)\begin{aligned} &3^1\equiv3,\ 3^2\equiv2,\ 3^3\equiv6\\ &\Rightarrow\ 3^4\equiv4,\ 3^5\equiv5,\ 3^6\equiv1 \quad\text{(period 6)} \end{aligned}
3

Locate the exponent. 100=6×16+4100=6\times16+4, so 3100≡343^{100}\equiv3^4.

3100≡34(mod7)(period 6, from step 2)⇒ 3100≡4(mod7)\begin{aligned} &3^{100}\equiv 3^{4}\pmod7 \quad\text{(period 6, from step 2)}\\ &\Rightarrow\ 3^{100}\equiv 4\pmod7 \end{aligned}
Remainder=4\text{Remainder}=4

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

See all Number Theory questions →
CAT 2024 Slot 1 QA Q10 — Remainder of a to the power n, divided by b. solution | TheCATExam