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.