Prime Numbers

Prime Numbers

1. What Is a Prime? (beginner)

Prime = integer $> 1$ divisible only by 1 and itself: 2, 3, 5, 7, 11, ... Composite = rest (4, 6, 8, 9, ...). 1 is NEITHER! Cryptography needs HUGE primes (300+ digits) — keys live or die on them!

2. Why Primes Rule Crypto

• Factoring is hard: multiply two big primes = easy; split back = infeasible (RSA security!).
• Unique factorization: every $n > 1$ = one product of primes (e.g. $60 = 2² \times 3 \times 5$).
• Field structure: arithmetic mod prime $p$ gives a field (every nonzero has inverse!) — needed for AES, RSA, Diffie-Hellman.

3. Quick Checks (exam drills!)

prime? 17 → divisors 1,17 only → PRIME
prime? 21 → 3 × 7 → COMPOSITE
prime? 2 → only even prime!
gcd(12, 18) = 6 (largest common divisor!)
12 and 25 → gcd = 1 → COPRIME (relatively prime!)

Relatively prime ($gcd = 1$) matters: RSA needs $e$ coprime to $φ(n)$!

4. Traps

• 1 is NOT prime (breaks factorization uniqueness!).
• 2 is prime (only even prime — favourite one-liner!).
• Primes infinite (Euclid's proof!): assume finite list, multiply +1 → new prime factor contradiction!

5. Exam Points

• Define prime/composite/coprime + factorize — 3-5 marks, frequent starter.
• Why primes for RSA/fields — 3 marks, frequent link.
• 2 is prime, 1 is not — 2-mark trap, evergreen.