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

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

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.

The 4-Step Exam Method

Power remainder algorithm

Reduce the base: replace

a

by its remainder modulo

m

Build the cycle: calculate

r^{1}, r^{2}, r^{3}, \dots

remainders until the pattern repeats.

Reduce the exponent: divide

n

by the cycle length.

Pick the position: exponent remainder

1

means first cycle term,

2

means second cycle term, and so on.

Important: If

n

is exactly divisible by the cycle length, pick the last term of the cycle, not the first.

Pattern 1: Base Is a Multiple of the Divisor

When the base already gives remainder $0$

a \equiv 0 (mod m)

, then

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

for every positive integer

n

Example:

Since

33

is divisible by

11

, we have

33 \equiv 0 (mod 11)

. Hence,

3 3^{33} \equiv 0 (mod 11)

Exam reflex: Before building a cycle, check whether the base is already divisible by the divisor.

CAT PYQ: $10^{100}$ Divided by $7$

CAT PYQ • cycle method

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

First reduce the base:

10 \equiv 3 (mod 7)

Power	$3^{1}$	$3^{2}$	$3^{3}$	$3^{4}$	$3^{5}$	$3^{6}$
Remainder mod $7$	$3$	$2$	$6$	$4$	$5$	$1$

Cycle length

= 6

100 \div 6

leaves remainder

4

So the answer is the 4th cycle term: remainder

4

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 short notes in this unit

chapter

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

Remainders, Divisibility and Modular Arithmetic short notes for CAT: 34 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practic

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 short 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

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

The Core Trick: Replace the Base by Its Remainder

Reduce the base first

The 4-Step Exam Method

Power remainder algorithm

Pattern 1: Base Is a Multiple of the Divisor

When the base already gives remainder 0

CAT PYQ: $10^{100}$ Divided by $7$

When 10100 is divided by 7, find the remainder

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

Step-by-Step Solution

Step-by-Step Solution

More short notes in this unit

A question from this chapter

Login to view the complete short notes

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

When the base already gives remainder $0$

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