# Thread: Primes, divisibility

1. ## Primes, divisibility

Given are two different primes $a,b\neq 2$. Show that $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:

$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.

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

AND

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

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

So, $2^a - 1$ and $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 $(2^a - 1)(2^b - 1) < 2^{ab} - 1$, so we have another factor, $c$.

So, $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.

4. 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!

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, $n$, then we can ALWAYS factor an expression of the form:
$a^n - b^n$. For example, for $n=3$, we have:
$a^3 - b^3 = (a - b)(a^2 + ab + 1)$. In general, we have:
$a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + ... + ab^{n-2} + b^{n-1})$.
Notice the term $(a - b)$ is always there.

Since you said your primes $a, b$ are odd (since they aren't 2), then your expression:
$2^{ab} - 1$ is of the form $a^n - b^n$. So basically I have factored it in two ways, yielding two distinct factors:
$2^a - 1$ and $2^b - 1$. The polynomial I was referring to was simply:
$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 $a,b\neq 2$. Show that $2^{ab}-1$ has at least three different prime divisors.
The above comments show that $2^{ab}-1$ has at least three (prime) factors. But the question is asking for something much stronger than that, namely that $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!