Prime numbers are the irreducible building blocks of the integers. Unique factorization rests on one decisive property: a prime dividing a product must divide one factor.
Irreducibles and primes
Definition. An integer \(p>1\) is prime if its only positive divisors are \(1,p\). An integer \(n>1\) is composite otherwise.
Euclid's lemma. If \(p\) is prime and \(p\mid ab\), then \(p\mid a\) or \(p\mid b\).
Proof. If \(p\nmid a\), then \(\gcd(p,a)=1\), so Bezout gives \(px+ay=1\). Multiplying by \(b\) yields \(pbx+aby=b\). Both terms on the left are divisible by \(p\), hence \(p\mid b\).
Fundamental theorem of arithmetic
Theorem. Every integer \(n>1\) can be written \[ n=p_1^{\alpha_1}\cdots p_r^{\alpha_r} \] with distinct primes \(p_i\) and positive exponents \(\alpha_i\). This factorization is unique up to ordering.
Proof. Strong induction proves existence: if \(n\) is not prime, write \(n=ab\) with \(1<a,b<n\) and factor both by induction. For uniqueness, if \(p_1\cdots p_k=q_1\cdots q_\ell\), Euclid's lemma makes \(p_1\) divide some \(q_j\), hence equal it. Cancel and induct on the number of factors.
The exponent valuation \[ v_p(n)=\max\{k:p^k\mid n\} \] turns factorization into coordinates: \[ v_p(mn)=v_p(m)+v_p(n),\quad v_p(\gcd(m,n))=\min(v_p(m),v_p(n)). \]
Infinitude and distribution of primes
Theorem (Euclid). There are infinitely many primes.
Proof. If \(p_1,\ldots,p_r\) were all primes, then \[ N=p_1\cdots p_r+1 \] would have a prime divisor \(q\). No \(p_i\) divides \(N\), since it leaves remainder \(1\), contradicting completeness of the list.
Proposition. Every composite \(n\) has a prime divisor at most \(\sqrt n\).
Proof. Write \(n=ab\) with \(1<a\le b\). Then \(a\le\sqrt n\), and some prime divisor of \(a\) is at most \(a\).
Perfect powers and divisor counts
If \(n=\prod p_i^{\alpha_i}\), then every divisor has the unique form \(\prod p_i^{\beta_i}\) with \(0\le\beta_i\le\alpha_i\). Hence \[ \tau(n)=\prod_i(\alpha_i+1),\qquad \sigma(n)=\prod_i\frac{p_i^{\alpha_i+1}-1}{p_i-1}. \] An integer is a square exactly when every \(v_p(n)\) is even. These simple consequences illustrate the central principle: multiplicative questions become additive or coordinatewise after prime factorization.
Example. \(360=2^3\cdot3^2\cdot5\), so \[ \tau(360)=4\cdot3\cdot2=24,\qquad \sigma(360)=15\cdot13\cdot6=1170. \]