Proving 'If (2^n)-1 is Prime, Then n is Prime' Using Groups

In summary, the speaker is trying to prove the statement "If (2^n)-1 is prime then n is prime" and has seen a proof using factorisation but is trying to use groups instead. They have noticed that n must be a multiple of (p-1) for some positive integer k, but this would mean n is not prime. They are looking for help or a useful theorem.
  • #1
Bleys
74
0
I was trying to prove the statement "If (2^n)-1 is prime then n is prime". I've already seen the proof using factorisation of the difference of integers and getting a contradiction, but I was trying to use groups instead. I was wondering if it's possible, since I keep getting stuck.
So far I've got:
If (2^n)-1=p where p is prime then [tex]2^{n}\equiv1 mod(p)[/tex]. The group {1,2,...,p-1} is cyclic and every element has order p-1. So n = k(p-1) for some positive integer k. But doesn't this mean n is not prime? which is wrong I know. Could someone point me in the right direction or a theorem that might be useful?
 
Physics news on Phys.org
  • #2
Interesting problem... I'm not yet sure of a proof, but your statement

Bleys said:
The group {1,2,...,p-1} is cyclic and every element has order p-1.

is wrong. All you know is that every element has an order that divides p-1. (E.g. for p=7 the element 2 has order 3).
 
Last edited:

1. What is the statement "If (2^n)-1 is Prime, Then n is Prime" in terms of groups?

The statement can be written as "If the order of the group generated by 2 is a prime number, then the order of any element in that group must also be prime."

2. How is this statement proved using groups?

This statement is proved using the fact that if an element has a prime order in a group, then it must also generate a cyclic subgroup of that same order. This can be shown by using the properties of groups and their orders.

3. Can this statement be extended to other numbers besides 2?

Yes, this statement can be generalized to other numbers as well. In fact, this statement is known as the "Sophie Germain's theorem" and states that if p is a prime number and 2p+1 is also prime, then p is also prime.

4. Are there any counterexamples to this statement?

No, there are no known counterexamples to this statement. However, it has not been proven to be true for all possible values of n, so there is a possibility that there may be a counterexample in the future.

5. Why is this statement important in mathematics?

This statement has important implications in number theory and cryptography. It helps in identifying prime numbers and can also be used in the testing of primality for large numbers. Additionally, it has connections to the security of certain encryption algorithms.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
730
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
622
  • Linear and Abstract Algebra
Replies
2
Views
758
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
17
Views
4K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
841
  • Linear and Abstract Algebra
Replies
8
Views
854
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
Back
Top