Results 1 to 6 of 6

Math Help - Divisors

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    12

    Divisors

    Prove, that a composite number 2^p - 1 (where p is a prime) has at least 2 different prime factors.

    How I tried to solve this problem:
    I tried to write 2^p -1 as x^n (x, n are integers, n>1, just to prove that it can't be this way). I know that the only prime factors of 2^p - 1 can be numbers like 2kp+1 and I also tried this way. What is more, I tried with two cases- n odd and n even, separately. But I didn't manage to prove anything. Please, help. Thank you in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    x^n-1=(x-1)*(x^{n-1}+x^{n-2}+...+x+1)

    EDIT: NOT HELPING TOO MUCH.

    What about p=31?

    2^31 - 1 is prime.
    Last edited by Also sprach Zarathustra; November 20th 2010 at 06:41 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2010
    Posts
    12
    Yes, but in my question if you have an equation x^n-1=(x-1)*(x^{n-1}+x^{n-2}+...+x+1) then x=2 and we have to prove that (x^{n-1}+x^{n-2}+...+x+1) has at least 2 prime factors. How?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by conrad View Post
    Prove, that a composite number 2^p - 1 (where p is a prime) has at least 2 different prime factors.

    How I tried to solve this problem:
    I tried to write 2^p -1 as x^n (x, n are integers, n>1, just to prove that it can't be this way). I know that the only prime factors of 2^p - 1 can be numbers like 2kp+1 and I also tried this way. What is more, I tried with two cases- n odd and n even, separately. But I didn't manage to prove anything. Please, help. Thank you in advance.
    I'll try to show a more general result: Let n, a and m be positive integers. If 2^n-1=a^m, then 2^n-1=a. To put it differently, m must equal 1. (execpt for the case n=1 , where 2^1-1=1^m)

    We suppose that n\geq2. It's clear that a is odd.
    If m is even, then a^m would be of the form 4k+1 . But 2^n-1 has the form 4q+3 ; therefore m is odd.*

    The following identity holds, since m is odd: a^m+1=(a+1)(a^{m-1}-a^{m-2}+\cdots+a^2-a+1)=2^n. Note that the term a^{m-1}-a^{m-2}+\cdots+a^2-a+1 is odd and thus relatively prime to 2^n . So 2^n must be equal to a+1 , namely a=2^n-1.

    Back to the original problem... Assume to the contrary that 2^p-1 has only one prime factor, that is 2^p-1=q^m, where q is prime. But the result implies that 2^p-1=q, contradiction.


    * To see why: For any odd a we have a\equiv\pm1\pmod4. Then a^m\equiv1\pmod4 if m is even. But 2^n-1\equiv-1\pmod4, so 1\equiv-1\pmod4, contradiction. Sorry if this part is tedious...
    Last edited by melese; November 20th 2010 at 09:26 AM. Reason: redundant words
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2010
    Posts
    12
    Thank you! You helped me so much. I'm very grateful!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2010
    Posts
    12
    @melese, maybe you have and idea how to solve this one:
    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..

    Thank you very much in advance!
    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