Remainders, Divisibility and Modular Arithmetic Notes for CAT: Concepts, Formulas, Worked Examples & Practice

Remainders, Divisibility and Modular Arithmetic notes for CAT: 50 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

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.

What Does Remainder of a Power Mean?

A huge power, a small answer

A question like:

“Find the remainder when

1 0^{100}

is divided by

7

.”

does not ask you to expand $1 0^{100}$ . It asks:

What number from

0

6

is left after dividing

1 0^{100}

7

Since possible remainders on division by $7$ are only $0, 1, 2, 3, 4, 5, 6$ , the answer must be small.

The Core Trick: Replace the Base by Its Remainder

Core move

Reduce the base first

If $a$ leaves remainder $r$ when divided by $m$ , then powers of $a$ and powers of $r$ leave the same remainders when divided by $m$ :

a \equiv r (mod m)

, then

a^{n} \equiv r^{n} (mod m)

10 \div 7

leaves remainder

3

, so

10 \equiv 3 (mod 7)

Therefore,

1 0^{100}

has the same remainder as

3^{100}

when divided by

7

This does not solve the whole question, but it makes the base smaller.

Remainders, Divisibility and Modular Arithmetic: Solved Questions with Step-by-Step Explanations (2 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$ .

More notes in this unit

chapter

Remainders, Divisibility and Modular Arithmetic Notes for CAT: Concepts, Formulas, Worked Examples & Practice

Remainders, Divisibility and Modular Arithmetic notes for CAT: 50 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice ques

A question from this chapter

Question 1

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 ?

Question 2

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 .

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free