Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
+1 vote
1.8k views
in Number System by (32.2k points)
closed by

Using Euclid’s algorithm, find the HCF of 

(i) 405 and 2520 

(ii) 504 and 1188 

(iii) 960 and 1575

1 Answer

+1 vote
by (32.1k points)
selected by
 
Best answer

(i)

On applying Euclid’s algorithm, i.e. dividing 2520 by 405, we get: 

Quotient = 6, Remainder = 90 

∴ 2520 = 405 × 6 + 90 

Again on applying Euclid’s algorithm, i.e. dividing 405 by 90, we get: 

Quotient = 4, Remainder = 45 

∴ 405 = 90 × 4 + 45 

Again on applying Euclid’s algorithm, i.e. dividing 90 by 45, we get: 

∴ 90 = 45 × 2 + 0 

Hence, the HCF of 2520 and 405 is 45.

(ii)

On applying Euclid’s algorithm, i.e. dividing 1188 by 504, we get: 

Quotient = 2, Remainder = 180 

∴ 1188 = 504 × 2 + 180 

Again on applying Euclid’s algorithm, i.e. dividing 504 by 180, we get: 

Quotient = 2, Remainder = 144 

∴ 504 = 180 × 2 + 144 Again on applying Euclid’s algorithm, i.e. dividing 180 by 144, we get: 

Quotient = 1, Remainder = 36 

∴ 180 = 144 × 1 + 36 

Again on applying Euclid’s algorithm, i.e. dividing 144 by 36, we get: 

∴ 144 = 36 × 4 + 0 

Hence, the HCF of 1188 and 504 is 36.

(iii)

On applying Euclid’s algorithm, i.e. dividing 1575 by 960, we get: 

Quotient = 1, Remainder = 615 

∴ 1575 = 960 × 1 + 615 

Again on applying Euclid’s algorithm, i.e. dividing 960 by 615, we get: 

Quotient = 1, Remainder = 345 

∴ 960 = 615 × 1 + 345 

Again on applying Euclid’s algorithm, i.e. dividing 615 by 345, we get: 

Quotient = 1, Remainder = 270 

∴ 615 = 345 × 1 + 270 

Again on applying Euclid’s algorithm, i.e. dividing 345 by 270, we get: 

Quotient = 1, Remainder = 75 

∴ 345 = 270 × 1 + 75 

Again on applying Euclid’s algorithm, i.e. dividing 270 by 75, we get: 

Quotient = 3, Remainder = 45 

∴ 270 = 75 × 3 + 45 

Again on applying Euclid’s algorithm, i.e. dividing 75 by 45, we get: 

Quotient = 1, Remainder = 30 

∴ 75 = 45 × 1 + 30 

Again on applying Euclid’s algorithm, i.e. dividing 45 by 30, we get: 

Quotient = 1, Remainder = 15 

∴ 45 = 30 × 1 + 15 

Again on applying Euclid’s algorithm, i.e. dividing 30 by 15, we get:

Quotient = 2, Remainder = 0 

∴ 30 = 15 × 2 + 0 

Hence, the HCF of 960 and 1575 is 15.

Related questions

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...