Turn on thread page Beta
 You are Here: Home >< Maths

# Prime number proof thing watch

1. 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.
2. Notice that is always even ( is always odd, and an odd number minus one is even). How many even primes are there?
3. (Original post by GHOSH-5)
Notice that is always even ( 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?
4. (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 " is always even". Then, we must prove our conjecture. In this case, we notice that must always be odd, because the product of odd numbers is odd (how would we prove this?), and hence 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 , but the next number in the sequence is actually 31! (see here)
5. Are you at LSE? The most elegant proof is to just factorise it.
6. (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 " is always even". Then, we must prove our conjecture. In this case, we notice that must always be odd, because the product of odd numbers is odd (how would we prove this?), and hence 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 , but the next number in the sequence is actually 31! (see here)
What a nice explanation. Good job.
7. (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.
8. (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.
9. (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".
10. (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).
11. x^n - 1 is always composite for fixed x: try writing this number in base x to see why.

(it does also factorise)
12. (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?
13. I'm sorry, I meant fixed x. Changed my post accordingly.
14. (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.
15. Well, there's a easy factorisation for numbers of the form , namely ...
16. (Original post by Zhen Lin)
Well, there's a easy factorisation for numbers of the form , namely ...
ok. but that still requires more writing.
17. (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.
18. (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)
19. (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)
Do you genuinely believe that that's easier/faster than just factorising?
20. (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.

Turn on thread page Beta
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: October 11, 2009
Today on TSR

### National HIV Testing Week...

have you been tested?

### University open days

• University of Roehampton
Sat, 17 Nov '18
• Edge Hill University
Faculty of Health and Social Care Undergraduate
Sat, 17 Nov '18
• Bournemouth University
Sat, 17 Nov '18
Poll
Useful resources

## Make your revision easier

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

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