# Math Help - Prime factors

1. ## Prime factors

There are given different odd prime numbers $p$ and $q$. Prove that number $2^{pq} -1$ has at least 3 different prime factors.

From what I found in an algebra book:
$a^n\,-\,b^n \;=\;(a\,-\,b)\,(a^{n-1}\,+\,a^{n-2}b\,+\,a^{n-3}b^2\,+\,\cdots\.+\,ab^{n-2}\,+\,b^{n-1})$

So maybe we can factorize this in two ways:
. . $(2^p)^q \,-\,1^q \;=\;(2^p\,-\,1)\left([2^p]^{q-1}\,+\,[2^p]^{q-2}\,+\,\cdots\,+[2^p]\,+\,1\right)$

. . $(2^q)^p \,-\,1^p \;=\;(2^q\,-\,1)\left([2^q]^{p-1}\,+\,[2^q]^{p-2} \,+\,\cdots\,+\,[2^q]\,+\,1\right)$

But I still don't know what to do next and if my steps were OK... Could you please help me?

2. I also tried to solve this problem. First of all look that 2^p -1 and 2^q -1 are relatively prime. Going next we must see to situations . 2^p - 1 and 2^q -1 are composite numbers(the proof is over) and the second one when 2^p - 1 and 2^q - 1 are primes. Now I don't know how to proof that the third factor is different from any power of the 2^p -1 or 2^q - 1

3. ## Possible solution.

Let $p$ and $q$ be distinct primes ( $q>p)$. Then $2^{pq}-1$ has at least three different prime divisors.

In general, $2^{st}-1=(2^s-1)\left[(2^s)^{t-1}+\cdots+(2^s)^2+(2^s)+1]$, where $t$ and $s$ are positive integers.

Both $2^p-1$ and $2^q-1$ divide $2^{pq}-1$; also they're relatively prime. If at least one of them is composite, then there's nothing to prove.

Assume that the only prime divisors of $2^{pq}-1$ are $2^p-1$ and $2^q-1$. Thus $2^{pq}-1=(2^p-1)^a(2^q-1)^b$, where $a,b$ are positive integers.

We show that $a\geq2$ implies $q=2^p-1$.
If $a\geq2$, then $(2^p-1)^2|2^{pq}-1$. But since $2^{pq}-1=(2^p-1)[(2^p)^{q-1}+\cdots+2^p+1]$, we have $2^p-1|(2^p)^{q-1}+\cdots+2^p+1$. In congruences, this translates into: $(2^p)^{q-1}+\cdots+2^p+1\equiv1+1+\cdots+1=q\equiv0\pmod{2^ p-1}$. (Note that $2^p\equiv1\pmod{2^p-1}$)
So $2^p-1|q$, but $q$ is prime, hence we must have $q=2^p-1$.

If $b\geq2$, we use the same reasoning to show that $p=2^q-1$, which is impossible. Because $p=2^q-1=1+2+\cdots+2^{q-1}>1+\cdots+1=q$, which contradicts $q>p$. So $b=1$.

We leave out the (simple) case $2^{pq}-1=(2^p-1)(2^q-1)$.
The case we consider therefore is $2^{pq}-1=(2^p-1)^a(2^q-1)$, where $q=2^p-1$, $a\geq2$. We rewrite to get $(q+1)^q-1=(2^p)^q-1=q^a\cdot(2^q-1)$.
At this point, the Binomial Theorem implies that $(1+q)^q=1+\binom{q}{1}q+\binom{q}{2}q^2+\binom{q}{ 3}q^3+\cdots=1+q^2+\frac{q(q-1)}{2}q^2+\cdots=1+q^2+q^3A$, where $A$ is some integer - to bring out the relevant form.

From the equality $(q+1)^q-1=q^a\cdot(2^q-1)$ then, we arrive at $q^2+q^3A=q^a\cdot(2^q-1)$.
$a$ must be less than 3; if not, then $q^3$ would divide $q^2$ $(=q^a(2^q-1)-q^3A)$. So $a<3$.

Divide $2^{pq}-1=(2^p-1)^a(2^q-1)$ by $2^q-1$ to get $(2^q)^{p-1}+\cdots+2^q+1=(2^p-1)^a=q^a$. From $2^q>q$ it follows that $q^a=(2^q)^{p-1}+\cdots+2^q+1>q^{p-1}+\cdots+q+1$. So, clearly, $a>p-1$; thus $a\geq p\geq3$.
Thus $a\geq3$. This contradicts the fact that $a<3$.

By the way, to see why $2^q>q$ is true, see the line that shows $2^q-1>q$.

I think/hope this is correct..., anybody?

4. Nice proof!

5. Wow.. thank you very much! I have some questions, though:

Originally Posted by melese
We show that $a\geq2$ implies $q=2^p-1$.
What do you mean by "implies"? That only for $a\geq2$ the $q=2^p-1$ can be true?

Originally Posted by melese
If $b\geq2$, we use the same reasoning to show that $p=2^q-1$, which is impossible.
So I have to rewrite the reasoning you provided above this line but with changing a to b, p to q and q to p, right?

Originally Posted by melese
We leave out the (simple) case $2^{pq}-1=(2^p-1)(2^q-1)$.
Why?

Originally Posted by melese
Thus $a\geq3$. This contradicts the fact that $a<3$.
So the contradiction shows the veracity of the problem description?

Originally Posted by Glyper
1. What do you mean by "implies"? That only for $a\geq2$ the $q=2^p-1$ can be true?
By the satement " $a\geq2$ implies $q=2^p-1$", I meant: If $a\geq2$, then $q=2^p-1$.
In other words: $a\geq2$ leads to the conclusion that $q=2^p-1$.

2. So I have to rewrite the reasoning you provided above this line but with changing a to b, p to q and q to p, right?
You assume that $b\geq2$ and then the divisibility $(2^q-1)^2|2^{pq}-1$ takes place. With this in mind, it's clear that you'll get $p=2^p-1$. Nothing special here, so there's no need to repeat the argument.
What I meant is that I skip this case, because it's not hard to show that $2^{pq}-1=(2^p-1)(2^q-1)$ cannot be. (Here, $a=b=1$.)
You'll see that eventually it's sufficient to consider $2^{pq}-1=(2^p-1)^a(2^q-1)$ with $a\geq2$ and $q=2^p-1$. This assumption leads us to the absurdity: $a<3$ and $a\geq3$. So yes.