Fundamental Theorem of Arithmetic
The fundamental theorem of arithmetic says that "factorization of every composite number can be expressed as a product of primes irrespective of the order in which the prime factors of that respective number occurs". The fundamental theorem of arithmetic is a very useful method to understand the prime factorization of any number.
| 1. | Fundamental Theorem of Arithmetic Definition |
| 2. | Fundamental Theorem of Arithmetic Proof |
| 3. | HCF and LCM Using Fundamental Theorem of Arithmetic |
| 4. | FAQs on Fundamental Theorem of Arithmetic |
Fundamental Theorem of Arithmetic Definition
The statement of the fundamental theorem of arithmetic is: "Every composite number can be factorized as a product of primes, and this factorization is unique, apart from the order in which the prime factors occur."
For example, let us find the prime factorization of 240.
From the above figure, we get 240 = 2 × 2 × 2 × 2 × 3 × 5. This theorem further tells us that this factorization must be unique. That is, there is no other way to express 240 as a product of primes. Of course, we can change the order in which the prime factors occur. For example, the prime factorization can be written as: 240 = 31 × 24 × 51 or 31× 22 × 51 × 22 etc. But the set of prime factors (and the number of times each factor occurs) is unique. That is, 240 can have only one possible prime factorization, with four factors of 2 that is 24, one factor of 3 that is 31, and one factor of 5 that is 51.
Fundamental Theorem of Arithmetic Proof
To prove the fundamental theorem of arithmetic, we have to prove the existence and the uniqueness of the prime factorization. Thus, the fundamental theorem of arithmetic proof is done in two steps. We will prove that for every integer, n ≥ 2, it can be expressed as the product of primes in a unique way: n = p1 × p2 ×⋯ × pi.
Step 1 - Existence of Prime Factorization
We will prove this using mathematical induction.
Basic Step: The statement is true for n = 2.
Assumption Step: Let us assume that the statement is true for n = k.
Then, k can be written as the product of primes.
Induction Step: Let us prove that the statement is true for n = k + 1.
If k + 1 is prime, then the case is obvious.
If k + 1 is NOT prime, then it definitely has some prime factor, say p.
Then k + 1 = pj, where j < k →(1)
Since j < k, by the "inductive step", k can be written as the product of primes.
Thus, from (1), k + 1 can also be written as the product of primes. Thus, by the mathematical induction, the "existence of factorization" is proved.
Step 2 - Uniqueness of Prime Factorization
Let us assume that n can be written as the product of primes in two different ways, say,
n = p1p2⋯pi, or,
n= q1q2⋯qj
Since these are prime factorization, q1,q2,…,qj are coprime numbers (as they are prime numbers).
Therefore, by Euclid's lemma, p1 divides only one of the primes.
Note that q1 is the smallest prime and so p1= q1.
In the same way, we can prove that pn = qn, for all n.
Hence, i = j.
Thus, the prime factorization of n is unique.
HCF and LCM Using Fundamental Theorem of Arithmetic
To find the HCF and LCM of two numbers, we use the fundamental theorem of arithmetic. For this, we first find the prime factorization of both numbers. Next, we consider the following:
- HCF is the product of the smallest power of each common prime factor.
- LCM is the product of the greatest power of each common prime factor.
For example, let's find the HCF of 850 and 680. For this, first, we will find the prime factorization of these numbers.
Prime factorization of 850 = 21 × 52 × 171
Prime factorization of 680 = 23 × 51 × 171
HCF is the product of the smallest power of each common prime factor. Hence, HCF (850, 680) = 21 × 51 × 171 = 170.
LCM is the product of the greatest power of each common prime factor. Hence, LCM (850, 680) = 23 × 52 × 171 = 3400.
Thus,
HCF (850, 680) = 170
LCM (850, 680) = 3400
Related Articles on Fundamental Theorem of Arithmetic
Check out these interesting articles to know more about the fundamental theorem of arithmetic and its related topics.
FAQs on Fundamental Theorem of Arithmetic
What is the Fundamental Theorem of Arithmetic?
The fundamental theorem of arithmetic states that every composite number can be factorized as a product of primes, and this factorization is unique, apart from the order in which the prime factors occur.
Why is the Fundamental Theorem of Arithmetic Important?
The fundamental theorem of the arithmetic statement ensures the existence and the uniqueness of the prime factorization of a number which is used in the process of finding the HCF and LCM.
How do you find the LCM using the Fundamental Theorem of Arithmetic?
To find the LCM of two numbers, we use the fundamental theorem of arithmetic. To do so, we have to first find the prime factorization of both numbers. The LCM is the product of the greatest power of each common prime factor.
What is the Fundamental Theorem of Arithmetic Formula?
There is no such thing as the fundamental theorem of the arithmetic formula. But, the definition of the fundamental theorem of arithmetic states that "any composite number can be expressed as the product of primes in a unique way, except for the order of the primes."
Who proved Fundamental Theorem of Arithmetic?
The fundamental theorem of arithmetic was proved by Carl Friedrich Gauss in 1801. He proved that every positive integer greater than 1 can be expressed as a product of primes.
Explain the Fundamental Theorem of Arithmetic with an Example?
Let's do the prime factorization of the number 15. The prime factors of 15 are 3 × 5. It turns out that the composite number 15 has a unique prime factorization and it is different from any other natural number. Thus, every composite number can be expressed as the product of its primes in a unique way is known as the fundamental theorem of arithmetic.