1. Primes, divisibility

Given are two different primes $\displaystyle a,b\neq 2$. Show that $\displaystyle 2^{ab}-1$ has at least three different prime divisors.

How would I go about first of all?

2. Think about the formula for a geometric progression:

$\displaystyle 1 + 2^b + 2^{2b} + \cdots + 2^{(a-1)b} = \frac {2^{ab} - 1}{2^b - 1}$

which gives you two divisors straight off.

3. Let's factor.

$\displaystyle 2^{ab} - 1 = (2^a)^b - 1^b = (2^a - 1)(f(a,b))$

AND

$\displaystyle 2^{ab} - 1 = (2^b)^a - 1^a = (2^b - 1)(f(b,a))$

$\displaystyle f(x,y)$ is an integral polynomial.

So, $\displaystyle 2^a - 1$ and $\displaystyle 2^b - 1$ are factors. If either of these are composite, then we have 3 prime factors readily. If they are both prime, then we observe $\displaystyle (2^a - 1)(2^b - 1) < 2^{ab} - 1$, so we have another factor, $\displaystyle c$.

So, $\displaystyle 2^{ab} - 1 = c(2^a - 1)(2^b - 1)$.

It does not matter whether any of these factors are composite. If they are composite, they have at least one prime factor. Hence, we have at least 3 prime factors.

Matt: could you tell me more on hwo your method involves the fact that the divisors have to be different? Eg. for b=3, we would have 8=2*2*2 in the denominator, so only one divisor, and how do we know how many there are on the left side?
Elemental: by integral polynomial you mean a polynomial with integer coefficients? If so, could you explain how you factor the f(a,b) or f(b,a) out? I don't really see it.

Sorry if I'm just being ignorant!

5. Originally Posted by atreyyu
Elemental: by integral polynomial you mean a polynomial with integer coefficients? If so, could you explain how you factor the f(a,b) or f(b,a) out? I don't really see it.
Yes, it has integer coefficients. This is a general polynomial. If we have an odd integer, $\displaystyle n$, then we can ALWAYS factor an expression of the form:
$\displaystyle a^n - b^n$. For example, for $\displaystyle n=3$, we have:
$\displaystyle a^3 - b^3 = (a - b)(a^2 + ab + 1)$. In general, we have:
$\displaystyle a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + ... + ab^{n-2} + b^{n-1})$.
Notice the term $\displaystyle (a - b)$ is always there.

Since you said your primes $\displaystyle a, b$ are odd (since they aren't 2), then your expression:
$\displaystyle 2^{ab} - 1$ is of the form $\displaystyle a^n - b^n$. So basically I have factored it in two ways, yielding two distinct factors:
$\displaystyle 2^a - 1$ and $\displaystyle 2^b - 1$. The polynomial I was referring to was simply:
$\displaystyle f(a,b) = a^{n-1} + a^{n-2}b + ... + ab^{n-2} + b^{n-1}$
I did not spell it out before because it wasn't important.

All you needed to know is that it WAS factorable.

Make sense?

6. Sure. Thanks a lot!

7. My solution was the same as that of elemental, just that I didn't go into all the detail (just gave you the clue you needed to do the rest yourself). Elemental finished it off.

8. Originally Posted by atreyyu
Given are two different primes $\displaystyle a,b\neq 2$. Show that $\displaystyle 2^{ab}-1$ has at least three different prime divisors.
The above comments show that $\displaystyle 2^{ab}-1$ has at least three (prime) factors. But the question is asking for something much stronger than that, namely that $\displaystyle 2^{ab}-1$ is divisible by three different primes. For a proof of this difficult result, see melese's comment #3 in this thread.

9. Zing, I thought that would be easier! Thanks for your input!