Find the HCF of the following pairs of integers and express it as a linear combination of them.
(i) 963 and 657
(ii) 592 and 252
(iii) 506 and 1155
(iv) 1288 and 575
(i) We need to find the H.C.F. of 963 and 657 and express it as a linear combination of 963 and 657.
By applying Euclid's division lemma $963=657 \times 1+306$
Since remainder $\neq 0$, apply division lemma on divisor 657 and remainder 306
$657=306 \times 2+45$
Since remainder $\neq 0$, apply division lemma on divisor 306 and remainder 45
$306=45 \times 6+36$
Since remainder $\neq 0$, apply division lemma on divisor 45 and remainder 36
$45=36 \times 1+9$
Since remainder $\neq 0$, apply division lemma on divisor 36 and remainder 9
$36=9 \times 4+0$
Therefore, H.C.F. = 9.
Now,
$9=45-36 \times 1$
$=45-[306-45 \times 6] \times 1$
$=45-306 \times 1+45 \times 6$
$=45 \times 7-306 \times 1$
$=[657-306 \times 2] \times 7-306 \times 1$
$=657 \times 7-306 \times 14-306 \times 1$
$=657 \times 7-306 \times 15$
$=657 \times 7-[963-657 \times 1] \times 15$
$=657 \times 7-963 \times 15+657 \times 15$
$=657 \times 22-963 \times 15 .$
(ii) We need to find the H.C.F. of 592 and 252 and express it as a linear combination of 592 and 252.
By applying Euclid’s division lemma
592 = 252×2+88
Since remainder $\neq 0$, apply division lemma on divisor 252 and remainder 88
252 = 88×2+76
Since remainder $\neq 0$, apply division lemma on divisor 88 and remainder 76
88 = 76×1+12
Since remainder $\neq 0$, apply division lemma on divisor 76 and remainder 12
76 = 12×6+4
Since remainder $\neq 0$, apply division lemma on divisor 12 and remainder 4
12 = 4×3+0.
Therefore, H.C.F. = 4.
Now,
$4=76-12 \times 6$
$=76-[88-76 \times 1] \times 6$
$=76-88 \times 6+76 \times 6$
$=76 \times 7-88 \times 6$
$=(252-88 \times 2) \times 7-88 \times 6$
$=252 \times 7-88 \times 14-88 \times 6$
$=252 \times 7-88 \times 20$
$=252 \times 7-[592-252 \times 2] \times 20$
$=252 \times 7-592 \times 20+252 \times 40$
$=252 \times 47-592 \times 20$
$=252 \times 47+592 \times(-20)$
(iii) We need to find the H.C.F. of 506 and 1155 and express it as a linear combination of 506 and 1155.
By applying Euclid’s division lemma
$1155=506 \times 2+143$
Since remainder $\neq 0$, apply division lemma on divisor 506 and remainder 143
$506=143 \times 3+77$
Since remainder $\neq 0$, apply division lemma on divisor 143 and remainder 77
$143=77 \times 1+66$
Since remainder $\neq 0$, apply division lemma on divisor 77 and remainder 66
$77=66 \times 1+11$
Since remainder $\neq 0$, apply division lemma on divisor 66 and remainder 11
$66=11 \times 6+0$
Therefore, H.C.F. = 11.
Now,
$11=77-66 \times 1$
$=77-[143-77 \times 1] \times 1$
$=77-143 \times 1+77 \times 1$
$=77 \times 2-143 \times 1$
$=[506-143 \times 3] \times 2-143 \times 1$
$=506 \times 2-143 \times 6-143 \times 1$
$=506 \times 2-143 \times 7$
$=506 \times 2-[1155-506 \times 2] \times 7$
$=506 \times 2-1155 \times 7+506 \times 14$
$=506 \times 16-1155 \times 7 .$
(iv) We need to find the H.C.F. of 1288 and 575 and express it as a linear combination of 1288 and 575.
By applying Euclid’s division lemma
$1288=575 \times 2+138$
Since remainder $\neq 0$, apply division lemma on divisor 575 and remainder 138
$575=138 \times 4+23 .$
Since remainder $\neq 0$, apply division lemma on divisor 138 and remainder 23
$138=23 \times 6+0$
Therefore, H.C.F. = 23.
Now,
$23=575-138 \times 4$
$=575-[1288-575 \times 2] \times 4$
$=575-1288 \times 4+575 \times 8$
$=575 \times 9-1288 \times 4$
- JEE Main
- Exam Pattern
- Previous Year Papers
- PYQ Chapterwise
- Physics
- Kinematics 1D
- Kinemetics 2D
- Friction
- Work, Power, Energy
- Centre of Mass and Collision
- Rotational Dynamics
- Gravitation
- Calorimetry
- Elasticity
- Thermal Expansion
- Heat Transfer
- Kinetic Theory of Gases
- Thermodynamics
- Simple Harmonic Motion
- Wave on String
- Sound waves
- Fluid Mechanics
- Electrostatics
- Current Electricity
- Capacitor
- Magnetism and Matter
- Electromagnetic Induction
- Atomic Structure
- Dual Nature of Matter
- Nuclear Physics
- Radioactivity
- Semiconductors
- Communication System
- Error in Measurement & instruments
- Alternating Current
- Electromagnetic Waves
- Wave Optics
- X-Rays
- All Subjects
- Physics
- Motion in a Plane
- Law of Motion
- Work, Energy and Power
- Systems of Particles and Rotational Motion
- Gravitation
- Mechanical Properties of Solids
- Mechanical Properties of Fluids
- Thermal Properties of matter
- Thermodynamics
- Kinetic Theory
- Oscillations
- Waves
- Electric Charge and Fields
- Electrostatic Potential and Capacitance
- Current Electricity
- Thermoelectric Effects of Electric Current
- Heating Effects of Electric Current
- Moving Charges and Magnetism
- Magnetism and Matter
- Electromagnetic Induction
- Alternating Current
- Electromagnetic Wave
- Ray Optics and Optical Instruments
- Wave Optics
- Dual Nature of Radiation and Matter
- Atoms
- Nuclei
- Semiconductor Electronics: Materials, Devices and Simple Circuits.
- Chemical Effects of Electric Current,
All Study Material
- JEE Main
- Exam Pattern
- Previous Year Papers
- PYQ Chapterwise
- Physics
- Kinematics 1D
- Kinemetics 2D
- Friction
- Work, Power, Energy
- Centre of Mass and Collision
- Rotational Dynamics
- Gravitation
- Calorimetry
- Elasticity
- Thermal Expansion
- Heat Transfer
- Kinetic Theory of Gases
- Thermodynamics
- Simple Harmonic Motion
- Wave on String
- Sound waves
- Fluid Mechanics
- Electrostatics
- Current Electricity
- Capacitor
- Magnetism and Matter
- Electromagnetic Induction
- Atomic Structure
- Dual Nature of Matter
- Nuclear Physics
- Radioactivity
- Semiconductors
- Communication System
- Error in Measurement & instruments
- Alternating Current
- Electromagnetic Waves
- Wave Optics
- X-Rays
- All Subjects
- Physics
- Motion in a Plane
- Law of Motion
- Work, Energy and Power
- Systems of Particles and Rotational Motion
- Gravitation
- Mechanical Properties of Solids
- Mechanical Properties of Fluids
- Thermal Properties of matter
- Thermodynamics
- Kinetic Theory
- Oscillations
- Waves
- Electric Charge and Fields
- Electrostatic Potential and Capacitance
- Current Electricity
- Thermoelectric Effects of Electric Current
- Heating Effects of Electric Current
- Moving Charges and Magnetism
- Magnetism and Matter
- Electromagnetic Induction
- Alternating Current
- Electromagnetic Wave
- Ray Optics and Optical Instruments
- Wave Optics
- Dual Nature of Radiation and Matter
- Atoms
- Nuclei
- Semiconductor Electronics: Materials, Devices and Simple Circuits.
- Chemical Effects of Electric Current,