Finding the Largest Number Dividing Powers of Two

The question asks for the largest number that divides both $2^{35} - 1$ and $2^{91} - 1$. This is the definition of the Greatest Common Divisor (GCD) of these two numbers. So, we need to find $\text{gcd}(2^{35} - 1, 2^{91} - 1)$.

There is a useful property concerning the GCD of numbers of the form $2^a - 1$ and $2^b - 1$. The property states that:

$\text{gcd}(2^a - 1, 2^b - 1) = 2^{\text{gcd}(a, b)} - 1$

In this problem, $a = 35$ and $b = 91$. Applying the property, we need to find $\text{gcd}(35, 91)$ first.

Calculating the Greatest Common Divisor of 35 and 91

We can find the GCD of 35 and 91 by listing their factors or by using prime factorization.

Method 1: Prime Factorization

• Prime factors of 35: $35 = 5 \times 7$.
• Prime factors of 91: $91 = 7 \times 13$.

The common prime factor is 7. Therefore, $\text{gcd}(35, 91) = 7$.

Method 2: Euclidean Algorithm

We can use the Euclidean algorithm to find the GCD of 35 and 91:

• Divide 91 by 35: $91 = 2 \times 35 + 21$
• Divide 35 by the remainder 21: $35 = 1 \times 21 + 14$
• Divide 21 by the remainder 14: $21 = 1 \times 14 + 7$
• Divide 14 by the remainder 7: $14 = 2 \times 7 + 0$

The last non-zero remainder is 7. Therefore, $\text{gcd}(35, 91) = 7$.

Both methods show that $\text{gcd}(35, 91) = 7$.

Applying the GCD Property

Now we can use the property $\text{gcd}(2^a - 1, 2^b - 1) = 2^{\text{gcd}(a, b)} - 1$ with $a=35$, $b=91$, and $\text{gcd}(35, 91) = 7$.

$\text{gcd}(2^{35} - 1, 2^{91} - 1) = 2^{\text{gcd}(35, 91)} - 1 = 2^7 - 1$

Calculating the Final Value

Finally, we calculate the value of $2^7 - 1$:

• $2^1 = 2$
• $2^2 = 4$
• $2^3 = 8$
• $2^4 = 16$
• $2^5 = 32$
• $2^6 = 64$
• $2^7 = 128$

So, $2^7 - 1 = 128 - 1 = 127$.

The largest number that divides both $2^{35} - 1$ and $2^{91} - 1$ is 127.

Revision Table: Key Concepts

Additional Information: Properties of Powers and GCD

The property $\text{gcd}(2^a - 1, 2^b - 1) = 2^{\text{gcd}(a, b)} - 1$ is a specific case of a more general property for integers $x > 1$: $\text{gcd}(x^a - 1, x^b - 1) = x^{\text{gcd}(a, b)} - 1$. This property is very useful in number theory problems involving exponents.

The Euclidean algorithm is a fundamental algorithm in number theory. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number, or more efficiently, by its remainder when divided by the smaller number.

Understanding GCD and its properties, especially with exponents, helps solve various problems in number theory and competitive mathematics.