Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    0
    ReputationRep:
    Show that, if a^n-1 is prime with a,n>1, a=2 and n is prime.
    I have absolutely no idea where to start, any hints?
    Offline

    0
    ReputationRep:
    There are lots of ways to prove it, it's a very famous theorem.

    What kind of level are you at? Where is the question asked?
    Have you done any group theory yet?

    Edit: Actually, sorry, maybe I've jumped a little.

    You're saying

    IF  a^n -1 is prime, with a,n >1.

    THEN a=2 and n is prime, right?
    • Thread Starter
    Offline

    0
    ReputationRep:
    (Original post by StephenNeill)
    There are lots of ways to prove it, it's a very famous theorem.

    What kind of level are you at? Where is the question asked?
    Have you done any group theory yet?
    It's from a Cambridge interview test. I don't know any group theory yet. Any hints?
    Offline

    17
    ReputationRep:
    Isn't this Fermat's Little Theorem?
    Offline

    2
    ReputationRep:
    (Original post by StephenNeill)
    There are lots of ways to prove it, it's a very famous theorem.

    What kind of level are you at? Where is the question asked?
    Have you done any group theory yet?

    Edit: Actually, sorry, maybe I've jumped a little.

    You're saying

    IF  a^n -1 is prime, with a,n >1.

    THEN a=2 and n is prime, right?
    So does it work? Surely backwards that must be an incredible tool for finding large primes?
    • Thread Starter
    Offline

    0
    ReputationRep:
    (Original post by StephenNeill)
    Edit: Actually, sorry, maybe I've jumped a little.

    You're saying

    IF  a^n -1 is prime, with a,n >1.

    THEN a=2 and n is prime, right?
    yes.
    Offline

    0
    ReputationRep:
    (Original post by Noble.)
    Isn't this Fermat's Little Theorem?
    This is what I first thought, but then edited because I'm not 100% sure. I think it is, it looks very similar. Someone confirm this?

    This is related to Mersenne Primes though, which are primes of the form 2^k-1. The wikipedia page for them actually lists the proof for this particular theorem.

    http://en.wikipedia.org/wiki/Mersenne_prime

    Edit:

    A hint for the proof, from the wikipedia page:
    Spoiler:
    Show

    a = 1 (mod a - 1).
    Then ap = 1 (mod a - 1),
    so a^p - 1 = 0 (mod a - 1).

    Now consider divisors of a^p-1... does this give any contradictions / insights?
    Full proof on the wiki page.


    (Original post by KissMyArtichoke)
    So does it work? Surely backwards that must be an incredible tool for finding large primes?
    Yep, the biggest known prime is a Mersenne Prime: 2^(43,112,609) - 1. Note that it isn't an "if and only if", so we can't take the theorem backwards and use our new prime as n.
    Offline

    0
    ReputationRep:
    I think some people are being thrown off by the fact that this looks a lot like Fermat's Little Theorem, and thus missing another way out. The following is a factorisation of the number:

    a^n - 1 = (a-1)(a^{n-1} + ... + a +1)

    but we are given that a^n - 1 is prime and so either a - 1 = 1, or the second parenthesis is equal to 1. For the latter case however, since a, n > 1 this is impossible. So it must be that a = 2. To show n is prime, suppose for a contradiction that n = pq, with p,q > 1. Can you do anything to factorise 2^n - 1?
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    What newspaper do you read/prefer?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.