how can we prove Euclid's division lemma?
In mathematics, Euclid's lemma is most important lemma as regards divisibility and prim numbers. In simplest form, lemma states that a prime number that divides a product of two integers have to divide one of the two integers. This key fact requires a amazingly sophisticated proof and is a wanted step in the ordinary proof of the fundamental theorem of arithmetic.
Euclid’s Division Lemma
- Euclid’s division lemma, state that for a few two positive integers ‘a’ and ‘b’ we can obtain two full numbers ‘q’ and ‘r’ such that
- Euclid’s division lemma can be used to:
Find maximum regular factor of any two positive integers and to show regular properties of numbers.
- Finding Highest Common Factor (HCF) using Euclid’s division lemma:
Suppose, we hold two positive integers a and b such that a is greater than b. Apply Euclid’s division lemma to specified integers a and b to find two full numbers q and r such that, a is equal to b multiplied by q plus r.
- 'r' value is verified. If r is equal to zero then b is the HCF of the known numbers.
- If r is not equal to zero, apply Euclid’s division lemma to the latest divisor b and remainder r.
- Maintain this process till remainder r becomes zero. Value of divisor b in that case is the HCF of two given numbers.
Euclid’s division algorithm can be used to find some regular properties of numbers.
Euclid's lemma in plain language says: If a number N is a multiple of a prime number p, and N = a · b, then at least one of a and b must be a multiple of p. Say,
Obviously, in this case, 7 divides 14 (x = 2).