State division algorithm to calculate HCF.

Answer

To calculate the Highest Common Factor (HCF) using the division algorithm (Euclid's Division Lemma), follow these steps:

### Step-by-Step Solution:

1. **Identify the Two Positive Integers**: Let the two positive integers be \( a \) and \( b \), where \( a > b \).

2. **Apply Euclid's Division Lemma**:
- According to the division lemma, we can express \( a \) in terms of \( b \):
\[ a = b \cdot q + r \]
where \( q \) is the quotient and \( r \) is the remainder. Additionally, the remainder \( r \) must satisfy:
\[ 0 \leq r < b \]

3. **Check the Remainder**:
- If \( r = 0 \), then the HCF is \( b \). This means that \( b \) divides \( a \) completely, and hence \( b \) is the HCF.
- If \( r \neq 0 \), proceed to the next step.

4. **Repeat the Process**:
- Now, apply the division lemma again, but this time with \( b \) and \( r \):
\[ b = r \cdot q' + r' \]
where \( q' \) is the new quotient and \( r' \) is the new remainder.

5. **Continue the Process**:
- Repeat the steps of checking the remainder until you get a remainder of 0. Each time, replace the larger number with the smaller number and the smaller number with the remainder from the previous step.

6. **Determine the HCF**:
- When you finally reach a remainder of 0, the divisor at that step will be the HCF of the original two numbers \( a \) and \( b \).

### Example:
Let’s say we want to find the HCF of 48 and 18.

1. \( a = 48, b = 18 \)
2. Apply Euclid's Division Lemma:
\[ 48 = 18 \cdot 2 + 12 \quad (q = 2, r = 12) \]
3. Since \( r \neq 0 \), apply the lemma again with \( b = 18 \) and \( r = 12 \):
\[ 18 = 12 \cdot 1 + 6 \quad (q' = 1, r' = 6) \]
4. Since \( r' \neq 0 \), apply the lemma again with \( b = 12 \) and \( r = 6 \):
\[ 12 = 6 \cdot 2 + 0 \quad (q'' = 2, r'' = 0) \]
5. Now that the remainder is 0, the HCF is \( 6 \).