
We have already explored the world of real numbers and encountered irrational numbers. We will continue our discussion on real numbers and learn one of the important properties called Euclid’s division lemma.
A statement that is utilized to prove another statement can be defined as a Lemma.
A system of steps that are used to solve a problem is defined as an algorithm. Euclid’s division lemma and algorithm are closely interlinked with each other. The Euclid division lemma/algorithm has several applications related to finding properties of numbers.
STATEMENT: Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.
Now, let us try finding the integers q and r for the following pair of positive integers a and b.
(1) 10, 3 (2) 20, 4 (3) 40, 19
Let us write the relation for each pair.
1. Let a = 10 and b = 3
Therefore, 10 = 3 × 3 + 1
Here, q = 3 and r = 1, where 0 ≤ 1 < 3
2. Let a = 20 and b = 4
Therefore, 20 = 4 × 5 + 0
Here, q = 5 and r = 0, where 0 ≤ 0 < 4
3. Let a = 40 and b = 19
Therefore, 40 = 19 × 2 + 2
Here, q = 2 and r = 2, where 0 ≤ 2 < 19
If we observe from the above, for each pair of positive integers a and b, we have found whole numbers q and r, satisfying the relation:
a = bq + r, 0 ≤ r < b
It can also be noticed that q and r are unique. Note that q and r can also be zero.
Hence, it is proved.
As we learned above, Euclid's division lemma has several applications related to the properties of numbers. We use Euclid's division lemma to find HCF. We can find the HCF of large numbers, which usually takes a lot of time with general calculations. Euclid's division lemma makes our workflow easier in finding the HCF of a number.
To obtain HCF of two positive integers, say s and t, with s > t, follow the steps below:
EXAMPLE: Use Euclid’s division lemma to find the HCF of 3814 and 2562.
SOLUTION: Here a = 3814 and b = 2562
Euclid’s division lemma, a = bq + r, 0 ≤ r < b, we get,
3814 = 2562 × 1 + 1252
Since r ≠ 0, continue the process by taking
a = 2562 and b = 1252.
2562 = 1252 × 2 + 58 ( r ≠ 0 )
1252 = 58 × 21 + 34 (r ≠ 0)
58 = 34 × 1 + 24 (r ≠ 0)
34 = 24 × 1+10 (r ≠ 0)
24 = 10 × 2 +4 (r ≠ 0)
10 = 4 × 2 + 2 (r ≠ 0)
4 = 2 × 2 + 0 (r = 0)
The remainder has now become zero, so stop the procedure. Since the divisor at this stage is 2, the HCF of 3814 and 2562 is 2.
Hence we can find the HCF of any number by using Euclid’s division lemma.
JEE Main marks vs rank vs percentile
JEE Advanced Eligibility Criteria
JEE Advanced Chemistry Syllabus
JEE Advanced Registration Dates
Derivation Of Lens Maker Formula
Unit Of Pressure Velocity Uses of Plane Mirror
Wave Theory of Light
Unit of Density Unit of Light Unit of Force Unit of Magnetic Field Unit of wavelength Unit of Viscosity Uses of Electroplating Young's Modulus
What is the Scattering of Light
Lenz Law Space Wave Propagation Schrodinger Wave Equation Relation between Fahrenheit and Celsius Refractive Index Potentiometer Working Pascal Law Oscillatory Motion Optical Instruments Newton's Laws of Motion - First Law Modulation and Demodulation Magnetic Flux Lens Formula and Magnification Kaleidoscope Faradays Law Epsilon Naught Value Energy Bands Electrostatics Electroscope AC Generator Unit of Current Lithosphere Bending Equation Derivation Difference Between Pound and Kilogram Semiconductor Devices OTEC - Ocean Thermal Energy Conversion Hall Effect Rectilinear Propagation of Light Difference Between Ammeter and Voltmeter Coefficient of Linear Expansion Ampere’s Law Cyclone and Thunderstorm Save The Environment From Pollution Particle Nature of Light Types of DC Motor Uses Of Transistor Derivation of Phase Rule Unit of Humidity