Turn on thread page Beta
    • Thread Starter
    Offline

    1
    ReputationRep:
    Question: 3^n - 1 is a prime number for which values of n (n is a natural number)?


    Don't want the answer but any advice on how to start/think about it? Cheers.
    Offline

    12
    ReputationRep:
    Notice that 3^n - 1 is always even (3^n is always odd, and an odd number minus one is even). How many even primes are there?
    • Thread Starter
    Offline

    1
    ReputationRep:
    (Original post by GHOSH-5)
    Notice that 3^n - 1 is always even (3^n is always odd, and an odd number minus one is even). How many even primes are there?
    2 is the only even prime number..so n can only equal 1.

    Thanks.

    Btw, how did you know that - have you seen it before or have you just done loads of this sort of question?
    Offline

    15
    (Original post by eivoquraf)
    Btw, how did you know that - have you seen it before or have you just done loads of this sort of question?
    Like lots of problems in mathematics, you first need to spot a pattern or rule intuitively, and then you need to prove it.

    In this case, if you write out the first few values of the sequence (2, 8, 26, 80, 242...) you'd see that they're all even, so we can conjecture that "3^n - 1 is always even". Then, we must prove our conjecture. In this case, we notice that 3^n must always be odd, because the product of odd numbers is odd (how would we prove this?), and hence 3^n -1 must be even. Finally, we use this fact to solve the problem, by noticing that 2 is the only even prime (why?) and hence the result that you've correctly given.

    The stage of proof is very important, as patterns you spot can sometimes be wrong. For example, the sequence for the number of pieces you can obtain from cutting a pizza in a straight line is 2, 4, 8, 16. From this, you'd probably guess that the number of pieces obtained by n cuts is 2^n, but the next number in the sequence is actually 31! (see here)
    Offline

    18
    ReputationRep:
    Are you at LSE? The most elegant proof is to just factorise it.
    • Community Assistant
    Offline

    20
    ReputationRep:
    Community Assistant
    (Original post by tommm)
    Like lots of problems in mathematics, you first need to spot a pattern or rule intuitively, and then you need to prove it.

    In this case, if you write out the first few values of the sequence (2, 8, 26, 80, 242...) you'd see that they're all even, so we can conjecture that "3^n - 1 is always even". Then, we must prove our conjecture. In this case, we notice that 3^n must always be odd, because the product of odd numbers is odd (how would we prove this?), and hence 3^n -1 must be even. Finally, we use this fact to solve the problem, by noticing that 2 is the only even prime (why?) and hence the result that you've correctly given.

    The stage of proof is very important, as patterns you spot can sometimes be wrong. For example, the sequence for the number of pieces you can obtain from cutting a pizza in a straight line is 2, 4, 8, 16. From this, you'd probably guess that the number of pieces obtained by n cuts is 2^n, but the next number in the sequence is actually 31! (see here)
    What a nice explanation. Good job.
    Offline

    14
    ReputationRep:
    (Original post by tommmFor example, the sequence for the number of pieces you can obtain from cutting a pizza in a straight line is 2, 4, 8, 16. From this, you'd probably guess that the number of pieces obtained by n cuts is [latex)
    2^n[/latex], but the next number in the sequence is actually 31! (see here)
    I was wondering how you got this result and then realised that you are making cuts that don't all go through the same point (chords, not cuts through the centre of the circle.) Fascinating.
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by jjarvis)
    I was wondering how you got this result and then realised that you are making cuts that don't all go through the same point (chords, not cuts through the centre of the circle.) Fascinating.
    Yes, Tom was talking about the maximum number of pieces you can get from making cuts - if you make three cuts and they all go through one point then you only get 6 pieces, but the maximum is 7.
    Offline

    14
    ReputationRep:
    (Original post by generalebriety)
    Yes, Tom was talking about the maximum number of pieces you can get from making cuts - if you make three cuts and they all go through one point then you only get 6 pieces, but the maximum is 7.
    Cool stuff. Always found maths interesting, and I wasn't *bad* at it per se, it's just there were other subjects I'm much *better* at.

    The general trend of innumeracy is just embarassing. No one acts as though it were ok not to be able to read, but people feel comfortable saying, "oh, I can't do numbers for toffee".
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by jjarvis)
    Cool stuff. Always found maths interesting, and I wasn't *bad* at it per se, it's just there were other subjects I'm much *better* at.

    The general trend of innumeracy is just embarassing. No one acts as though it were ok not to be able to read, but people feel comfortable saying, "oh, I can't do numbers for toffee".
    Yeah, I think Ben Green said a very similar thing a couple of years back. And I agree. Though most people are rubbish at some things, and maths is hard, so it only makes sense (I grudgingly admit).
    Offline

    12
    ReputationRep:
    x^n - 1 is always composite for fixed x: try writing this number in base x to see why.

    (it does also factorise)
    Offline

    12
    ReputationRep:
    (Original post by around)
    x^n - 1 is always composite for fixed n: try writing this number in base x to see why.

    (it does also factorise)
    You must have heard of Mersenne primes?
    Offline

    12
    ReputationRep:
    I'm sorry, I meant fixed x. Changed my post accordingly.
    Offline

    16
    ReputationRep:
    (Original post by Swayum)
    Are you at LSE? The most elegant proof is to just factorise it.
    not really. factorising is a massive hassle whereas 3^n=2k+1 so 3^n-1=2k for some k => it's even.... is much nicer i think.
    Offline

    10
    ReputationRep:
    Well, there's a easy factorisation for numbers of the form a^n - 1, namely (a - 1)(a^{n-1} + a^{n-2} + \cdots + a + 1)...
    Offline

    16
    ReputationRep:
    (Original post by Zhen Lin)
    Well, there's a easy factorisation for numbers of the form a^n - 1, namely (a - 1)(a^{n-1} + a^{n-2} + \cdots + a + 1)...
    ok. but that still requires more writing.
    Offline

    18
    ReputationRep:
    (Original post by Totally Tom)
    3^n=2k+1
    It's ridiculously obvious that that's true, but you haven't actually proven that 3^n can always be written as 2k + 1, have you (i.e. you'd have to prove that the product of two odd numbers is always odd first)? Proving it would be far more hassley compared with my suggestion of factorising it like Zhen Lin did.
    Offline

    12
    ReputationRep:
    (Original post by Swayum)
    It's ridiculously obvious that that's true, but you haven't actually proven that 3^n can always be written as 2k + 1, have you (i.e. you'd have to prove that the product of two odd numbers is always odd first)? Proving it would be far more hassley compared with my suggestion of factorising it like Zhen Lin did.
    It's not really a big hassle; just proving that an odd times an odd is still odd, essentially. Or you can be ultra-slippery by considering 3^n (mod 2) :awesome:
    Offline

    18
    ReputationRep:
    (Original post by GHOSH-5)
    It's not really a big hassle; just proving that an odd times an odd is still odd, essentially. Or you can be ultra-slippery by considering 3^n (mod 2) :awesome:
    Do you genuinely believe that that's easier/faster than just factorising?
    Offline

    12
    ReputationRep:
    (Original post by Swayum)
    Do you genuinely believe that that's easier/faster than just factorising?
    I don't think it's much slower. Regardless, both ways are elegant enough for no-one to care a huge amount which way you're going.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: October 11, 2009

University open days

  • University of Roehampton
    All departments Undergraduate
    Sat, 17 Nov '18
  • Edge Hill University
    Faculty of Health and Social Care Undergraduate
    Sat, 17 Nov '18
  • Bournemouth University
    Undergraduate Open Day Undergraduate
    Sat, 17 Nov '18
Poll
Black Friday: Yay or Nay?
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

Equations

Best calculators for A level Maths

Tips on which model to get

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

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

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