Factorization & Euler's Totient Function

Prime Factorization

Every integer greater than 1 can be uniquely expressed as a product of prime numbers. This is fundamental to RSA encryption and number theory.

Example: 60 = 2² × 3 × 5

Euler's Totient Function

φ(n) counts how many integers from 1 to n are coprime (relatively prime) to n. Essential for calculating private keys in RSA.

Example: φ(12) = 4 (1, 5, 7, 11 are coprime to 12)

Relative Primality

Two numbers are coprime (relatively prime) if their greatest common divisor (GCD) is 1. Used in modular arithmetic and cryptography.

gcd(a, n) = 1 means a and n are coprime

RSA Application

In RSA: n = p × q (product of two primes), and φ(n) = (p-1) × (q-1) is used to calculate the private key d.