Fundamental Theorem of Arithmetic

Fundamental Theorem Introduction

In earlier sessions, we have learned about prime numbers and composite numbers. We know that prime numbers are the numbers that can be divided by itself and only 1. For example: 2,3,5,7,11,13, 19……...are some of the prime numbers. And composite numbers are the numbers that have more than two factors. We can say that composite numbers are the product of prime numbers. For example, 4, 6, 8, 10, 12………..all these numbers have more than two factors so-called composite numbers. 

Now let us study what is the Fundamental Theorem of Arithmetic.

Fundamental Theorem of Arithmetic

The fundamental theorem of Arithmetic(FTA) was proved by Carl Friedrich Gauss in the year 1801.

It states that every composite number can be expressed as a product of prime numbers, this factorization is unique except for the order in which the prime factors occur. So it is also called a unique factorization theorem or the unique prime factorization theorem.

Proof of Fundamental Theorem of Arithmetic(FTA)

For example, consider a given 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.

As shown in the below figure, we have 140 = 2 x 2x 5 x 7.

[Image will be Uploaded Soon]

Also, we can factorize it as shown in the below figure,

[Image will be Uploaded Soon]

We observe that in both the factorization of 140, the prime numbers appearing are the same, although the order in which they appear is different. Thus the prime factorization of 140 is unique except the order in which the prime numbers occur.

Consider another example: 30

It can be factorize as 30 = 2 x 3 x 5 ; 30 = 3 x 2 x 5 ; 30 = 5 x 2 x 3 

Hence we can say that in general, a composite number is expressed as the product of prime factors written in ascending order of their values.

There exists only a single way to represent a composite number by the product of prime factors, not taking into consideration the order of the prime factors.

In general form , a composite number “ x ” can be expressed as,

x = p1,p2,p3, p4,.......pn where p1,p2,p3, p4,.......pn  are the prime factors. The prime factors are represented in ascending order such that  p1 ≤ p2 ≤  p3 ≤  p4 ≤ ....... ≤ pn.

If we write the prime factors in ascending order the representation becomes unique. So we can say that every composite number can be expressed as the products of powers distinct primes in ascending or descending order in a unique way.

Application of Fundamental Theorem of Arithmetic

Fundamental Theorem of Arithmetic is used to find

  1. Highest Common Divisor(HCF)

  2. Lowest Common Multiple(LCM)

 

For any two positive integers:

Some Formulas for LCM and HCF

LCM of a Number x HCF of a Number = Product of the Numbers

LCM = \[\frac{Product of the Numbers}{HCF}\] 

HCF= \[\frac{Product of the Numbers}{LCM}\]  

One Number =  \[\frac{LCM X HCF}{Other Number}\]  

 

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

  1. Find the HCF X LCM for the numbers 105 and 120

  2. The HCF of two numbers is 18 and their LCM is 720. If one of the numbers is 90, find the other

FAQ (Frequently Asked Questions)

1. How to Find Out Prime Factorization of a Number?

Answer: Prime factorization is a method of breaking the composite number into the product of prime numbers. Or we can say that breaking a number into the simplest building blocks.

Prime factorization can be carried out in two ways 

  1. Trial division method

  2. Factor Tree

  • Trial Division Method

In the trial division method, we first try to divide the number by the smallest prime number such that it should completely divide the number. The result is again divided by the next number. This step is continued until we get the prime numbers. At last, we will get the product of all prime numbers. For example, let us factorize 100

  • 100 ÷ 2 = 50; first factor is  2

  • 50 ÷ 2 = 25; second factor is again 2 

  • 25 ÷ 5 = 5, not completely divisible by 2 and 3 so divide  by next highest number 5, so the third factor is 5 

  • 5 ÷ 5 = 1; again it is completely divisible by 5 so the last factor is 5

The resulting prime factors are multiples of, 2 x 2 x 5 x 5 

  • Factor Tree

The following figure shows how the concept of factor tree implies. Keep on factoring the number until you get the prime number.

[Image will be Uploaded Soon]

Prime factorization is basically used in cryptography, or when you have to secure your data.

2. Why is Primes Factorization Important in Cryptography?

Answer: The study of converting the plain text into code and vice versa is called cryptography. Prime factorization is a vital concept used in cryptography. This is because finding the product of two prime numbers is a very easy task for the computer. But on the contrary, 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 be further factorized into 3 x 5 x 2 x 5. For computers finding this product is quite difficult. Hence this concept is used in coding.