Find the HCF of `(2^(315) - 1) and (2^(25) -1)` is

Options

A. 5
B. 2
C. 31
D. None of these

Answer

To find the HCF of \(2^{315} - 1\) and \(2^{25} - 1\), we can use the property of HCF for numbers of the form \(2^m - 1\) and \(2^n - 1\). The property states that:

\[ \text{HCF}(2^m - 1, 2^n - 1) = 2^{\text{HCF}(m, n)} - 1 \]

### Step 1: Identify \(m\) and \(n\)
Here, we have:
- \(m = 315\)
- \(n = 25\)

### Step 2: Find the HCF of \(m\) and \(n\)
Next, we need to find \(\text{HCF}(315, 25)\).

To find the HCF, we can use the prime factorization method or the Euclidean algorithm. We'll use the Euclidean algorithm here:

1. Divide \(315\) by \(25\):
\[ 315 \div 25 = 12 \quad \text{(quotient)} \]
\[ 315 - (25 \times 12) = 315 - 300 = 15 \quad \text{(remainder)} \]

2. Now, apply the algorithm again with \(25\) and the remainder \(15\):
\[ 25 \div 15 = 1 \quad \text{(quotient)} \]
\[ 25 - (15 \times 1) = 25 - 15 = 10 \quad \text{(remainder)} \]

3. Now, apply the algorithm again with \(15\) and the remainder \(10\):
\[ 15 \div 10 = 1 \quad \text{(quotient)} \]
\[ 15 - (10 \times 1) = 15 - 10 = 5 \quad \text{(remainder)} \]

4. Finally, apply the algorithm with \(10\) and the remainder \(5\):
\[ 10 \div 5 = 2 \quad \text{(quotient)} \]
\[ 10 - (5 \times 2) = 10 - 10 = 0 \quad \text{(remainder)} \]

Since the remainder is now \(0\), the last non-zero remainder is \(5\). Thus, \(\text{HCF}(315, 25) = 5\).

### Step 3: Calculate the HCF of \(2^{315} - 1\) and \(2^{25} - 1\)
Now we can use the property we stated earlier:
\[ \text{HCF}(2^{315} - 1, 2^{25} - 1) = 2^{\text{HCF}(315, 25)} - 1 = 2^5 - 1 \]

### Step 4: Calculate \(2^5 - 1\)
Now we calculate:
\[ 2^5 = 32 \]
Thus,
\[ 2^5 - 1 = 32 - 1 = 31 \]

### Final Answer
Therefore, the HCF of \(2^{315} - 1\) and \(2^{25} - 1\) is \(31\).

---