Find the HCF of 1260 and 7344 using Euclid's algorithm

Answer

To find the HCF (Highest Common Factor) of 1260 and 7344 using Euclid's algorithm, we will follow these steps:

### Step 1: Apply Euclid's Algorithm
We start by dividing the larger number (7344) by the smaller number (1260).

\[ 7344 \div 1260 = 5 \quad \text{(quotient)} \]
\[ 7344 - (1260 \times 5) = 7344 - 6300 = 1044 \quad \text{(remainder)} \]

### Step 2: Repeat the Process
Now, we replace the larger number with the smaller number (1260) and the smaller number with the remainder (1044), and repeat the division.

\[ 1260 \div 1044 = 1 \quad \text{(quotient)} \]
\[ 1260 - (1044 \times 1) = 1260 - 1044 = 216 \quad \text{(remainder)} \]

### Step 3: Continue Dividing
Next, we take 1044 and divide it by the new remainder (216).

\[ 1044 \div 216 = 4 \quad \text{(quotient)} \]
\[ 1044 - (216 \times 4) = 1044 - 864 = 180 \quad \text{(remainder)} \]

### Step 4: Repeat Again
Now, we take 216 and divide it by the new remainder (180).

\[ 216 \div 180 = 1 \quad \text{(quotient)} \]
\[ 216 - (180 \times 1) = 216 - 180 = 36 \quad \text{(remainder)} \]

### Step 5: Final Division
Next, we take 180 and divide it by the new remainder (36).

\[ 180 \div 36 = 5 \quad \text{(quotient)} \]
\[ 180 - (36 \times 5) = 180 - 180 = 0 \quad \text{(remainder)} \]

### Conclusion
Since we have reached a remainder of 0, the last non-zero remainder is the HCF. Therefore, the HCF of 1260 and 7344 is **36**.

---