Results 1 to 6 of 6

Math Help - Prime factors

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    41

    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?
    Last edited by Glyper; November 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 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?
    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
    7
    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 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?

    Quote Originally Posted by melese View Post
    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?

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

    Quote Originally Posted by melese View Post
    Thus a\geq3. This contradicts the fact that 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 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?
    Short answer: Yes.
    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.


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


    4. So the contradiction shows the veracity of the problem description
    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.
    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: November 20th 2010, 04:57 AM
  2. Replies: 1
    Last Post: December 7th 2009, 10:42 AM
  3. prime factors
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 30th 2008, 07:40 AM
  4. prime factors
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 24th 2008, 02:17 AM
  5. prime factors
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 26th 2007, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum