Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number or can be expressed in the form of primes. In other words, all the natural numbers can be expressed in the form of the product of its prime factors. To recall, prime factors are the numbers which are divisible by 1 and itself only. For example, the number 35 can be written in the form of its prime factors as:
35 = 7 × 5
Here, 7 and 5 are the prime factors of 35
Similarly, another number 114560 can be represented as the product of its prime factors by using prime factorization method,
114560 = 27 × 5 × 179
So, we have factorized 114560 as the product of the power of its primes.
Therefore, every natural number can be expressed in the form of the product of the power of its primes. This statement is known as the Fundamental Theorem of Arithmetic, unique factorization theorem or the unique-prime-factorization theorem.
Proof
For this proof, we will assume that the reader already knows the following two facts:
- Every integer greater than 1 has at least one prime divisor. This implies that every integer greater than 1 is either prime or composite. (Used to show existence)
- (Euclid's Lemma) If a prime p|ab for integers a,b, then p|a or p|b. (Used to show uniqueness)
If either of these seem unfamiliar, take a moment now to think about why they are true. They can also be found in previous lessons.
There are two parts we need to prove:
- The existence of such a product of primes
- The product of primes is unique up to their order
Existence
It must be shown that every integer greater than 1 is either prime or a product of primes. First, 2 is prime. Then, by strong induction, assume this is true for all numbers greater than 1 and less than n. If n is prime, there is nothing more to prove. Otherwise, there are integers a and b, where n = ab, and 1 < a ≤ b < n. By the induction hypothesis, a = p1p2...pj and b = q1q2...qk are products of primes. But then n = ab = p1p2...pjq1q2...qk is a product of primes.
Uniqueness
To prove uniqueness, Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let n be the least such integer and write n = p1 p2 ... pj = q1 q2 ... qk, where each pi and qi is prime. (Note j and k are both at least 2.) We see p1 divides q1 q2 ... qk, so p1 divides some qi by Euclid's lemma. Without loss of generality, say p1 divides q1. Since p1 and q1 are both prime, it follows that p1 = q1. Returning to our factorizations of n, we may cancel these two terms to conclude p2 ... pj = q2 ... qk. We now have two distinct prime factorizations of some integer strictly smaller than n, which contradicts the minimality of n.
Post a Comment