# Prime factors

• Nov 27th 2010, 02:53 AM
Glyper
Prime factors
There are given different odd prime numbers $\displaystyle p$ and $\displaystyle q$. Prove that number $\displaystyle 2^{pq} -1$ has at least 3 different prime factors.

From what I found in an algebra book:
$\displaystyle 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:
. . $\displaystyle (2^p)^q \,-\,1^q \;=\;(2^p\,-\,1)\left([2^p]^{q-1}\,+\,[2^p]^{q-2}\,+\,\cdots\,+[2^p]\,+\,1\right)$

. . $\displaystyle (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?
• Nov 27th 2010, 03:04 AM
francois
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
• Nov 27th 2010, 08:40 AM
melese
Possible solution.
Let $\displaystyle p$ and $\displaystyle q$ be distinct primes ($\displaystyle q>p)$. Then $\displaystyle 2^{pq}-1$ has at least three different prime divisors.

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

Both $\displaystyle 2^p-1$ and $\displaystyle 2^q-1$ divide $\displaystyle 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 $\displaystyle 2^{pq}-1$ are $\displaystyle 2^p-1$ and $\displaystyle 2^q-1$. Thus $\displaystyle 2^{pq}-1=(2^p-1)^a(2^q-1)^b$, where $\displaystyle a,b$ are positive integers.

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

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

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

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

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

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

I think/hope this is correct..., anybody?
• Nov 27th 2010, 10:14 AM
Opalg
Nice proof! (Happy)
• Nov 28th 2010, 02:07 AM
Glyper
Wow.. thank you very much! I have some questions, though:

Quote:

Originally Posted by melese
We show that $\displaystyle a\geq2$ implies $\displaystyle q=2^p-1$.

What do you mean by "implies"? That only for $\displaystyle a\geq2$ the $\displaystyle q=2^p-1$ can be true?

Quote:

Originally Posted by melese
If $\displaystyle b\geq2$, we use the same reasoning to show that $\displaystyle 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?

Quote:

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

Why?

Quote:

Originally Posted by melese
Thus $\displaystyle a\geq3$. This contradicts the fact that $\displaystyle a<3$.

So the contradiction shows the veracity of the problem description?
• Nov 28th 2010, 06:43 AM
melese

Quote:

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

By the satement "$\displaystyle a\geq2$ implies $\displaystyle q=2^p-1$", I meant: If $\displaystyle a\geq2$, then $\displaystyle q=2^p-1$.
In other words: $\displaystyle a\geq2$ leads to the conclusion that $\displaystyle q=2^p-1$.

Quote:

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 $\displaystyle b\geq2$ and then the divisibility $\displaystyle (2^q-1)^2|2^{pq}-1$ takes place. With this in mind, it's clear that you'll get $\displaystyle 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 $\displaystyle 2^{pq}-1=(2^p-1)(2^q-1)$ cannot be. (Here, $\displaystyle a=b=1$.)
You'll see that eventually it's sufficient to consider $\displaystyle 2^{pq}-1=(2^p-1)^a(2^q-1)$ with $\displaystyle a\geq2$ and $\displaystyle q=2^p-1$. This assumption leads us to the absurdity: $\displaystyle a<3$ and $\displaystyle a\geq3$. So yes.