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?
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.
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.
Thank you both for your answers!
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!
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?
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.