Prime and Special Number Categories for UPSC CSAT

1. Theoretical Foundation & Mathematical Underpinnings

1.1 Formal Definition & Scope

• Prime Number (p): An integer p > 1 that has exactly two distinct positive divisors: {1, p}.
  • Set Notation: P = { p ∈ ℤ⁺ | d(p) = 2 }, where d(p) denotes the number of positive divisors.
  • Boundary Condition: 1 is neither prime nor composite because d(1) = 1. Negative integers and 0 are excluded from primality definitions in standard arithmetic.
  • Fundamental Theorem of Arithmetic: Every integer N > 1 can be uniquely factored into a product of prime powers:

    N = p₁^a₁ · p₂^a₂ … p_k^a_k

    where each p_i is a distinct prime and each a_i ≥ 1. Primes serve as the foundational building blocks of the integers.

• Perfect Number (N): An integer equal to the sum of its proper positive divisors:

  N = ∑ d_proper(N) = σ(N) – N

  where σ(N) is the sum of all positive divisors.

  • Examples: 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, followed by 496 and 8128.
  • Euclid-Euler Theorem: Every even perfect number takes the form:

    N = 2^p-1(2^p – 1)

    where both p and (2^p – 1) are prime numbers (the term 2^p – 1 being a Mersenne prime).

• Co-Prime / Relatively Prime Pair (a, b): Two integers a and b satisfying gcd(a, b) = 1 or HCF(a, b) = 1. Their prime factorizations share no common prime bases.
  • Scope: Co-primality is a relational property between numbers, not an intrinsic property of an individual number.
• Twin Primes: A pair of primes of the form (p, p + 2).
  • Examples: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43).

1.2 The “Why” Behind the Math — Short Proofs

Why is 2 the only even prime?
If an integer p > 2 is even, it can be written as p = 2k where k > 1. The divisor set of p must include at least {1, 2, 2k}, which means d(p) ≥ 3. Thus, p is composite. Consequently, every prime p > 2 must be odd.

Why does every prime p > 3 satisfy p = 6k ± 1?
By the Division Algorithm, any integer N can be expressed in one of six forms modulo 6:

N ∈ {6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5}

Evaluating each residue class for primality:

• 6k, 6k + 2 = 2(3k + 1), 6k + 4 = 2(3k + 2) are all divisible by 2 and thus composite for k ≥ 1.
• 6k + 3 = 3(2k + 1) is divisible by 3 and thus composite for k ≥ 1.
• The only remaining candidates are 6k + 1 and 6k + 5 ≡ 6k – 1.

Critical Distinction (Necessary vs. Sufficient): The condition p = 6k ± 1 is necessary for primes > 3, but not sufficient. It acts as an elimination filter. For instance, 25 = 6(4) + 1 = 5² and 35 = 6(6) – 1 = 5 × 7 satisfy the form, yet both are composite.

Why do we test divisors only up to √N for primality?
Let N = a × b with 1 < a ≤ b < N. If a > √N, then:

a × b > √N × √N = N

This creates a contradiction. Therefore, in any non-trivial factor pair (a, b), the smaller factor must satisfy a ≤ √N.

• Contrapositive: If an integer N has no prime factor p ≤ √N, it cannot have any factor q > √N. Hence, checking prime divisors up to ⌊√N⌋ is mathematically sufficient to prove primality.

Why is the integer between twin primes (p > 3) always divisible by 6?
Let the twin prime pair be (p, p + 2) with p > 3. The intermediate integer is m = p + 1.

1. Divisibility by 3: Among any three consecutive integers {p, p + 1, p + 2}, exactly one is divisible by 3. Since p and p + 2 are primes strictly greater than 3, neither is divisible by 3. Therefore, m = p + 1 must be divisible by 3.
2. Divisibility by 2: Since p is an odd prime, m = p + 1 is an even integer and divisible by 2.

Because gcd(2, 3) = 1, it follows that m is divisible by 2 × 3 = 6.

Why are consecutive integers always co-prime?
Let d = gcd(n, n + 1). By the properties of divisibility:

d | (n + 1) and d | n ⇒ d | ((n + 1) – n) ⇒ d | 1

Since d is a positive integer, d = 1. Thus, gcd(n, n + 1) = 1 for all n ∈ ℤ⁺.

1.3 Key Theorems & Invariant Properties

• Parity Theorem for Primes:
  • Prime + Prime = Odd ⇒ One of the primes must be 2.
  • If the sum of an odd number of primes is even, then at least one prime in the set must be 2.
  • Example: If p + q + r = 50 (sum of 3 primes is even), the sum Odd + Odd + Odd = Odd fails; hence, one prime must be even (⇒ p = 2).
• Prime Square Invariant:
  For any prime p > 3:

  p² ≡ 1 (mod 24) ⇔ 24 | (p² – 1)

  Proof Outline: Factor p² – 1 = (p – 1)(p + 1). Since p is an odd prime, (p – 1) and (p + 1) are consecutive even integers, making one a multiple of 4 and the other a multiple of 2 (⇒ 8 | (p² – 1)). Additionally, one of the three consecutive integers {p – 1, p, p + 1} is divisible by 3; since p > 3 is prime, 3 | (p – 1)(p + 1). Since gcd(8, 3) = 1, 24 | (p² – 1).

• Co-prime Divisibility Theorem:
  If a | N, b | N, and gcd(a, b) = 1, then:

  (a × b) | N

  Caution: If gcd(a, b) ≠ 1, the conclusion does not hold.

  • Valid: 8 | N and 9 | N ⇒ 72 | N (since gcd(8, 9) = 1).
  • Invalid: 4 | 36 and 6 | 36, but 24 ∤ 36 (because gcd(4, 6) = 2 ≠ 1).

2. Comparative Matrix & Conceptual Distinctions

3. High-Yield Data Anchors & Benchmarks

A. Prime Frequency Distribution

Key Benchmark: When counting primes in the range 1 ≤ N ≤ 100, the total is strictly 25. Avoid the common error of counting 1.

B. High-Frequency Deceptive Composites (Prime Look-Alikes)

These numbers satisfy 6k ± 1 and have no obvious divisibility by 2, 3, or 5, making them standard trap options.

C. Core Invariants & Algebraic Benchmarks

• For any prime p > 3: p ≡ ±1 (mod 6) and p² ≡ 1 (mod 24).
• Consecutive Integer Product: n(n + 1) is always even, and gcd(n, n + 1) = 1.
• Three Consecutive Integers: n³ – n = (n – 1)n(n + 1) is always divisible by 6.
• Essential Benchmark Squares (⌊√N⌋ references):
  11² = 121, 13² = 169, 15² = 225, 17² = 289, 19² = 361, 23² = 529

4. Standard Algorithmic Protocols

PROTOCOL 1: Systematic Primality Testing for an Integer N

1. Boundary & Base Cases:
   • If N ≤ 1 ⇒ Neither prime nor composite.
   • If N ∈ {2, 3} ⇒ Prime.
2. Filter Multiples of 2 and 3:
   • If N > 3 and N mod 2 = 0 or N mod 3 = 0 ⇒ Composite.
   • Otherwise, N must satisfy N = 6k ± 1. Proceed to Step 3.
3. Establish the Square-Root Upper Bound:
   • Determine k = ⌊√N⌋.
   • Compile the list of all prime numbers p ≤ k.
4. Trial Division by Primes Only:
   • Test divisibility of N sequentially by each prime p ≤ k.
   • If N mod p = 0 for any p ⇒ Composite (terminate).
   • If no prime p ≤ k divides N ⇒ Certified Prime.

Working Example: Primality Test of N = 257

1. 257 > 3, not divisible by 2 (odd) or 3 (digit sum = 14).
2. Form check: 257 = 6(43) – 1 (passes filter).
3. Upper bound: √257 ≈ 16.03 ⇒ k = 16.
4. Primes to test: {5, 7, 11, 13}.
   • 257 mod 5 = 2 ≠ 0
   • 257 = 7 × 36 + 5 ⇒ Remainder 5 ≠ 0
   • 257 = 11 × 23 + 4 ⇒ Remainder 4 ≠ 0
   • 257 = 13 × 19 + 10 ⇒ Remainder 10 ≠ 0
5. Conclusion: 257 is prime.

PROTOCOL 2: Divisibility by a Composite Modulus C

To establish whether C | N for a composite divisor C:

1. Decompose C into Pairwise Co-prime Factors:
   Find integers a, b > 1 such that:

   C = a × b with gcd(a, b) = 1

   (Correct: 72 = 8 × 9 where gcd(8, 9) = 1. Incorrect: 72 = 6 × 12 where gcd(6, 12) = 6 ≠ 1.)

2. Verify Sub-Divisibility:
   • Evaluate if a | N. If false ⇒ C ∤ N.
   • Evaluate if b | N. If false ⇒ C ∤ N.
3. Synthesize Result:
   If both conditions hold, then C | N.

Working Example: Check if N = 43,200 is divisible by C = 72.

1. Factorize 72 = 8 × 9 with gcd(8, 9) = 1.
2. Check 8 | 43,200: Last three digits are 200; 200 / 8 = 25 (✓).
3. Check 9 | 43,200: Digit sum is 4 + 3 + 2 + 0 + 0 = 9, which is divisible by 9 (✓).
4. Conclusion: Since both conditions are satisfied, 72 | 43,200.

5. Standard Question Typologies & Analytical Solutions

TYPE A: Parity & Multi-Variable Constraints

Problem Statement:
Let x, y, z be prime numbers such that x < y < z and x + y + z = 100. What is the maximum possible value of z?

(a) 79
(b) 83
(c) 89
(d) 97

Detailed Analytical Solution:

Step 1: Parity Analysis
The target sum 100 is even. For three positive integers:

Odd + Odd + Odd = Odd
Even + Odd + Odd = Even

Since the sum of three primes is even, at least one prime must be even. The only even prime is 2. Given the strict ordering x < y < z, we must set:

x = 2

Step 2: Algebraic Reduction & Optimization
Substitute x = 2 into the equation:

2 + y + z = 100 ⇒ y + z = 98 ⇒ z = 98 – y

To maximize z, we must minimize the odd prime y such that y > 2 and z is prime:

• Try y = 3 ⇒ z = 98 – 3 = 95 = 5 × 19 (Composite ×)
• Try y = 5 ⇒ z = 98 – 5 = 93 = 3 × 31 (Composite ×)
• Try y = 7 ⇒ z = 98 – 7 = 91 = 7 × 13 (Composite × — classic trap)
• Try y = 11 ⇒ z = 98 – 11 = 87 = 3 × 29 (Composite ×)
• Try y = 13 ⇒ z = 98 – 13 = 85 = 5 × 17 (Composite ×)
• Try y = 17 ⇒ z = 98 – 17 = 81 = 3⁴ (Composite ×)
• Try y = 19 ⇒ z = 98 – 19 = 79 (Prime ✓)

Step 3: Verification
For x = 2, y = 19, and z = 79:

• 2 < 19 < 79 (Ordering satisfied)
• 2 + 19 + 79 = 100
• 79 is prime (divisors tested up to √79 < 9 ⇒ {2, 3, 5, 7}; none divide 79).

Correct Option: (a) 79

TYPE B: Statement-Based / Analytical Evaluation

Problem Statement:
Consider the following statements:

1. Every prime number greater than 3 can be written in the form 6k ± 1 for some integer k.
2. Every integer of the form 6k ± 1, where k is a positive integer, is a prime number.
3. If p is a prime number greater than 3, then p² – 1 is always divisible by 24.

Which of the statements given above is/are correct?

(a) 1 and 3 only
(b) 2 and 3 only
(c) 1 only
(d) 1, 2 and 3

Detailed Analytical Solution:

Step 1: Evaluate Statement 1
By the Division Algorithm modulo 6, all integers take one of the forms 6k, 6k ± 1, 6k ± 2, 6k + 3. Multiples of 2 and 3 cannot be prime for p > 3. Thus, every prime p > 3 must be of the form 6k ± 1. (Statement 1 is TRUE)

Step 2: Evaluate Statement 2
The condition 6k ± 1 is necessary, not sufficient. A single counterexample disproves universality: for k = 4, 6(4) + 1 = 25 = 5² (composite). Similarly, for k = 6, 6(6) – 1 = 35 = 5 × 7 (composite). (Statement 2 is FALSE)

Step 3: Evaluate Statement 3
Factor p² – 1 = (p – 1)(p + 1). Because p is an odd prime > 3:

• (p – 1) and (p + 1) are consecutive even numbers ⇒ their product is divisible by 8.
• One of {p – 1, p, p + 1} is divisible by 3; since p is prime > 3, 3 | (p – 1)(p + 1).
• Since gcd(8, 3) = 1, 24 | (p² – 1). (Statement 3 is TRUE)

Correct Option: (a) 1 and 3 only

TYPE C: Existence & Arithmetic Progression Archetype

Problem Statement:
How many prime triplets of the form (p, p + 2, p + 4) exist such that all three terms are prime numbers?

(a) Exactly one
(b) Exactly two
(c) Infinitely many
(d) None

Detailed Analytical Solution:

Step 1: Modulo 3 Analysis
Any prime p can be represented in one of three residue classes modulo 3:

p ≡ 0 (mod 3), p ≡ 1 (mod 3), or p ≡ 2 (mod 3)

Step 2: Evaluate Each Residue Class

• Case 1 (p ≡ 0 (mod 3)): Since p is prime, the only multiple of 3 that is prime is p = 3.
  • Evaluating the triplet: (3, 3 + 2, 3 + 4) = (3, 5, 7). All three are prime. ⇒ Valid triplet.
• Case 2 (p ≡ 1 (mod 3)): Then p = 3k + 1.
  • p + 2 = (3k + 1) + 2 = 3k + 3 = 3(k + 1).
  • Since p > 3 ⇒ k ≥ 1, p + 2 is a multiple of 3 strictly greater than 3, making it composite.
• Case 3 (p ≡ 2 (mod 3)): Then p = 3k + 2.
  • p + 4 = (3k + 2) + 4 = 3k + 6 = 3(k + 2).
  • Since k ≥ 1, p + 4 is a multiple of 3 strictly greater than 3, making it composite.

Step 3: Conclusion
The only prime triplet of the form (p, p + 2, p + 4) is (3, 5, 7).

Correct Option: (a) Exactly one

TYPE D: Algebraic Expressions & Prime Invariants

Problem Statement:
Let p be a prime number strictly greater than 5. Consider the integer N = p² – 1. Which of the following statements is always true?

(a) N is divisible by 12, but not necessarily by 24
(b) N is always divisible by 24
(c) N is always divisible by 120
(d) N is always an odd number

Detailed Analytical Solution:

Step 1: Structural Factorization

N = p² – 1 = (p – 1)(p + 1)

Since p > 5 is prime, p is odd and not divisible by 2 or 3.

Step 2: Divisibility Analysis

• Divisibility by 8: Let p – 1 = 2k and p + 1 = 2k + 2 = 2(k + 1). Then:

  N = 4k(k + 1)

  Since k(k + 1) is the product of two consecutive integers, it is always even (2 | k(k + 1)). Hence, 8 | N.

• Divisibility by 3: Among the three consecutive integers {p – 1, p, p + 1}, exactly one is divisible by 3. Since p > 3 is prime, 3 ∤ p, forcing 3 | (p – 1)(p + 1).
• Combining Divisors: Because gcd(8, 3) = 1, N is always divisible by 8 × 3 = 24.

Step 3: Counterexample for 120
Test p = 7: N = 7² – 1 = 48. While 24 | 48, 120 ∤ 48. Thus, divisibility by 120 is not universally guaranteed.

Correct Option: (b) N is always divisible by 24

TYPE E: Divisibility & Co-Prime Factorization

Problem Statement:
A positive integer N is divisible by both 12 and 18. Which of the following statements must be true?

1. N is divisible by 36.
2. N is divisible by 216 (12 × 18).

Select the correct answer:

(a) 1 only
(b) 2 only
(c) Both 1 and 2
(d) Neither 1 nor 2

Detailed Analytical Solution:

Step 1: Prime Factor Decomposition

12 = 2² × 3¹, 18 = 2¹ × 3²

For N to be divisible by both 12 and 18, the prime factorization of N must satisfy:

Power of 2 ≥ max(2, 1) = 2
Power of 3 ≥ max(1, 2) = 2

Step 2: Evaluate Statements

• Statement 1: The minimal integer satisfying these prime factor bounds is:

  LCM(12, 18) = 2² × 3² = 36

  Therefore, any common multiple of 12 and 18 must be a multiple of 36. ⇒ True.

• Statement 2: Since gcd(12, 18) = 6 ≠ 1, we cannot multiply the divisors directly. For instance, if N = 36, N is divisible by both 12 and 18, but 36 is not divisible by 216. ⇒ False.

Correct Option: (a) 1 only

TYPE F: Perfect Numbers & Factor Fingerprints

Problem Statement:
Consider the following statements regarding the integer 28:

1. It is a perfect number.
2. It can be expressed as the sum of the first 5 prime numbers.

Which of the statements given above is/are correct?

(a) 1 only
(b) 2 only
(c) Both 1 and 2
(d) Neither 1 nor 2

Detailed Analytical Solution:

Step 1: Verify Statement 1
Find all positive proper divisors of 28:

d_proper(28) = {1, 2, 4, 7, 14}

Sum of proper divisors:

∑ d_proper = 1 + 2 + 4 + 7 + 14 = 28

Since the sum equals the number itself, 28 is a perfect number. (Statement 1 is TRUE)

Step 2: Verify Statement 2
List the first 5 prime numbers: {2, 3, 5, 7, 11}.
Calculate their sum:

2 + 3 + 5 + 7 + 11 = 28

(Statement 2 is TRUE)

Correct Option: (c) Both 1 and 2

6. The Examiner Trap Matrix

7. Core Rules & Instant Exam Deductions

Summary: Problem design in prime number theory frequently revolves around edge-case constraints: recognizing that 2 is the unique even prime, using 6k ± 1 as an elimination sieve rather than a generator, testing only up to ⌊√N⌋, and checking prime factors for composite look-alikes such as 91, 143, and 221.