Want to identify that a number is prime

[i.mehrzad]

Well i read this somewhere that most prime numbers will give a whole number when equated with the formulae 6n+/-1(plus or minus)
Is there any proof for this or is it just a coincidence.

 

[DeadWolfe]

Well you are saying that most prime numbers are of the form 6n+1 or 6n+5 for some n.

Well, note that all numbers can be written as 6n+m for some n, and some m between 0 and 5. So all we are claiming is that m cannot be any number other than 1 or 5. This can be seen simply by checking cases.

p=6n+0 would imply p is a multiple of 6, so not prime
p=6n+2=2(3n+1) implies p is even, so not prime unless p is 2
p=6n+3=3(2n+1) implies p is a multiple of 3, and so prime only when p=3.
p=6n+4=2(3n+2) implies p is even.

 

[Gib Z]

On from DeadWolfe's post, that doesn't end up telling you that the number is actually prime though. It just rules out that 2 and 3 are not factors, which indeed rules out a lot of numbers, but isn't actually very effective. ie 35 = 6*(5) + 5. However 35 is not prime, 5*7.

 

[Werg22]

There can't be any known way for the simple reason that if there was one, Euclid's proof of the infinity of prime numbers wouldn't be the only one, as it is now.

 

[DeadWolfe]

There can't be any known way for the simple reason that if there was one, Euclid's proof of the infinity of prime numbers wouldn't be the only one, as it is now.

What are you saying? There is no way to tell whether a number is prime? Obviously there are methods (we can all think of at least one)

Furthermore, I don't understand how this would relate to proofs of the infinitude of primes, but there are many known proofs of this fact.

 

[Werg22]

Are there? Admittedly I was venturing myself a bit so the argument probably doesn't hold. Though, I am skeptical whether that there is a general way to verify that a number is prime. If there was, it would be simple to construct prime numbers, something that I doubt is possible.

 

[DeadWolfe]

Of course there is: to test p is prime, check all the numbers less than sqrt(p) and make sure none of them divide p. Of course, this does indeed yield a method for constructing primes, called the sieve Eratosthenes, and it has been known for thousands of years. Of course it isn't very effective...

 

[Werg22]

Sieve of Eratosthenes you say? I was unaware of that, I'll look into it.

 

[Gib Z]

Not to mention I can think of a few proofs for the infintitude of the primes, my favorite being Euler's which shows $$\sum \frac{1}{p}$$ diverges, which of course it can't unless there are infinite p.

 

[ktoz]

Not to mention I can think of a few proofs for the infintitude of the primes, my favorite being Euler's which shows $$\sum \frac{1}{p}$$ diverges, which of course it can't unless there are infinite p.

Since that's from Euler, it's undoubtedly correct, but I don't follow the logic. If p = {1, 2, 3, ... 2^1000} rather than primes, that would also diverge but it has an explicit upper bound. How do you get from a diverging sum to proof of infinitude?

 

[d_leet]

Since that's from Euler, it's undoubtedly correct, but I don't follow the logic. If p = {1, 2, 3, ... 2^1000} rather than primes, that would also diverge but it has an explicit upper bound. How do you get from a diverging sum to proof of infinitude?

If p belongs to any set of numbers let's call it P, it is fairly obvious that if P is finite then the sum of all 1/p converges because this is a finite sum of finite numbers. This statement is equivalent to( the contrapositive of) the statement that if the sum of all 1/p diverges then P is infinite.

 

[Gib Z]

Umm if they example serious you gave where p = 1,2,3,4,5,... then it diverges if that sequence has an infinite number of terms. However if it has a finite number implied by your 2^1000, then it actually converges.

 

[ktoz]

Umm if they example serious you gave where p = 1,2,3,4,5,... then it diverges if that sequence has an infinite number of terms. However if it has a finite number implied by your 2^1000, then it actually converges.

I guess I was thinking it diverges because

$$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} < \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}$$

and that adding each subsequent 1/n would produce a greater sum than the last, thus divergence. That's not what you mean by divergence though I suspect.

 

[ktoz]

If p belongs to any set of numbers let's call it P, it is fairly obvious that if P is finite then the sum of all 1/p converges because this is a finite sum of finite numbers. This statement is equivalent to( the contrapositive of) the statement that if the sum of all 1/p diverges then P is infinite.

OK. That makes sense. Thanks

 

[JohnDuck]

Since that's from Euler, it's undoubtedly correct, but I don't follow the logic. If p = {1, 2, 3, ... 2^1000} rather than primes, that would also diverge but it has an explicit upper bound. How do you get from a diverging sum to proof of infinitude?

Remember that a series is said to converge if the limit of the sequence of it's partial sums converges. In the case:

$$\sum_{a\in A}\frac{1}{a}$$

Where A is finite (i.e., |A| = some natural number n), the series of partial sums converges exactly to nth partial sum. Intuitively, what could the (n+1)th partial sum possibly be? If it was anything other than the nth partial sum, it would seem to indicate that |A|> n, which would violate our hypothesis. Since A is finite implies this series is convergent, then the contrapositive must also be true--if this series is divergent, then A is infinite.

Of course this doesn't actually prove that this series is divergent when A is the set of prime numbers. Just that if it is divergent, then there must be infinite number of prime numbers.

Edit: Looks like I was beaten to the punch.