Fundamentals of Arithmetic, Divisibility Theory, and Modular Arithmetic - IIM CAT 2026 Masterclass

Welcome to this comprehensive LibreTexts-style chapter guide tailored specifically for aspirants of IIM CAT 2026. Arithmetic forms the bedrock of the Quantitative Aptitude (QA) section, consistently accounting for 35% to 45% of the total questions in recent CAT exam papers. Mastering number hierarchies, prime factorization, Euclidean algorithms, and modular congruences is essential for achieving a 99+ percentile.

Chapter 1: The Number Hierarchy & Categorization

Before diving into advanced problem-solving, a competitive aspirant must master the axiomatic classification of numbers. Real numbers are divided into nested subsets, each possessing distinct algebraic properties critical for CAT constraints (such as integer constraints in QA questions).

• Natural Numbers (\(\mathbb{N}\)): The counting numbers \(\{1, 2, 3, 4, \dots\}\). In CAT questions, "positive integers" refers precisely to \(\mathbb{N}\).
• Whole Numbers (\(\mathbb{W}\)): Natural numbers augmented with zero: \(\{0, 1, 2, 3, \dots\}\).
• Integers (\(\mathbb{Z}\)): Complete set of positive, negative, and zero whole numbers: \(\{\dots, -2, -1, 0, 1, 2, \dots\}\).
• Rational Numbers (\(\mathbb{Q}\)): Numbers expressed as \(\frac{a}{b}\) where \(a, b \in \mathbb{Z}\) and \(b eq 0\). These exhibit terminating or recurring decimal expansions.
• Real Numbers (\(\mathbb{R}\)): The continuous set comprising all rational and irrational numbers (non-terminating, non-recurring decimals such as \(\sqrt{2}\) or \(\pi\)).

Chapter 2: Fundamental Theorem of Arithmetic & Prime Factorization

The Fundamental Theorem of Arithmetic asserts that every integer strictly greater than 1 is either a prime itself or can be uniquely factored into a product of prime numbers, ignoring order.

Theorem Formulation

For any integer \(n > 1\), there exist distinct prime numbers \(p_1 < p_2 < \dots < p_k\) and positive integer exponents \(a_1, a_2, \dots, a_k\) such that:

\[n = \prod_{i=1}^{k} p_i^{a_i} = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}\]

This canonical prime factorization is the primary tool used in CAT to determine the total number of factors, sum of factors, Euler's totient count, and trailing zeros in factorial expressions.

Chapter 3: Divisibility Rules & The Euclidean Algorithm for GCD

Divisibility forms the cornerstone of quantitative problem solving. An integer \(a\) divides an integer \(b\) (denoted as \(a \mid b\)) if there exists an integer \(c\) such that \(b = ac\).

The Euclidean Algorithm

To find the Greatest Common Divisor (GCD or HCF) of two large integers efficiently without complete factorization, we apply the iterative remainder principle:

\[\gcd(a, b) = \gcd(b, a \pmod b)\]

Worked Example: Computing \(\gcd(252, 105)\)

1. Express 252 in terms of 105: \(252 = 2 \times 105 + 42\)
2. Reduce to remainder: \(\gcd(252, 105) = \gcd(105, 42)\)
3. Express 105 in terms of 42: \(105 = 2 \times 42 + 21\)
4. Reduce to remainder: \(\gcd(105, 42) = \gcd(42, 21)\)
5. Express 42 in terms of 21: \(42 = 2 \times 21 + 0\)

Since the remainder has reached 0, the last non-zero remainder is the answer. Thus, \(\gcd(252, 105) = 21\).

Chapter 4: Modular Arithmetic Essentials & Congruences

Modular arithmetic is an essential technique for solving CAT questions involving remainders of massive exponents, calendar cycles, and unit digits.

Definition of Congruence Modulo \(n\)

Let \(n\) be a positive integer. Two integers \(a\) and \(b\) are congruent modulo \(n\), written as \(a \equiv b \pmod n\), if \(n\) divides their difference \(a - b\):

\[\forall a, b \in \mathbb{Z}, \quad a \equiv b \pmod n \iff n \mid (a - b)\]

Algebraic Properties of Modular Arithmetic

If \(a \equiv c \pmod n\) and \(b \equiv d \pmod n\), then the following fundamental operational properties hold true:

• Modular Addition: \((a + b) \equiv (c + d) \pmod n\)
• Modular Multiplication: \((a \times b) \equiv (c \times d) \pmod n\)

CAT Exam Weightage & PYQ Pattern Analysis

Understanding exam patterns helps structure preparation effectively:

• Chapter Weightage: Arithmetic and Number Systems combined contribute 9 to 12 questions out of 22 in CAT QA. Modular arithmetic and prime factor properties appear directly or indirectly in 2-3 questions per slot.
• NTA / CAT Pattern Trends: Questions have moved away from pure formula memorization towards conceptual application. CAT frequently combines divisibility constraints with algebraic inequalities or function equations.
• PYQ Analysis: Prior year questions regularly test remainder theorems (Fermat's Little Theorem, Euler's Totient Theorem, and Chinese Remainder Theorem) alongside Euclidean GCD applications in real-world scenarios (e.g., tiling, grouping, and cycle synchronization).

People Also Ask (FAQs)

---