Euclid Algorithm to Find HCF of 1190 and 1445

The Euclidean algorithm is a method used to find the highest common factor (HCF) of two numbers. It involves dividing the larger number by the smaller number repeatedly until the remainder becomes zero. The last non-zero remainder obtained will be the HCF of the two numbers.

Step 1: Identify the Numbers
In this case, we need to find the HCF of 1190 and 1445.

Step 2: Divide the Larger Number by the Smaller Number
Since 1445 is greater than 1190, we divide 1445 by 1190.

1445 ÷ 1190 = 1 remainder 255

Step 3: Divide the Previous Divisor by the Remainder
We now divide the previous divisor (1190) by the remainder (255).

1190 ÷ 255 = 4 remainder 170

Step 4: Repeat the Process
We continue dividing the previous divisor by the remainder until the remainder becomes zero.

255 ÷ 170 = 1 remainder 85

170 ÷ 85 = 2 remainder 0

Step 5: Last Non-Zero Remainder
The last non-zero remainder obtained is 85. Therefore, the HCF of 1190 and 1445 is 85.

Expressing HCF in the Form 1190m + 1445n
To express the HCF in the form 1190m + 1445n, we need to find the coefficients (m and n) that satisfy the equation.

Step 1: Express the Remainders in Terms of the Dividends and Divisors
Starting from the last step, we express the remainders in terms of the dividends and divisors.

85 = 255 - 1 × 170
170 = 1190 - 4 × 255
255 = 1445 - 1 × 1190

Step 2: Substitute the Expressions into the Last Non-Zero Remainder
Now we substitute the expressions obtained in the previous step into the last non-zero remainder.

85 = 255 - 1 × 170
= 255 - 1 × (1190 - 4 × 255)
= 255 - 1 × 1190 + 4 × 255
= -1 × 1190 + 5 × 255

Therefore, the HCF of 1190 and 1445 can be expressed as -1 × 1190 + 5 × 255, which can be simplified to:

HCF = -1190 + 1275
= 85

Hence, the HCF of 1190 and 1445 can be expressed as 1190(-1) + 1445(5).