Fundamental Theorem of Arithmetic
First Step (Prop 10.1 pg 186)
Recall that, if \(a\) and \(b\) are natural numbers, there are integers \(k\) and \(l\) so that \[ \gcd(a,b) = ak+bl. \]
Proposition: Suppose that \(n\ge 2\) and that \(a_1,\ldots, a_n\) are \(n\) integers. Let \(p\) be a prime number. If \(p|(a_1\cdot a_2\cdots a_n)\) then \(p\) divides at least one of the \(a_i\).
Proof:
Second Step (Theorem 10.1, page 192)
Proposition: Any integer \(n>1\) has a unique prime factorization, meaning it can be written as a product of prime numbers, and any two such products differ only up to the order of the factors.
Step 1: Every integer has a prime factorization (strong induction).
Step 2: The prime factorization is unique (minimal counterexample).