Using Euclid's Algorithm, find the HCF of 2048 and 960

Answer

To find the HCF (Highest Common Factor) of 2048 and 960 using Euclid's Algorithm, we follow these steps:

### Step 1: Identify the two numbers
We have two numbers: 2048 and 960.

### Step 2: Apply Euclid's Algorithm
Euclid's Algorithm states that the HCF of two numbers can be found by repeatedly applying the division algorithm. We start by dividing the larger number by the smaller number and taking the remainder.

1. **Divide 2048 by 960**:
\[ 2048 \div 960 = 2 \quad \text{(quotient)} \]
\[ \text{Remainder} = 2048 - (960 \times 2) = 2048 - 1920 = 128 \]

### Step 3: Replace the larger number
Now we replace the larger number (2048) with the smaller number (960) and the smaller number with the remainder (128).

2. **Now divide 960 by 128**:
\[ 960 \div 128 = 7 \quad \text{(quotient)} \]
\[ \text{Remainder} = 960 - (128 \times 7) = 960 - 896 = 64 \]

### Step 4: Repeat the process
Now we replace 960 with 128 and 128 with the remainder (64).

3. **Now divide 128 by 64**:
\[ 128 \div 64 = 2 \quad \text{(quotient)} \]
\[ \text{Remainder} = 128 - (64 \times 2) = 128 - 128 = 0 \]

### Step 5: Conclusion
Since the remainder is now 0, we stop here. The last non-zero remainder is the HCF.

Thus, the HCF of 2048 and 960 is **64**.

### Summary of Steps:
1. Divide 2048 by 960, remainder is 128.
2. Divide 960 by 128, remainder is 64.
3. Divide 128 by 64, remainder is 0.
4. The last non-zero remainder is the HCF, which is 64.

---