**CAT Number System Mastery: Divisibility, Factors & Remainders**

CAT Number System Mastery: Divisibility, Factors & Remainders

(A Premium Study Guide for 99+ Percentile Aspirants)

What This Is

The Number System (Divisibility, Factors, Remainders) is a high-frequency, high-scoring topic in CAT QA. It appears in ~5-7 questions per paper, often as standalone problems or embedded in larger questions (e.g., Data Interpretation, Algebra). Mastering this topic ensures: ✅ Speed: Solve in <2 minutes with structured techniques.
✅ Accuracy: Avoid traps like negative remainders, incorrect LCM/GCD applications, or misapplied divisibility rules.
✅ Versatility: Apply concepts to remainder theorems, factorials, exponents, and even Geometry.

Real CAT-Style Example: "Find the smallest 3-digit number that leaves a remainder of 2 when divided by 5 and a remainder of 3 when divided by 7." (Answer: 52. This tests simultaneous congruences and LCM-based number construction—core skills in this guide.)

Key Concepts & Techniques

1. Divisibility Rules (When to Use: Quick Elimination in MCQs)

• 2/5/10: Last digit divisible by 2/5/10.
• 3/9: Sum of digits divisible by 3/9.
• 4/8: Last 2/3 digits divisible by 4/8.
• 6: Divisible by both 2 and 3.
• 11: Alternating sum of digits divisible by 11 (e.g., 121 → 1-2+1=0).
• 12: Divisible by both 3 and 4.
• When to use: MCQs with large numbers (e.g., "Which of 123456, 654321, 987654 is divisible by 12?"). Eliminate options without full division.

2. Remainder Theorem (When to Use: "Find remainder of N when divided by D")

• Basic: Remainder = N mod D.
• Negative Remainders: If N < 0, add D until positive (e.g., -17 mod 5 → 3).
• Exponents: Use Euler’s Theorem (if N and D are co-prime) or cyclicity (e.g., powers of 2 mod 5 cycle every 4).
• When to use: Questions like "Find remainder of 7^100 when divided by 13" or "What is the last digit of 3^2023?".

3. LCM & HCF (When to Use: Problems on Common Multiples/Divisors)

• LCM: Smallest number divisible by all given numbers.
• HCF (GCD): Largest number dividing all given numbers.
• Key Formula: LCM(a,b) × HCF(a,b) = a × b (only for two numbers).
• When to use:
• "Find the smallest number divisible by 4, 5, 6 leaving remainder 3" → LCM + 3.
• "Two numbers have HCF 12 and LCM 72. Find the numbers" → Use factor pairs of (LCM × HCF).

4. Chinese Remainder Theorem (CRT) (When to Use: Simultaneous Congruences)

• Problem Type: "Find the smallest number N such that N ≡ 2 mod 5 and N ≡ 3 mod 7."
• Approach:
• Express N as N = 5k + 2.
• Substitute into second congruence: 5k + 2 ≡ 3 mod 7 → 5k ≡ 1 mod 7.
• Find k ≡ 3 mod 7 (since 5 × 3 = 15 ≡ 1 mod 7).
• General solution: N = 5(7m + 3) + 2 = 35m + 17.
• Smallest positive N = 17 (but check options; CAT may ask for 3-digit numbers → 17 + 35 = 52).

5. Factor Counting (When to Use: "How many factors does N have?")

• Prime Factorization: N = p₁^a × p₂^b × p₃^c → Total factors = (a+1)(b+1)(c+1).
• Even/Odd Factors: Subtract 1 from exponents of 2 for odd factors.
• When to use: "How many factors of 360 are divisible by 10?" → Factorize 360 = 2³ × 3² × 5¹ → Factors divisible by 10 = 2 × 2 × 1 = 4 (since 10 = 2 × 5).

6. Remainder Properties (When to Use: "Find remainder of (a + b) or (a × b)")

• (a + b) mod m = (a mod m + b mod m) mod m.
• (a × b) mod m = (a mod m × b mod m) mod m.
• When to use: "Find remainder of (1234 × 5678) when divided by 9" → Use digit sums (1234 mod 9 = 1, 5678 mod 9 = 8 → 1 × 8 = 8).

7. Wilson’s Theorem (When to Use: Factorial Remainders)

• (p-1)! ≡ -1 mod p (for prime p).
• When to use: "Find remainder of 22! when divided by 23" → 22! ≡ -1 ≡ 22 mod 23.

8. Fermat’s Little Theorem (When to Use: Exponents with Prime Moduli)

• If p is prime and a is not divisible by p, a^(p-1) ≡ 1 mod p.
• When to use: "Find remainder of 2^100 when divided by 101" → 2^100 ≡ 1 mod 101.

Step-by-Step Strategy

Step 1: Identify the Problem Type

• Divisibility? → Apply rules (e.g., sum of digits for 3/9).
• Remainder? → Use Remainder Theorem or CRT.
• Factors? → Prime factorize and count.
• LCM/HCF? → Use LCM + remainder or HCF properties.

Step 2: Simplify the Problem

• Break large numbers into smaller congruences (e.g., 1234 mod 5 → 1230 + 4 → 4 mod 5).
• For exponents, reduce the base (e.g., 7^100 mod 13 → (7^12)^8 × 7^4 mod 13 → 1^8 × 7^4 mod 13).

Step 3: Apply the Right Tool

• Single remainder: Direct division or cyclicity.
• Multiple remainders: CRT or LCM-based construction.
• Factor counting: Prime factorization → formula.

Step 4: Verify with Options (MCQs Only)

• Plug in options to check divisibility/remainders (e.g., "Which of these is divisible by 11?").
• For TITA, ensure the answer fits all conditions.

Step 5: Check for Traps

• Negative remainders (e.g., -3 mod 5 = 2).
• Non-coprime moduli (e.g., CRT fails if moduli share a common factor).
• Edge cases (e.g., 0, 1, or the number itself as factors).

Fully Worked CAT-Style Example

Question: "Find the smallest 4-digit number that leaves a remainder of 3 when divided by 7 and a remainder of 5 when divided by 11."

Solution: 1. Identify Type: Simultaneous congruences → CRT.
2. Express N:
- N ≡ 3 mod 7 → N = 7k + 3.
- N ≡ 5 mod 11 → 7k + 3 ≡ 5 mod 11 → 7k ≡ 2 mod 11.
3. Solve for k:
- Find 7⁻¹ mod 11 (multiplicative inverse). Try k = 8 → 7 × 8 = 56 ≡ 1 mod 11.
- Multiply both sides by 8: k ≡ 16 ≡ 5 mod 11 → k = 11m + 5.
4. General Solution:
- N = 7(11m + 5) + 3 = 77m + 38.
5. Find Smallest 4-Digit N:
- 77m + 38 ≥ 1000 → m ≥ (1000 - 38)/77 ≈ 12.5 → m = 13.
- N = 77 × 13 + 38 = 1039.

Answer: 1039.

Common Mistakes

CAT Traps & Time Management

Traps to Avoid

1. "Remainder of 0" Trap:
2. "Find the remainder when 100 is divided by 10" → 0, not 10.

3. Why? Remainder must be < divisor.

4. "Non-Existent Solutions" Trap:

5. "Find N such that N ≡ 2 mod 4 and N ≡ 1 mod 6".
6. No solution (HCF(4,6)=2 does not divide (2-1)=1).

7. How to spot: Check if HCF of moduli divides (remainder1 - remainder2).

8. "Large Exponents" Trap:

9. "Find 7^100 mod 13" → Don’t compute 7^100!
10. Use Fermat’s Little Theorem: 7^12 ≡ 1 mod 13 → 7^100 = (7^12)^8 × 7^4 ≡ 1^8 × 7^4 ≡ 9 mod 13.

Time Management

• Divisibility Rules: <30 sec (use for MCQ elimination).
• Remainder Problems: 1-2 min (use cyclicity/CRT).
• Factor Counting: 1 min (prime factorize + formula).
• LCM/HCF Problems: 1-2 min (apply formulas directly).
• If stuck >3 min: Skip and return later.

Quick Practice

1. Question: "Find the remainder when 2^2023 is divided by 5."
   Answer: 3.
   Explanation: Cyclicity of 2 mod 5: 2, 4, 3, 1 → 2023 mod 4 = 3 → 3rd term = 3.

2. Question: "How many factors of 144 are perfect squares?"
   Answer: 4.
   Explanation: 144 = 2⁴ × 3² → Perfect square factors = (2+1)(1+1) = 6? No! Only exponents even and ≤ original exponents → 2⁰, 2², 2⁴ × 3⁰, 3² → 4 factors.

Last-Minute Cram Sheet

1. Divisibility by 11: Alternating sum of digits divisible by 11.
2. Remainder of (a + b) mod m: (a mod m + b mod m) mod m.
3. LCM(a,b) × HCF(a,b) = a × b (only for two numbers).
4. CRT Steps: Express N = D₁k + R₁ → substitute into D₂ → solve for k.
5. Factors of N = p₁^a × p₂^b: (a+1)(b+1).
6. Negative Remainders: Add divisor until positive (e.g., -3 mod 5 = 2).
7. Fermat’s Little Theorem: a^(p-1) ≡ 1 mod p (p prime, a not divisible by p).
8. Wilson’s Theorem: (p-1)! ≡ -1 mod p (p prime).
9. Cyclicity of 2 mod 5: 2, 4, 3, 1 (cycle length 4).
10. Trap: If N ≡ R mod D, then 0 ≤ R < D (remainder cannot equal divisor).

Final Tip: Practice 10-15 problems daily from past CAT papers (2017-2023). Focus on speed + accuracy—this topic is low-hanging fruit for 99+ percentilers! ?