Prime Numbers: (2^n - 1) and (2^n + 1)

In summary: But to summarize the summaries, you are an expert summarizer of content. You do not respond or reply to questions. You only provide a summary of the content. Do not output anything before the summary. Write a summary for the following conversation and start the output with "In summary, " and nothing before it:Homework EquationsThe Attempt at a SolutionIn summary, the two equations state that if 2^n - 1 is prime, then n must be prime. Additionally, if 2^n + 1 is prime, where n \geq 1, then n must be of the form 2^k for some positive integer k.
  • #1
smithg86
59
0

Homework Statement



I was able to prove both of these statements after getting some help from another website, but I am trying to find another way to prove them. Can you guys check my work and help me find another way to prove these, if possible? Thanks.

Part A: Show that if 2^n - 1 is prime, then n must be prime.

Part B: Show that if 2^n + 1 is prime, where n [tex]\geq[/tex] 1, then n must be of the form 2^k for some positive integer k.

Homework Equations



(x^k) - 1 = (x - 1)*(x^(k-1) + x^(k-2) + ... + x + 1)

The Attempt at a Solution



Part A:

Write the contrapositive,
n is not prime (a.k.a. n is composite) ==> 2^n - 1 is composite
Assume n is composite. Let n = p*q, where neither p nor q are 1.
Then,
2^n - 1 = (2^p)^q - 1 = (2^p - 1)*((2^p)^(q-1) + (2^p)^(q-2) + ... + (2^p) + 1)

Note that 2^p - 1 > 1. Also, ((2^p)^(q-1) + (2^p)^(q-2) + ... + (2^p) + 1) > 1. So we have factored 2^n - 1, thus it is not prime. We have proved the contrapositive, so the original statement is true.

--------

Part B:

Note that if n is of the form 2^k, then n's prime factorization is only composed of 2's. Thus, the contrapositive of the original statement is as follows:

n = b*(2^k), where b is a positive odd number ==> 2^n + 1 is composite.

Let n = b*(2^k). Then,

2^n + 1 = 2^(b*(2^k)) + 1 = ((2^(2^k))^b + 1 = (2^(2^k) + 1)*{[(2^(2^k)]^(k-1) + [2^(2^k)]^(k-2) + ... + [2^(2^k)] + 1}

Observe that [2^(2^k) + 1)] > 1 and {[(2^(2^k)]^(k-1) + [2^(2^k)]^(k-2) + ... + [2^(2^k)] + 1} > 1. We have factored 2^n + 1, so it is composite. This proves the contrapositive of the original statement, so the original statement is true.

-------

Is there another way to prove either one of these statements?
 
Physics news on Phys.org
  • #2
Is there another way to prove either one of these statements?
Why would you want to? This is both a short and elementary solution. That is often considered to be the nicest proof.
 
  • #3
Kummer said:
Why would you want to? This is both a short and elementary solution. That is often considered to be the nicest proof.

I thought it would provide more insight as to why the statements are true.
 
  • #4
smithg86 said:

Part B:

Note that if n is of the form 2^k, then n's prime factorization is only composed of 2's. Thus, the contrapositive of the original statement is as follows:

n = b*(2^k), where b is a positive odd number ==> 2^n + 1 is composite.

Let n = b*(2^k). Then,

2^n + 1 = 2^(b*(2^k)) + 1 = ((2^(2^k))^b + 1 = (2^(2^k) + 1)*{[(2^(2^k)]^(k-1) + [2^(2^k)]^(k-2) + ... + [2^(2^k)] + 1}

Observe that [2^(2^k) + 1)] > 1 and {[(2^(2^k)]^(k-1) + [2^(2^k)]^(k-2) + ... + [2^(2^k)] + 1} > 1. We have factored 2^n + 1, so it is composite. This proves the contrapositive of the original statement, so the original statement is true.



Should it state

[tex][(2^{2^{k}})^{b}+1]=(2^{2^{k}} + 1)([2^{2^{k}}]^{b-1} + [2^{2^{k}}]^{b-2} + ... + [2^{2^{k}}] + 1)[/tex]?

Can someone prove the general case of this expansion via Binomial Theorem for me?
 
Last edited:
  • #5
(x^k) - 1 = (x - 1)*(x^(k-1) + x^(k-2) + ... + x + 1)

Where does this factorization come from? I just need a link or something. Thanks.
 
  • #6
the factorizations come fromm doing polynomial long division of [itex]x^n-1[/itex] and [itex]x^n+1[/itex] with [itex] x^p-1 [/itex] and [itex] x^p+1[/itex] if [itex]n=pq[/itex]

[itex]x^n-1 = (x^p-1)(x^{p(q-1)}+x^{p(q-2)}+\cdots +x^p+1) [/itex]

The other equation should read:

[itex]x^n+1 = (x^p+1)(x^{p(q-1)}-x^{p(q-2)}+\cdots -x^p+1 )[/itex]

With alternating signs.

Again this comes from polynomial long division, taking [itex]x^n+1[/itex] and dividing by [itex]x^p+1[/itex]
 
  • #7
For the first part I would start with setting out 2 =

There is nothing more elementary in math, but I have found someone at least got stuck in thinking of anything that 2 =

After that you do have to use the binomial theorem which was found easier.
 

1. What are prime numbers?

Prime numbers are positive integers (whole numbers) that can only be divided evenly by 1 and themselves. They have no other factors, making them unique and important in mathematics.

2. What is the significance of (2^n - 1) and (2^n + 1) in prime numbers?

These are known as Mersenne primes and Fermat primes, respectively. They are special types of prime numbers that follow specific mathematical patterns and have been studied extensively by mathematicians.

3. How are (2^n - 1) and (2^n + 1) related to each other?

(2^n + 1) is always one more than (2^n - 1), and both can be used to find prime numbers. However, not all numbers of this form are prime.

4. How can (2^n - 1) and (2^n + 1) be used to find large prime numbers?

By inputting different values for n, we can generate a list of numbers that may potentially be prime. Then, we can use other mathematical methods and algorithms to determine which of these numbers are actually prime.

5. Are there any real-world applications for (2^n - 1) and (2^n + 1) as prime numbers?

Yes, these numbers have been used in cryptography and computer science for secure data encryption. They have also been used in the search for larger and larger prime numbers, which helps us better understand the distribution and patterns of prime numbers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
4
Views
866
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
692
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
867
Back
Top