Fundamental Theorem of Arithmetic

What is the Fundamental Theorem of Arithmetic?

The fundamental theorem of arithmetic states that every integer greater than 1 either is prime itself or is the product of prime numbers and this product of prime numbers is unique. It is also known as the unique factorization theorem or unique prime factorization theorem.

Fundamental theorem of Arithmetic Proof

Prime factor of composite number is always multiple of prime:

10 = 2 x 5

12 = 2 x 2 x 3

14 = 2 x 7

15 = 3 x 5

The product of prime number is Unique because these multiple factors are not multiple factors of another number.

Example: The multiple factors of 10 are 2 x 5. This factor (2 x 5) is multiple factors of only 10. It cannot be multiple factors of any other number. That is why it is called unique.

 

This theorem is one of the main reasons why 1 is not considered a prime number. If 1 were prime then factorization into primes would not be unique.

   Ex: 5 = 5 x 1 = 5 x 1 x 1 = —–

Prime Number

A prime number is a number that cannot be exactly divided by any other number (except 1 or itself).

Example: 2, 3, 5, 7, 11, 13, ——

Composite Number

A composite number is a positive integer that is not primed. All even numbers except 2 are composite numbers. 1 is neither a prime nor a composite number.

Ex: 4, 6, 8,9,10,12,14,15  ——-

Definition of Euclid’s Division Lemma

According to Euclid’s Division Lemma, given two positive integers ‘a’ and ‘b’, there exist unique whole numbers q and r satisfying a = bq + r, 0  r < b.

Euclid’s division lemma is also called Euclid’s division algorithms. To find the highest common factor (HCF) of two positive integers ‘a’ and ‘b’ we use Euclid’s division algorithm. The largest number which exactly divides two or more positive integers is called HCF.

 

Application of Euclid’s Division Algorithm

To obtain the HCF of two positive integers, say a and b, a > b, follow the steps below:

Step1. On dividing a by b, we get the quotient q and remainder r such that a = bq + r, where 0 r < b.

Step2. If r=0 then HCF (a,b) = b

If r  0 then apply the division lemma to b and r.

Step3. Continue the process until the remainder becomes 0. The remainder has now become zero, so our procedure stops. The last divisor will be the required HCF.

Euclid’s Division Lemma (or Algorithm)

Consider we have two numbers 272 and 1032. Use Euclid’s algorithms to find the HCF of both of these numbers.

Since 1032 > 272, 1032 is divided by 272 to get 3 as the quotient and 216 as the remainder. Apply Euclid’s division algorithms, we get

1032 = 272 x 3 + 216

Since the remainder is not equal to 0. Further, apply the Euclid division method, we get

272 = 216 x 1 + 56

Since the remainder is not equal to 0. Further, apply the Euclid division method, we get

216 = 56 x 3 + 48

Since the remainder is not equal to 0. Further, apply the Euclid division method, we get

56 = 48 x 1 + 8

Since the remainder is not equal to 0. Further, apply the Euclid division method, we get

48 = 8 x 6 + 0

The remainder has now become 0, so our procedure stops, and the last divisor will be the required HCF.

Hence, HCF of 272 and 1032 = 8

This method is also known as the successive division method.

 

Read More…