Results 1 to 6 of 6

Thread: Prime factors

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    41

    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?
    Last edited by Glyper; Nov 28th 2010 at 02:07 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2010
    Posts
    4
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

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

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    10
    Nice proof!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2010
    Posts
    41
    Wow.. thank you very much! I have some questions, though:

    Quote Originally Posted by melese View Post
    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 View Post
    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 View Post
    We leave out the (simple) case $\displaystyle 2^{pq}-1=(2^p-1)(2^q-1)$.
    Why?

    Quote Originally Posted by melese View Post
    Thus $\displaystyle a\geq3$. This contradicts the fact that $\displaystyle a<3$.
    So the contradiction shows the veracity of the problem description?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Reply

    Thanks for asking,

    Quote Originally Posted by Glyper View Post
    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$.


    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?
    Short answer: Yes.
    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.


    3. Why?
    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$.)


    4. So the contradiction shows the veracity of the problem description
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime factors
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Nov 20th 2010, 04:57 AM
  2. Replies: 1
    Last Post: Dec 7th 2009, 10:42 AM
  3. prime factors
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 30th 2008, 07:40 AM
  4. prime factors
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Aug 24th 2008, 02:17 AM
  5. prime factors
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Aug 26th 2007, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum