Results 1 to 9 of 9

Thread: Primes, divisibility

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    91

    Primes, divisibility

    Given are two different primes $\displaystyle a,b\neq 2$. Show that $\displaystyle 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
    MHF Contributor Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    1,281
    Thanks
    197
    Think about the formula for a geometric progression:

    $\displaystyle 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; Dec 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
    69
    Let's factor.

    $\displaystyle 2^{ab} - 1 = (2^a)^b - 1^b = (2^a - 1)(f(a,b))$

    AND

    $\displaystyle 2^{ab} - 1 = (2^b)^a - 1^a = (2^b - 1)(f(b,a))$

    $\displaystyle f(x,y)$ is an integral polynomial.

    So, $\displaystyle 2^a - 1$ and $\displaystyle 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 $\displaystyle (2^a - 1)(2^b - 1) < 2^{ab} - 1$, so we have another factor, $\displaystyle c$.

    So, $\displaystyle 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; Dec 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
    69
    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, $\displaystyle n$, then we can ALWAYS factor an expression of the form:
    $\displaystyle a^n - b^n$. For example, for $\displaystyle n=3$, we have:
    $\displaystyle a^3 - b^3 = (a - b)(a^2 + ab + 1)$. In general, we have:
    $\displaystyle a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + ... + ab^{n-2} + b^{n-1})$.
    Notice the term $\displaystyle (a - b)$ is always there.

    Since you said your primes $\displaystyle a, b$ are odd (since they aren't 2), then your expression:
    $\displaystyle 2^{ab} - 1$ is of the form $\displaystyle a^n - b^n$. So basically I have factored it in two ways, yielding two distinct factors:
    $\displaystyle 2^a - 1$ and $\displaystyle 2^b - 1$. The polynomial I was referring to was simply:
    $\displaystyle 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
    MHF Contributor Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    1,281
    Thanks
    197
    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
    10
    Quote Originally Posted by atreyyu View Post
    Given are two different primes $\displaystyle a,b\neq 2$. Show that $\displaystyle 2^{ab}-1$ has at least three different prime divisors.
    The above comments show that $\displaystyle 2^{ab}-1$ has at least three (prime) factors. But the question is asking for something much stronger than that, namely that $\displaystyle 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: Mar 31st 2010, 12:33 PM
  2. primes and divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 31st 2010, 09:34 AM
  3. primes?
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Jan 13th 2010, 06:37 PM
  4. Primes and divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 11th 2009, 06:51 PM
  5. TI-83 Plus... Primes
    Posted in the Calculators Forum
    Replies: 8
    Last Post: Feb 3rd 2009, 08:36 AM

Search Tags


/mathhelpforum @mathhelpforum