You are Here: Home >< Maths

# Primes. Watch

1. Show that, if is prime with , and is prime.
I have absolutely no idea where to start, any hints?
2. 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 is prime, with a,n >1.

THEN a=2 and n is prime, right?
3. (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?
4. Isn't this Fermat's Little Theorem?
5. (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 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?
6. (Original post by StephenNeill)
Edit: Actually, sorry, maybe I've jumped a little.

You're saying

IF is prime, with a,n >1.

THEN a=2 and n is prime, right?
yes.
7. (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:

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.
8. 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:

but we are given that 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 ?

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: December 3, 2010
Today on TSR

### Medicine, fastest and slowest offer senders

Have you got yours?

### You can apply to Hogwarts?!

Discussions on TSR

• Latest
• ## 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
Useful resources

### 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

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## 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

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