Remainders, Divisibility and Modular Arithmetic Practice Questions for CAT: 87+ Solved Questions with Step-by-Step Solutions

Solve 87+ Remainders, Divisibility and Modular Arithmetic practice 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

How many positive integers less than $2500$ leave remainder $2$ when divided by each of $5$ , $7$ and $8$ , and are also divisible by $3$ ?

Correct Answer:

Step-by-Step Solution

Key idea: this is a same-remainder simultaneous congruence question with an extra divisibility filter. It is recognisable because one remainder repeats across several divisors, and then a separate divisibility condition is added.

Step 1: If $N$ leaves remainder $2$ when divided by $5$ , $7$ and $8$ , then $N - 2$ is divisible by all three divisors. So $N - 2$ is divisible by their LCM.

Since $5$ , $7$ and $8$ are pairwise coprime in the needed way, $LCM (5, 7, 8) = 280$ .

Therefore write

$N = 280 q + 2$

for some integer $q$ .

Step 2: Apply the bound $N < 2500$ .

$280 q + 2 < 2500 ⟹ 280 q < 2498 ⟹ q \leq 8.$

Also $N$ is positive, and $q = 0$ gives $N = 2$ , so $q$ can initially be $0, 1, 2, \dots, 8$ .

Step 3: Apply the extra condition that $N$ is divisible by $3$ .

Modulo $3$ ,

$280 \equiv 1 (mod 3),$

$N = 280 q + 2 \equiv q + 2 (mod 3) .$

For divisibility by $3$ ,

$q + 2 \equiv 0 (mod 3) ⟹ q \equiv 1 (mod 3) .$

Step 4: Count valid $q$ values among $0, 1, \dots, 8$ .

The values congruent to $1$ modulo $3$ are

$q = 1, 4, 7.$

So there are $3$ valid integers.

Answer: $3$ .

Question 2 · Quantitative Ability NAT

Let $B$ be the largest positive integer that divides every number of the form

$3^{k + 1} + 4 (3^{k}) + 3^{k},$

where $k$ is any positive integer. Find $B$ .

Correct Answer:

Step-by-Step Solution

Key idea: this is a whole-family divisor question where the expression should be simplified first. The terms all contain a common power of $3$ .

Step 1: Rewrite every term as a multiple of $3^{k}$ .

$3^{k + 1} = 3 \cdot 3^{k} .$

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

Step 2: Use the condition that $k$ is a positive integer.

Since $k \geq 1$ , the smallest power of $3$ that appears is $3^{1} = 3$ .

Therefore

$8 \cdot 3^{k} = 24 \cdot 3^{k - 1},$

and $3^{k - 1}$ is an integer for every positive $k$ .

Hence $24$ divides every member of the family.

Step 3: Check that no larger universal divisor is possible.

At $k = 1$ ,

$3^{2} + 4 (3^{1}) + 3^{1} = 9 + 12 + 3 = 24.$

Any integer dividing every member must divide this first value, so it cannot exceed $24$ .

Answer: $24$ .

Question 3 · Quantitative Ability NAT

Find the largest positive integer less than $500$ that leaves remainder $7$ when divided by $18$ and is divisible by $11$ .

Correct Answer:

385

Step-by-Step Solution

Key idea: this is a “do not take the largest $q$ immediately” question. The largest value in the arithmetic progression may fail the extra divisibility condition.

Step 1: Translate the remainder condition.

If the number $N$ leaves remainder $7$ when divided by $18$ , then

$N = 18 q + 7$

for some integer $q \geq 0$ .

Step 2: Use the bound $N < 500$ to find the largest possible $q$ before checking divisibility.

$18 q + 7 < 500 ⟹ 18 q < 493 ⟹ q \leq 27.$

So the largest possible progression term before the extra check is $18 (27) + 7 = 493$ .

Step 3: Impose divisibility by $11$ .

Work modulo $11$ :

$18 \equiv 7 (mod 11),$

$N = 18 q + 7 \equiv 7 q + 7 = 7 (q + 1) (mod 11) .$

For $N$ to be divisible by $11$ ,

$7 (q + 1) \equiv 0 (mod 11) .$

Since $g cd (7, 11) = 1$ , this means

$q + 1 \equiv 0 (mod 11) ⟹ q \equiv 10 (mod 11) .$

Step 4: Choose the largest $q \leq 27$ satisfying this.

The possible values are $q = 10$ and $q = 21$ . The largest is $q = 21$ .

Step 5: Compute $N$ .

$N = 18 (21) + 7 = 378 + 7 = 385.$

Answer: $385$ .

Question 4 · Quantitative Ability MCQ

Let $N$ be the number of integers that can be written as $4^{r}$ for a positive integer $r$ and lie strictly between $8^{6}$ and $8^{24}$ .

A function $f$ maps positive integers to whole numbers such that

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

for all positive integers $x, y$ , and $f (p) = 1$ for every prime $p$ . Find $f (N)$ .

A.
7
B.
3
C.
1
D.
15

Correct Answer:

Step-by-Step Solution

Key idea: this is a two-stage power-form + function-transform question. The first stage asks for a count of powers between two powers; the second stage evaluates the standard add-one transformed function at that count.

Step 1: Rewrite the boundaries in base 2.

$8^{6} = (2^{3})^{6} = 2^{18}, 8^{24} = (2^{3})^{24} = 2^{72} .$

A number of the form $4^{r}$ is $2^{2 r}$ .

Step 2: Count strictly between the boundaries.

We need

$2^{18} < 2^{2 r} < 2^{72} ⟺ 18 < 2 r < 72.$

Dividing by 2 gives

$9 < r < 36.$

Thus $r = 10, 11, \dots, 35$ , so

$N = 35 - 10 + 1 = 26.$

Step 3: Transform the function.

Define $g (n) = f (n) + 1$ . Then

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

For every prime $p$ , $g (p) = f (p) + 1 = 2$ .

Therefore, if $n$ has total prime-factor count $Ω (n)$ , then

$g (n) = 2^{Ω (n)} and f (n) = 2^{Ω (n)} - 1.$

Step 4: Evaluate at $N = 26$ .

Since $26 = 2 \cdot 13$ , $Ω (26) = 2$ . Hence

$f (26) = 2^{2} - 1 = 3.$

Answer: 3

Common trap: including the endpoints gives $r = 9, \dots, 36$ , so $N = 28$ , leading to $f (28) = 7$ . The word strictly excludes both endpoints.

Question 5 · Quantitative Ability NAT

Find the smallest positive integer $n$ such that

$3^{n} \equiv 1 (mod 17)$

and $n$ has exactly $18$ positive divisors.

Correct Answer:

288

Step-by-Step Solution

Key idea: this question combines multiplicative order with divisor-count structure. First find the exact order of $3$ modulo $17$ . Then find the smallest multiple of that order having exactly $18$ divisors.

Step 1: Find the order of $3$ modulo $17$ .

Compute powers of $3$ :

$3^{2} = 9,$

$3^{4} = 81 \equiv 13 (mod 17),$

$3^{8} \equiv 1 3^{2} = 169 \equiv 16 \equiv - 1 (mod 17) .$

Therefore

$3^{16} \equiv 1 (mod 17) .$

We must check that no smaller divisor of $16$ works. The divisors of $16$ are $1, 2, 4, 8$ .

$3^{1} \neq \equiv 1, 3^{2} = 9 \neq \equiv 1, 3^{4} \equiv 13 \neq \equiv 1, 3^{8} \equiv - 1 \neq \equiv 1.$

Hence the order is $16$ .

Step 2: Translate the congruence condition.

Since the order is $16$ ,

$3^{n} \equiv 1 (mod 17) ⟺ 16 ∣ n .$

So $n$ must be a multiple of $16$ .

Step 3: Use the divisor-count condition.

We need $d (n) = 18$ . Since

$18 = 18 = 9 \cdot 2 = 6 \cdot 3 = 3 \cdot 3 \cdot 2,$

the possible exponent patterns in the prime factorisation of $n$ are:

$p^{17}, p^{8} q, p^{5} q^{2}, p^{2} q^{2} r .$

Also, $n$ must be divisible by $16 = 2^{4}$ , so the exponent of $2$ in $n$ must be at least $4$ .

Step 4: Minimise $n$ under these patterns.

Pattern $p^{17}$ : the smallest multiple of $16$ is $2^{17}$ , which is very large.

Pattern $p^{8} q$ : to have $2^{4} ∣ n$ , the exponent of $2$ must be $8$ , so the smallest number is

$2^{8} \cdot 3 = 768.$

Pattern $p^{5} q^{2}$ : to have $2^{4} ∣ n$ , the exponent of $2$ can be $5$ , and the smallest square is $3^{2}$ . This gives

$2^{5} \cdot 3^{2} = 32 \cdot 9 = 288.$

Pattern $p^{2} q^{2} r$ : no prime exponent exceeds $2$ , so $2^{4}$ cannot divide $n$ . This pattern is impossible.

Step 5: Compare the viable candidates.

The smallest viable candidate is $288$ .

Check:

$288 = 2^{5} \cdot 3^{2},$

$d (288) = (5 + 1) (2 + 1) = 6 \cdot 3 = 18.$

Also $16 ∣ 288$ , so $3^{288} \equiv 1 (mod 17)$ .

Answer: $288$ .

Common trap: using Fermat’s theorem loosely and assuming $n$ only has to be a multiple of $8$ or $4$ . The exact order is needed. Another trap is choosing a number with $18$ divisors, such as $180$ , without checking the order condition; $180$ is not divisible by $16$ .

Remainders, Divisibility and Modular Arithmetic Practice Questions for CAT: 87+ 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 practice questions in this unit

A question from this chapter

Login to view the complete practice 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