Remainders, Divisibility and Modular Arithmetic Previous Year Questions (PYQs) for CAT: 5+ Solved Questions with Step-by-Step Solutions

Solve 5+ Remainders, Divisibility and Modular Arithmetic previous year questions for CAT with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Remainders, Divisibility and Modular Arithmetic

CAT QA • Number System

Remainders, Divisibility and Modular Arithmetic

A compact chapter: only 8 own-course PYQs, but the ideas are high-speed scoring tools when recognized.

⚡ t1 — Remainders of Powers

Find remainders of huge powers by spotting cycles. 3 PYQs • importance hint: 0.46.

You master: reducing the base, finding a cycle, reducing the exponent, and handling zero-remainder cases.

🧩 t2 — Divisibility, GCD and Congruence Conditions

Use divisibility conditions and common-divisor logic. 3 PYQs • importance hint: 0.46.

🔁 t3 — Power Forms and Multiplicative Functions

Decode expressions involving powers and special multiplicative-style functions. 2 PYQs • importance hint: 0.37.

Starting point: This card is saved with t1: Remainders of Powers, because power remainders are the fastest entry into modular arithmetic.

Remainders of Powers: The Big Idea

⚡

Topic Hero

Remainders of Powers

CAT loves expressions like $1 0^{100}$ , $3 3^{33}$ , or $1 0^{68}$ because they look impossible, but their remainders are usually tiny patterns.

Scary form

a^{n} \div m

→

Smart form

cycle of remainders

Hook: Do not calculate the power. Calculate the remainder pattern.

Remainders, Divisibility and Modular Arithmetic: Solved Questions with Step-by-Step Explanations (5 Problems)

Question 1 · Quantitative Ability NAT

Let A be the largest positive integer that divides all the numbers of the form $3^{k} + 4^{k} + 5^{k}$ , and B be the largest positive integer that divides all the numbers of the form $4^{k} + 3 (4^{k}) + 4^{k + 2}$ , where k is any positive integer. Then (A + B) equals

Correct Answer:

Step-by-Step Solution

Key idea: This is a "largest divisor of a whole family" question — we must find the largest positive integer that divides every number generated by a formula as $k$ ranges over positive integers. The method is: test small values of $k$ to squeeze down the possible GCD, then confirm it always works.

Why this applies: The expression involves a variable exponent $k$ , and we want one fixed number that divides all outputs — this is exactly the "test small $k$ , then generalise" pattern.

Part A: $A$ = largest divisor of $3^{k} + 4^{k} + 5^{k}$

Step 1 — Test small $k$ :

$k = 1 : 3 + 4 + 5 = 12$

$k = 2 : 9 + 16 + 25 = 50$

Step 2 — Any divisor of the whole family must divide $g cd (12, 50) = 2$ . So $A \leq 2$ .

Step 3 — Check $2$ always works: $3^{k}$ and $5^{k}$ are always odd (odd base), and $4^{k}$ is always even, so $odd + odd + even = even$ . So $2$ divides every term.

Hence $A = 2$ .

Part B: $B$ = largest divisor of $4^{k} + 3 (4^{k}) + 4^{k + 2}$

Step 1 — Simplify algebraically first (don't jump to testing numbers blindly):

$4^{k} + 3 (4^{k}) = 4^{k} (1 + 3) = 4 \cdot 4^{k} = 4^{k + 1}$

$4^{k + 1} + 4^{k + 2} = 4^{k + 1} (1 + 4) = 5 \cdot 4^{k + 1}$

So the expression always equals $5 \cdot 4^{k + 1}$ .

Step 2 — Since $k$ is any positive integer, $k \geq 1$ , so $4^{k + 1}$ takes values $4^{2}, 4^{3}, 4^{4}, \dots$ The smallest of these is $4^{2} = 16$ (at $k = 1$ ).

Step 3 — The largest number dividing every term of $5 \cdot 4^{k + 1}$ for $k \geq 1$ is $5 \cdot 4^{2} = 80$ , because $16 ∣ 4^{k + 1}$ for every $k \geq 1$ , and $16$ is the largest such common power (since $k = 1$ actually achieves it).

Hence $B = 80$ .

Final step:

$A + B = 2 + 80 = 82$

Common trap: Testing only one value of $k$ for Part A (e.g. only $k = 1$ , giving $12$ ) and stopping there — without testing a second value to shrink the GCD down to the true answer of $2$ .

Answer: 82

Question 2 · Quantitative Ability MCQ

When $3 3^{33}$ is divided by 11, the remainder is

A.
5
B.
10
C.
1
D.
6

Correct Answer:

Step-by-Step Solution

Pattern: this is a "remainder of a large power" question — recognizable from the phrase "when [big power] is divided by [a prime], the remainder is". The huge exponent is the giveaway that a direct calculation is impossible and a cycle/Fermat approach is needed.

Step 1 — Check for a shortcut first.

Always check whether the divisor shares a common factor with the base before doing any heavy work — that can make the remainder trivially 0. Here, work with the base modulo 11 first: reduce the base to its remainder form modulo 11 so the exponentiation stays small.

Step 2 — Use Fermat's Little Theorem.

Since 11 is prime and the (reduced) base is not divisible by 11, Fermat's Little Theorem tells us: (base) $^{10} \equiv 1 (mod 11)$ , because the theorem states $x^{p - 1} \equiv 1 (mod p)$ for any prime $p$ and any $x$ not divisible by $p$ .

Step 3 — Reduce the exponent using the cycle length 10.

Write the exponent $33 = 10 \times 3 + 3$ . So (base) $^{33} = ((base)^{10})^{3} \times (base)^{3} \equiv 1^{3} \times (base)^{3} (mod 11)$ .

Step 4 — Compute the small remaining power.

$(base)^{3} = 27$ . And $27 = 2 \times 11 + 5$ , so $27 \equiv 5 (mod 11)$ .

Step 5 — State the remainder.

The remainder is $5$ .

Answer: option A, 5.

Question 3 · Quantitative Ability MCQ

A function $f$ maps the set of natural numbers to whole numbers, such that $f (x y) = f (x) f (y) + f (x) + f (y)$ for all $x, y$ and $f (p) = 1$ for every prime number $p$ . Then, the value of $f (160000)$ is

A.
4095
B.
8191
C.
2047
D.
1023

Correct Answer:

Step-by-Step Solution

Key idea: The function $f$ is not directly multiplicative — it satisfies $f (x y) = f (x) f (y) + f (x) + f (y)$ , which has extra " $+ f (x) + f (y)$ " terms. This is the classic add-1 transformation trick: define a new function that absorbs those extra terms and becomes cleanly multiplicative.

Why this applies: Whenever a functional equation looks like $f (x y) = f (x) f (y) + f (x) + f (y)$ (or similar with extra additive terms), adding $1$ to both sides usually factors nicely.

Step 1 — Transform the equation:

Add $1$ to both sides:

$f (x y) + 1 = f (x) f (y) + f (x) + f (y) + 1 = (f (x) + 1) (f (y) + 1)$

Define $g (x) = f (x) + 1$ . Then:

$g (x y) = g (x) g (y)$

This means $g$ is a completely multiplicative function.

Step 2 — Find $g$ on primes:

Given $f (p) = 1$ for every prime $p$ :

$g (p) = f (p) + 1 = 2$

Step 3 — Extend $g$ to any number using prime factorisation:

If $N = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ , then by complete multiplicativity:

$g (N) = g (p_{1})^{a_{1}} g (p_{2})^{a_{2}} \dots g (p_{k})^{a_{k}} = 2^{a_{1} + a_{2} + \dots + a_{k}} = 2^{Ω (N)}$

where $Ω (N)$ is the total number of prime factors of $N$ , counted with multiplicity.

Step 4 — Factorise $160000$ :

$160000 = 16 \times 10000 = 2^{4} \times 1 0^{4} = 2^{4} \times (2 \times 5)^{4} = 2^{4} \times 2^{4} \times 5^{4} = 2^{8} \times 5^{4}$

So $Ω (160000) = 8 + 4 = 12$ .

Step 5 — Compute $g (160000)$ and then $f (160000)$ :

$g (160000) = 2^{12} = 4096$

$f (160000) = g (160000) - 1 = 4096 - 1 = 4095$

Common trap: Treating $f (x y) = f (x) f (y)$ directly (ignoring the extra additive terms) leads to an incorrect, much smaller value.

Answer: 4095

Question 4 · Quantitative Ability MCQ

When $1 0^{100}$ is divided by 7, the remainder is

A.
3
B.
4
C.
1
D.
6

Correct Answer:

Step-by-Step Solution

We need the remainder when $1 0^{100}$ is divided by $7$ .

Instead of calculating the huge number, find the repeating remainder pattern.

First reduce the base modulo $7$ :

$10 \equiv 3 (mod 7)$

Therefore,

$1 0^{100} \equiv 3^{100} (mod 7)$

Now find the cycle of powers of $3$ modulo $7$ :

$3^{1} \equiv 3 (mod 7)$

$3^{2} = 9 \equiv 2 (mod 7)$

$3^{3} = 27 \equiv 6 (mod 7)$

Since

$6 \equiv - 1 (mod 7)$

we get

$3^{3} \equiv - 1 (mod 7)$

Squaring both sides:

$3^{6} \equiv 1 (mod 7)$

So powers of $3$ repeat every $6$ powers modulo $7$ .

Now reduce the exponent $100$ modulo $6$ :

$100 = 6 \times 16 + 4$

Hence,

$100 \equiv 4 (mod 6)$

Therefore,

$3^{100} \equiv 3^{4} (mod 7)$

Now,

$3^{4} = 81$

and

$81 = 7 \times 11 + 4$

So,

$81 \equiv 4 (mod 7)$

Hence,

$1 0^{100} \equiv 4 (mod 7)$

Therefore, the remainder is

$4$

Correct option: B.

Question 5 · Quantitative Ability MCQ

If $1 0^{68}$ is divided by 13, the remainder is

A.
5
B.
8
C.
9
D.
4

Correct Answer:

Step-by-Step Solution

We need the remainder when $1 0^{68}$ is divided by $13$ .

Instead of calculating the huge number, we find the repeating remainder pattern of powers of $10$ modulo $13$ .

First few powers:

$1 0^{1} \equiv 10 (mod 13)$

$1 0^{2} = 100 \equiv 9 (mod 13)$

Now,

$1 0^{3} = 10 \cdot 1 0^{2}$

$1 0^{3} \equiv 10 \cdot 9 = 90 (mod 13)$

Since

$90 = 13 \times 6 + 12$

we get

$90 \equiv 12 (mod 13)$

Also,

$12 \equiv - 1 (mod 13)$

Therefore,

$1 0^{3} \equiv - 1 (mod 13)$

Squaring both sides:

$1 0^{6} \equiv 1 (mod 13)$

So the powers of $10$ repeat every $6$ powers modulo $13$ .

Now reduce the exponent $68$ modulo $6$ :

$68 = 6 \times 11 + 2$

Hence,

$68 \equiv 2 (mod 6)$

Therefore,

$1 0^{68} \equiv 1 0^{2} (mod 13)$

Now,

$1 0^{2} = 100$

and

$100 = 13 \times 7 + 9$

So,

$100 \equiv 9 (mod 13)$

Hence,

$1 0^{68} \equiv 9 (mod 13)$

Therefore, the remainder is

$9$

Correct option: C.

Remainders, Divisibility and Modular Arithmetic Previous Year Questions (PYQs) for CAT: 5+ Solved Questions with Step-by-Step Solutions

Chapter Roadmap: Remainders, Divisibility and Modular Arithmetic

Remainders, Divisibility and Modular Arithmetic

⚡ t1 — Remainders of Powers

🧩 t2 — Divisibility, GCD and Congruence Conditions

🔁 t3 — Power Forms and Multiplicative Functions

Remainders of Powers: The Big Idea

Remainders of Powers

Remainders, Divisibility and Modular Arithmetic: Solved Questions with Step-by-Step Explanations (5 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit

A question from this chapter

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course