What is the HCF of 135 and \( 180 ? \)

To find the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of **135** and **180**, we can use two primary methods: **Prime Factorization** and the **Euclidean Algorithm**. Here's how each method works: --- ### **Method 1: Prime Factorization** 1. **Prime Factorize Each Number** - **135**: - Divide by 5: \( 135 \div 5 = 27 \) - Divide by 3: \( 27 \div 3 = 9 \) - Divide by 3: \( 9 \div 3 = 3 \) - Divide by 3: \( 3 \div 3 = 1 \) - **Prime Factors**: \( 135 = 3^3 \times 5 \) - **180**: - Divide by 5: \( 180 \div 5 = 36 \) - Divide by 2: \( 36 \div 2 = 18 \) - Divide by 2: \( 18 \div 2 = 9 \) - Divide by 3: \( 9 \div 3 = 3 \) - Divide by 3: \( 3 \div 3 = 1 \) - **Prime Factors**: \( 180 = 2^2 \times 3^2 \times 5 \) 2. **Identify Common Prime Factors** - Common primes between 135 and 180: **3** and **5**. 3. **Choose the Lowest Powers of Common Primes** - For **3**: The lower exponent is \( 3^2 \) (from 180). - For **5**: The exponent is \( 5^1 \). 4. **Calculate the HCF** \[ \text{HCF} = 3^2 \times 5 = 9 \times 5 = 45 \] --- ### **Method 2: Euclidean Algorithm** The Euclidean Algorithm is a method based on division to find the HCF. 1. **Apply the Algorithm** - **Step 1**: Divide the larger number by the smaller number and find the remainder. \[ 180 \div 135 = 1 \quad \text{with a remainder of} \quad 45 \] - **Step 2**: Replace the larger number with the smaller number and the smaller number with the remainder. \[ \text{Now find HCF}(135, 45) \] - **Step 3**: Repeat the process. \[ 135 \div 45 = 3 \quad \text{with a remainder of} \quad 0 \] - **Conclusion**: When the remainder is 0, the divisor at this step is the HCF. 2. **HCF is 45** --- ### **Final Answer** The **HCF of 135 and 180 is 45**.