Results 1 to 9 of 9

Math Help - Divisors again

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    12

    Divisors again

    We have:
    z = (2^(mn) - 1)/[(2^m - 1)(2^n - 1)], where (2^m - 1) and (2^n - 1) are prime numbers.
    Prove that (2^m - 1) and (2^n - 1) are not the only prime factors of z.

    I tried to solve it writing z = (2^m - 1)^a * (2^n - 1)^b and proving that it is not correct. But I don't know how. I also noticed that it would be sufficient to prove that 2^(mn) - 1 can't be written as ((2^m - 1)^x * (2^n - 1)^y but I also have no idea how to prove it. I tried with comparing highest exponents, but nothing..
    It will be fantastic if you help me with proving this fact.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by conrad View Post
    We have:
    z = (2^(mn) - 1)/[(2^m - 1)(2^n - 1)], where (2^m - 1) and (2^n - 1) are prime numbers.
    Prove that (2^m - 1) and (2^n - 1) are not the only prime factors of z.

    I tried to solve it writing z = (2^m - 1)^a * (2^n - 1)^b and proving that it is not correct. But I don't know how. I also noticed that it would be sufficient to prove that 2^(mn) - 1 can't be written as ((2^m - 1)^x * (2^n - 1)^y but I also have no idea how to prove it. I tried with comparing highest exponents, but nothing..
    It will be fantastic if you help me with proving this fact.
    Hint: See melese's comment #4 in this thread, and think what happens mod 4.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2010
    Posts
    12
    Well, I don't really know what you mean.. I guess we can prove that one of those numbers: x and y is odd and another is even. But, what next?
    Last edited by conrad; November 20th 2010 at 03:08 PM.
    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
    My previous comment was based on a misreading of the question. Ignore it.

    However, the question as stated is plain wrong (unless I'm still misreading it):
    We have: z = (2^{mn} - 1)/[(2^m - 1)(2^n - 1)], where (2^m - 1) and (2^n - 1) are prime numbers. Prove that (2^m - 1) and (2^n - 1) are not the only prime factors of z.
    Try taking m=2 and n=3. Then z = \frac{2^6 - 1}{(2^2 - 1)(2^3 - 1)} = \frac{63}{3\times7} = 3. The only prime factor of z is 3, which is 2^m-1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2010
    Posts
    12

    mistake

    Oh, I'm sorry. Now I realised that I should have written: (2^m -1) and (2^n -1) are two different ODD primes.
    But my question still remains the same.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Here's an approach that seems to work. Look at the polynomial x^{2k+1}-1, and let p(x^2) be a nonconstant polynomial in x^2. Let q(x) be the quotient, and r(x) the remainder, when x^{2k+1}-1 is divided by p(x^2). I claim that if q(x) is nonzero then it consists entirely of odd powers of x. Reason: suppose not, let 2s be the highest even degree of a nonzero term in q(x), and let 2t be the degree of p(x^2). Then there is a nonzero term of degree 2(s+t) in their product (and there is no term of that degree in r(x)). But there is no term of that degree in x^{2k+1}-1, so we have a contradiction.

    Therefore p(x)q(x) consists entirely of terms of odd degree, and it follows that the constant term in r(x) must be 1.

    Now let m, n be odd numbers, and suppose that 2^m-1 is a repeated factor of 2^{mn}-1. Notice that (2^m-1)^2 = 2^{2m}- 2^{m+1}+1. Since both those powers of 2 are even, that is a polynomial in 2^2. So let p(x) = x^m-x^{(m+1)/2}+1, divide x^{mn}-1 by p(x^2) and then put x=2. The above result says that the remainder will be r(2), and r(2) must be an odd number (since the constant term in r(x) will be the only odd term). In particular r(2) can never be 0.

    Conclusion: 2^m-1, and similarly 2^n-1, can never be repeated factors of 2^{mn}-1. And since their product can never be equal to 2^{mn}-1, there must always be a third factor.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2010
    Posts
    12
    Quote Originally Posted by Opalg View Post
    Conclusion: 2^m-1, and similarly 2^n-1, can never be repeated factors of 2^{mn}-1. And since their product can never be equal to 2^{mn}-1, there must always be a third factor.
    But, well, if we try with m=3, n=7, then 2^m -1 = 7 and 2^mn -1 = 2^21 -1 = 2 097 151 = 49 * 42799. So 2^m - 1 is a double factor. I think it would be enough to prove that 2^m - 1 can't be a triple factor. How?
    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 conrad View Post
    But, well, if we try with m=3, n=7, then 2^m -1 = 7 and 2^mn -1 = 2^21 -1 = 2 097 151 = 49 * 42799. So 2^m - 1 is a double factor. I think it would be enough to prove that 2^m - 1 can't be a triple factor. How?
    Rats! I had to work through that example carefully to see why my argument breaks down. I don't have any other ideas on this at the moment.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Nov 2010
    Posts
    12
    Well, you know I'm just trying to solve following problem found in the other thread: http://www.mathhelpforum.com/math-he...rs-155363.html
    I try to prove that 2^mn - 1 (where m and n are two different odd primes) has at least 3 different prime factors. I already know about two of them that are quite obvious - 2^m -1 and 2^n -1. I can prove this statement when at least one of numbers 2^m - 1 and 2^n -1 is composite. I've got a problem when both are primes, I don't know how to solve it.
    Or maybe I should try for example with Euler's theorem or Fermat's little theorem? I don't know... Please, help me with this problem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relitivly prime, unique divisors of divisors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 24th 2010, 09:40 AM
  2. divisors
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 7th 2010, 06:20 PM
  3. Zero divisors and such
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 4th 2010, 08:32 PM
  4. Divisors of N
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 04:36 PM
  5. divisors
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 27th 2005, 01:01 AM

Search Tags


/mathhelpforum @mathhelpforum