Another algebra problem about prime and induction

In summary, to prove by induction that the n^th prime is less than 2^{2^n}, we can assume it is correct for all n \leq k and then compare p_{k+1} with p_1p_2...p_k+1. If p_{k+1} is larger than this suggested number, it can be proven to have no prime divisors, leading to a contradiction. The use of the Euclidean algorithm may be helpful in this proof.
  • #1
kntsy
82
0

Homework Statement



prove by induction that the [itex]n^{\text th}[/itex] prime is less than [itex]2^{2^{\text n}}[/itex]

Homework Equations


hint:assume it is correct for all [itex]n \leq k[/itex], and then compare [itex]p_{k+1}[/itex] with [itex]p_{1}p_{2}...p_{k}+1[/itex]

The Attempt at a Solution


is [itex]p_{k+1}[/itex] smaller/greater than [itex]p_{1}p_{2}...p_{k}+1[/itex] so that i can extend the use of inequality?
I attempt to use euclidean algorithm but do not know where to use.
Thank you.
 
Physics news on Phys.org
  • #2
If [tex]p_{k+1}[/tex] is larger than the suggested number, you should be able to prove that it has no prime divisors which is a contradiction
 

FAQ: Another algebra problem about prime and induction

What is the problem statement?

The problem states that we need to prove that for any prime number p, the sum of the first p consecutive integers is divisible by p.

How do we approach this problem?

We can use mathematical induction to prove this statement. First, we will prove that the statement is true for p = 2, then we will assume that the statement is true for some arbitrary prime number k and use that assumption to prove that it is also true for k+1.

Can you provide an example to illustrate the problem?

Sure. Let's take the case of p = 5. The first 5 consecutive integers are 1, 2, 3, 4, and 5. The sum of these integers is 15, which is divisible by 5. Therefore, our statement holds true for p = 5.

How does mathematical induction work?

Mathematical induction is a proof technique that involves proving a statement for a base case (usually the smallest possible value) and then assuming the statement is true for an arbitrary value and using that assumption to prove that it is also true for the next value.

Can you explain how the proof for this problem works?

Sure. We first prove that the statement holds true for p = 2, which is the base case. Then, we assume that the statement is true for an arbitrary prime number k. This means that the sum of the first k consecutive integers is divisible by k. Using this assumption, we can prove that the statement is also true for k+1, which completes our proof by mathematical induction.

Similar threads

Every S-composite can be expressed as a product of S-primes
Replies
13
Views
2K
Contractions of the Euclidean Group ISO(3) = E(3)
Replies
1
Views
1K
Strong Induction: Proving Every Int n>1 is a Product of Primes
Replies
5
Views
2K
Prove that the Goldbach conjecture that every even integer....
Replies
6
Views
2K
Characteristic function of the sum of random variables
Replies
6
Views
2K
Every integer greater than 5 is the sum of three primes?
Replies
4
Views
2K
Proving a formula for # of edges
Replies
8
Views
1K
Solving a Sequencing Problem: Allocating Cost Savings
Replies
1
Views
1K
Abstract Algebra Proof question
Replies
6
Views
2K
Solving a system of nonlinear equations
Replies
7
Views
2K

Hot Threads

Recent Insights

Back
Top