2.7 The Fundamental Theorem of Arithmetic
Theorem 2.7.1. Each integer greater than 1 can be written as a product of primes. This can
be done in a unique way.
Proof. Suppose some integer greater than \(1\) is not a product of primes, and let \(n\) be the least such, which exists by well-ordering. Then \(n\) is not itself prime, so \(n = ab\) with \(1<a<n\) and \(1<b<n\). By minimality both \(a\) and \(b\) are products of primes, and concatenating those factorisations expresses \(n\) as a product of primes — a contradiction. Hence no such \(n\) exists. □
Note. This proves existence only. Uniqueness up to order is the harder half and needs Euclid’s lemma: if a prime divides a product it divides one of the factors. Without uniqueness the statement is much weaker than it sounds, and it is uniqueness that fails in rings such as \(\mathbb {Z}\left [\sqrt {-5}\right ]\), where \(6 = 2\cdot 3 = \left (1+\sqrt {-5}\right )\left (1-\sqrt {-5}\right )\) gives two genuinely different factorisations into irreducibles.
Lemma 2.7.3. If \(\, a\, , \, b\, , \, c\,\) are integers, with \(a/bc\) and \((a,b) = 1\), then \(a/c\).
Proof. \(a/bc \, \implies \, \exists \, \) an integer \(k\ni bc = ka.\, (a,b) = 1\, \implies \, \exists \,\) integers \(\, m\, ,\, n\ni 1 = ma + nb \) \begin {align*} \implies \, c & = cma + nbc\\ & = cma + nka\\ c & = a\big (cm + nk\big ) \end {align*}
\(\implies \, a\) divides \(c\). Clearly \(a/c\).
□
Lemma 2.7.4. If \(p\) is prime and \(a_1\, ,\, a_2\, , \, \cdots \cdots \, , a_n\) are integers and \(p\, |\, a_1\,a_2\,a_3\cdots \cdots \,a_n\), then \(p\, |\,a_i\), for some \(i\, , \, 1\leq i\leq n\).
Proof. By induction on the sequence \(a_1\, ,\, a_2\, , \, \cdots \cdots \, , a_n\)
□
- 1.
- Find the divisors of 48.
Solution. \(48 = 2^4\, \cdot \, 3^1\)
Now \(\, (4 + 1)\times (1 + 1) = 10\) divisors
\(\therefore \, \, 1\, , \, 2\, , \, 3\, , \, 4\, , \, 6\, , \, 8\, , \, 12\, , \, 16\, , \, 22\, , \, 48\) are the divisors of \(48\).
- 2.
- Find the number of divisors of the number where prime factorization is \(\, p^l \cdot q^m \cdot r^m\)
Solution. Number of divisors is \(\, (l + 1)\times (m+1)\times (n+1) = (l+1)(m+1)(n+1)\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.