Use Euclid's algrithm to find HCF of 1190 and 1445. Express the HCF in the form 1190m + 1445m.

Answer

To find the HCF of 1190 and 1445 using Euclid's algorithm and express it in the form of \(1190m + 1445n\), we can follow these steps:

### Step 1: Apply Euclid's Algorithm
1. Identify the two numbers: \(a = 1445\) and \(b = 1190\).
2. Perform the division:
\[ 1445 \div 1190 = 1 \quad \text{(quotient)} \]
\[ \text{Remainder} = 1445 - (1 \times 1190) = 1445 - 1190 = 255 \]

### Step 2: Continue with the Algorithm
3. Now, replace \(a\) with \(b\) and \(b\) with the remainder:
\[ a = 1190, \quad b = 255 \]
4. Perform the division:
\[ 1190 \div 255 = 4 \quad \text{(quotient)} \]
\[ \text{Remainder} = 1190 - (4 \times 255) = 1190 - 1020 = 170 \]

### Step 3: Repeat the Process
5. Replace \(a\) and \(b\):
\[ a = 255, \quad b = 170 \]
6. Perform the division:
\[ 255 \div 170 = 1 \quad \text{(quotient)} \]
\[ \text{Remainder} = 255 - (1 \times 170) = 255 - 170 = 85 \]

### Step 4: Final Step
7. Replace \(a\) and \(b\):
\[ a = 170, \quad b = 85 \]
8. Perform the division:
\[ 170 \div 85 = 2 \quad \text{(quotient)} \]
\[ \text{Remainder} = 170 - (2 \times 85) = 170 - 170 = 0 \]

Since the remainder is now 0, we conclude that the HCF is the last non-zero remainder, which is:
\[ \text{HCF} = 85 \]

### Step 5: Express HCF in the form \(1190m + 1445n\)
Now, we need to express \(85\) in the form \(1190m + 1445n\).

From our previous steps, we can backtrack:
1. From \(255 = 1445 - 1190\)
2. From \(170 = 255 - 85\)
3. From \(85 = 255 - 170\)

Now substituting back:
- Start with \(85 = 255 - 170\)
- Replace \(170\) with \(1190 - 4 \times 255\):
\[ 85 = 255 - (1190 - 4 \times 255) = 5 \times 255 - 1190 \]
- Now replace \(255\) with \(1445 - 1190\):
\[ 85 = 5 \times (1445 - 1190) - 1190 = 5 \times 1445 - 5 \times 1190 - 1190 \]
- Simplifying gives:
\[ 85 = 5 \times 1445 - 6 \times 1190 \]

Thus, we can express \(85\) as:
\[ 85 = 1190(-6) + 1445(5) \]

### Final Answer
The HCF of 1190 and 1445 is \(85\), which can be expressed as:
\[ 85 = 1190(-6) + 1445(5) \]