Results 1 to 6 of 6

Thread: 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; Nov 20th 2010 at 05: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 $\displaystyle n, a$ and $\displaystyle m $ be positive integers. If $\displaystyle 2^n-1=a^m$, then $\displaystyle 2^n-1=a$. To put it differently, $\displaystyle m $ must equal 1. (execpt for the case $\displaystyle n=1 $, where $\displaystyle 2^1-1=1^m$)

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

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

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


    * To see why: For any odd $\displaystyle a $ we have $\displaystyle a\equiv\pm1\pmod4$. Then $\displaystyle a^m\equiv1\pmod4$ if $\displaystyle m $ is even. But $\displaystyle 2^n-1\equiv-1\pmod4$, so $\displaystyle 1\equiv-1\pmod4$, contradiction. Sorry if this part is tedious...
    Last edited by melese; Nov 20th 2010 at 08: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: Nov 24th 2010, 08:40 AM
  2. divisors
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 7th 2010, 05:20 PM
  3. Zero divisors and such
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Apr 4th 2010, 07:32 PM
  4. Divisors of N
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 27th 2008, 03:36 PM
  5. divisors
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Aug 27th 2005, 12:01 AM

Search Tags


/mathhelpforum @mathhelpforum