Name: Fundamental Theorem of Arithmetic
Uploaded: 2019-07-19
Duration: 5 min 4 s
Description: A number can be represented in the form of the Product of their Primes. This method is also called the Fundamental Theorem of Arithmetic. Watch the video to...

Question

Using Euclid’s algorithm, find the HCF of

960

and

1575

.

Accepted Answer

Euclids Division Algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.

On applying Euclid’s division lemma, i.e. dividing $1575$ by $960$ , we get:
Quotient $= 1$ , Remainder $= 615$
$∴ 1575 = 960 \times 1 + 615$

Again on applying Euclid’s division lemma, i.e. dividing $960$ by $615$ , we get:
Quotient $= 1$ , Remainder $= 345$
$∴ 960 = 615 \times 1 + 345$

Again on applying Euclid’s division lemma, i.e. dividing $615$ by $345$ , we get:
Quotient $= 1,$ Remainder $= 270$
$∴ 615 = 345 \times 1 + 270$

Again on applying Euclid’s division lemma, i.e. dividing $345$ by $270$ , we get:
Quotient $= 1$ , Remainder $= 75$
$∴ 345 = 270 \times 1 + 75$

Again on applying Euclid’s division lemma, i.e. dividing $270$ by $75$ , we get:
Quotient $= 3$ , Remainder $= 45$
$∴ 270 = 75 \times 3 + 45$

Again on applying Euclid’s division lemma, i.e. dividing $75$ by $45,$ we get:
Quotient $= 1,$ Remainder $= 30$
$∴ 75 = 45 \times 1 + 30$

Again on applying Euclid’s division lemma, i.e. dividing $45$ by $30$ , we get:
Quotient $= 1$ , Remainder $= 15$
$∴ 45 = 30 \times 1 + 15$

Again on applying Euclid’s division lemma, i.e. dividing $30$ by $15,$ we get:
Quotient $= 2$ , Remainder $= 0$
$∴ 30 = 15 \times 2 + 0$

Hence, the HCF of $960$ and $1575$ is $15$ .

Using Euclid’s algorithm, find the HCF of $960$ and $1575$ .

Important Questions on Real Numbers

Learn and Prepare for any exam you want !

Using Euclid’s algorithm, find the HCF of 960 and 1575.

Important Questions on Real Numbers

Learn and Prepare for any exam you want !

Using Euclid’s algorithm, find the HCF of $960$ and $1575$ .