Results 1 to 7 of 7

Math Help - Mersenne Primes

  1. #1
    Junior Member raheel88's Avatar
    Joined
    Apr 2010
    Posts
    31

    Mersenne Primes

    How can I prove that if a^n - 1 is prime, then a = 2 and n is prime?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by raheel88 View Post
    How can I prove that if a^n - 1 is prime, then a = 2 and n is prime?
    First note  n must be prime. Suppose  n=cd , then  a^n-1=a^{cd}-1=(a^c-1)\cdot \left(1+a^c+a^{2c}+a^{3c}+\cdots+a^{(d-1)c}\right) .

    I'll get back to you with your other question.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
    First note  n must be prime. Suppose  n=cd , then  a^n-1=a^{cd}-1=(a^c-1)\cdot \left(1+a^c+a^{2c}+a^{3c}+\cdots+a^{(d-1)c}\right) .

    I'll get back to you with your other question.
     a=2 because  a-1\mid a^n-1 . Can you see why?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member raheel88's Avatar
    Joined
    Apr 2010
    Posts
    31
    Quote Originally Posted by chiph588@ View Post
     a=2 because  a-1\mid a^n-1 . Can you see why?
    of course!

    we've already proved that a^n-1 is prime so a-1 must be equal to 1!

    thanks chiph588... I've got another problem posted that is most definitely more challenging and in your forte.

    regards
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by raheel88 View Post
    of course!

    we've already proved that a^n-1 is prime so a-1 must be equal to 1!

    thanks chiph588... I've got another problem posted that is most definitely more challenging and in your forte.

    regards
    I didn't quite follow your explanation there. My explanation is

    a \equiv 1\ (\text{mod}\ (a-1))

    Therefore a^n-1 \equiv 1^n - 1 \equiv 0\ (\text{mod}\ (a-1)).

    Edit: Never mind, I guess you weren't trying to explain that part. The wording is just a bit odd though, in terms of, we haven't proven that a^n-1 is prime, merely stating conditions for it being possible.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by undefined View Post
    I didn't quite follow your explanation there. My explanation is

    a \equiv 1\ (\text{mod}\ (a-1))

    Therefore a^n-1 \equiv 1^n - 1 \equiv 0\ (\text{mod}\ (a-1)).

    Edit: Never mind, I guess you weren't trying to explain that part.
    Another way is to observe  a^n-1 = (a-1)(a^{n-1}+a^{n-2}+\cdots+a+1) .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member raheel88's Avatar
    Joined
    Apr 2010
    Posts
    31
    Quote Originally Posted by undefined View Post
    I didn't quite follow your explanation there. My explanation is

    a \equiv 1\ (\text{mod}\ (a-1))

    Therefore a^n-1 \equiv 1^n - 1 \equiv 0\ (\text{mod}\ (a-1)).

    Edit: Never mind, I guess you weren't trying to explain that part. The wording is just a bit odd though, in terms of, we haven't proven that a^n-1 is prime, merely stating conditions for it being possible.
    yeh sorry...i meant to say that we're assuming that a^n - 1 is prime, not that we've already proven it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mersenne numbers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 14th 2010, 06:06 PM
  2. Congruence and Mersenne primes.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 11th 2010, 06:20 PM
  3. Mersenne numbers
    Posted in the Number Theory Forum
    Replies: 26
    Last Post: April 22nd 2009, 03:19 PM
  4. Mersenne prime
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: January 17th 2009, 01:16 PM
  5. mersenne primes
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2007, 05:25 AM

Search Tags


/mathhelpforum @mathhelpforum