Primes, divisibility

**atreyyu** · December 1st 2010, 10:59 AM

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?

**Matt Westwood** · December 1st 2010, 11:55 AM

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.

**elemental** · December 1st 2010, 12:46 PM

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.

**atreyyu** · December 1st 2010, 03:04 PM

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!

**elemental** · December 1st 2010, 03:33 PM

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?

**atreyyu** · December 1st 2010, 03:41 PM

Sure. Thanks a lot!

**Matt Westwood** · December 1st 2010, 09:20 PM

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.

**Opalg** · December 1st 2010, 11:44 PM

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.

**atreyyu** · December 2nd 2010, 01:02 PM

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

Thread: Primes, divisibility

LinkBack

Thread Tools

Display

Primes, divisibility

Similar Math Help Forum Discussions

primes and divisibility puzzle

primes and divisibility

primes?

Primes and divisibility

TI-83 Plus... Primes

Search Tags