Fundamental Theorem Introduction
Prime Numbers and Composite Numbers
A prime number is a natural number that is greater than 1 and it is not a product of two smaller natural numbers. A composite number is a number greater than 1 that is not a prime number, which means that a particular number is a natural number and can be expressed as a product of two or more than two numbers.
Fundamental Theorem of Arithmetic
In the year 1801, Carl Friedrich Gauss proved the fundamental theorem of Arithmetic (FTA). This theory states that every composite number can be expressed as a product of two or more prime numbers; this method of factorization is unique except for the order in which these prime factors occur. So this theory is sometimes also called a unique factorization theorem or unique prime factorization theorem.
The proof of Fundamental Theorem of Arithmetic is given below:
Let us consider a composite number 140. Factorize this number. If we keep on doing the factorization we will arrive at a stage when all the factors are prime numbers.
So, we have 140 = 2 x 2x 5 x 7.
140 can also be expressed as, 140 = 5 x 2 x 7 x 2
Hence, we observe that in both the cases, the factorization of 140, the prime numbers which appear are the same, but the order in which they appear is different. So we see that the prime factorization of 140 is unique except the order in which the prime numbers occur.
Solved Examples
1. Express Each of the Following Positive Integers as the Product of its Prime Factors by Prime Factorization Method.
a.156 b. 234
a. 156
Solution: 156 = 2 x 78
= 2 x 2 x 39
= 2 x 2 x 3 x 13
156 = 2 x 2 x 3 x 13
b. 234
Solution: 234 = 2 x 117
=2 x 3 x 39
= 2 x 3 x 3 x 13
234 = 2 x 3 x 3 x 13
2. Find the HCF and LCM of 26 and 91 and Prove that LCM × HCF = Product of Two Numbers.
Solution:
By prime factorization
26 = 2 x 13
91 = 7 x 13
HCF (26, 91) = 13
LCM (26, 91) = 13 x 2 x 7
= 26 × 7 = 182
LCM × HCF = 13 × 182 = 2366
Product of two numbers = 26 × 91 = 2366.
Hence, L.C.M. × H.C.F. = Product of two numbers.
Quiz Time
Find the HCF X LCM for the numbers 105 and 120
The HCF of two numbers is 18 and their LCM is 720. If one of the numbers is 90, find the other
Conclusion
We have explained a few examples above based on the concept for your better understanding. These notes on Fundamental Theorem of Arithmetic are created by subject-specific experts and academics with excellent knowledge on the topic. These notes are highly accurate, provide lucid explanations and illustrations wherever necessary, and thus provide an excellent learning material resource for the students to prepare for their exams.
FAQs on Fundamental Theorem of Arithmetic
1. What is LCM?
The LCM or Least Common Multiple or Lowest Common Multiple or Least Common Divisor of two or more numbers is the smallest number that is evenly divisible by all numbers in the set. To understand this, we have to look at the methodology of the process of finding LCM. The numbers are factories by taking in the common multiple of the numbers in the set and then the smallest number that is evenly divisible by all numbers in the set is chosen. It is also interesting to note that the LCM of a prime number with any other number that is not a multiple of the prime number is always 1.
2. What is HCF?
And The HCG or Highest Common Factor or the Greatest Common Divisor of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers supposedly, x and y, the HCF is denoted by HCF(x,y). For ex- The greatest common divisor of 8 and 12 is 4. This notion can be extended to polynomials and other commutative rings.
3. How to find our Prime Factorization of a Number?
Prime factorization is a method of breaking a composite number into the product of prime numbers. So, we can say that breaking a number into the simplest building blocks.
Prime factorization can be carried out in two ways
Trial division method
Factor Tree
Trial Division Method
In the trial division method, we first have to try and divide the number by the smallest prime number such that it should completely divide the number. This result is again divided by the next number. This step is again continued until we get the prime numbers. In the end, we will get the product of all prime numbers
4. Why is Prime Factorization important in cryptography?
The field of study which deals with converting plain text into code and vice versa is called cryptography. Prime factorization is a pivotal concept used in cryptography. This is so because finding the product of two prime numbers is a very easy task for the computer. But then again, guessing the product of prime numbers for the number is very difficult. And it is also time-consuming. For instance, 150 can be written as 15 x 10. But this can again be factorized into 3 x 5 x 2 x 5. Finding this product using computers is quite difficult. Hence Prime Factorisation is used in coding.
5. I am having trouble with the concept of LCM and HCF, what shall I do?
The fundamental concept of Arithmetic, from which the concepts of LCM and HCF have been derived, is one of the foundational principles of mathematics and it is extensively used in primary education as well as higher studies in the subjects of Mathematics and Computer science. Try asking the doubts to your teachers and discuss the exercise questions with your friends.