Results 1 to 9 of 9

Math Help - Primes, divisibility

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    91

    Primes, divisibility

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

  2. #2
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    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.
    Last edited by Matt Westwood; December 1st 2010 at 11:57 AM. Reason: correction
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68
    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.
    Last edited by elemental; December 1st 2010 at 01:10 PM. Reason: formatting
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2008
    Posts
    91
    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68
    Quote Originally Posted by atreyyu View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2008
    Posts
    91
    Sure. Thanks a lot!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by atreyyu View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Aug 2008
    Posts
    91
    Zing, I thought that would be easier! Thanks for your input!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. primes and divisibility puzzle
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 31st 2010, 12:33 PM
  2. primes and divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 31st 2010, 09:34 AM
  3. primes?
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: January 13th 2010, 06:37 PM
  4. Primes and divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 11th 2009, 06:51 PM
  5. TI-83 Plus... Primes
    Posted in the Calculators Forum
    Replies: 8
    Last Post: February 3rd 2009, 08:36 AM

Search Tags


/mathhelpforum @mathhelpforum