[help] does anyone understand Euclid theorem of infinity prime numbers?

[Kilolo]

so in this light novel I currently read, there's a mention about the MC answering the question about does prime numbers goes infinitely, and then he provide the Euclid theorem to proving that prime number is indeed goes to infinity.

but my problem is that I barely understood half of the theorem.

I do understand that :
if p = prime number then
p₁ * p₂ *... pₙ + 1 = q

then q would be either prime or a non prime number.

i understand if you're using the prime number in ascending order, that you would get

2+1=33, is prime
2×3+1=7, is prime
2×3×5+1=31, is prime
2×3×5×7+1=211, is prime
2×3×5×7×11+1=2311, is prime
and so on.

what i didn't understand is the second part, what should i do if the i use a difference sequence of the prime numbers and arrive at a non-prime number of q

for example if i use 3 * 5 + 1 = 16
then what should i do with the 16 to proof that i could make it into a prime number that's not in the list of p? (which is 3 and 5)

and yes, the first example should be enough to proof that the number of primes are infinite, but when i check wikipedia and other site everyone dictate the same thing that suggest you could do something about the non-prime number of q, my brain just couldn't make sense any of it.

can anyone giving me an example for the 2nd part which is easy to understand?

 

[Ilikewaterkusa]

so in this light novel I currently read, there's a mention about the MC answering the question about does prime numbers goes infinitely, and then he provide the Euclid theorem to proving that prime number is indeed goes to infinity.

but my problem is that I barely understood half of the theorem.

I do understand that :
if p = prime number then
p₁ * p₂ *... pₙ + 1 = q

then q would be either prime or a non prime number.

i understand if you're using the prime number in ascending order, that you would get

2+1=33, is prime
2×3+1=7, is prime
2×3×5+1=31, is prime
2×3×5×7+1=211, is prime
2×3×5×7×11+1=2311, is prime
and so on.

what i didn't understand is the second part, what should i do if the i use a difference sequence of the prime numbers and arrive at a non-prime number of q

for example if i use 3 * 5 + 1 = 16
then what should i do with the 16 to proof that i could make it into a prime number that's not in the list of p? (which is 3 and 5)

and yes, the first example should be enough to proof that the number of primes are infinite, but when i check wikipedia and other site everyone dictate the same thing that suggest you could do something about the non-prime number of q, my brain just couldn't make sense any of it.

can anyone giving me an example for the 2nd part which is easy to understand?

Why does it sound like you are asking for help on math homework…

 

[K5Rakitan]

I don't know, but I would like someone to tell me about these things during sex.

 

[Kilolo]

Why does it sound like you are asking for help on math homework…

if this is how you perceive it, then that means you never help anyone with their math homework.

i didn't try to find the x or shit, even the theorem is already proven.
but i still trying to understood the principle behind it because despite it doesn't makes any sense to me, everyone is saying the same thing.

and by everyone i meant article that explaining about euclid theorem.

so that's just means i'm lacking in the understanding, and i want to know what it is.

 

[Sigyrr]

so in this light novel I currently read, there's a mention about the MC answering the question about does prime numbers goes infinitely, and then he provide the Euclid theorem to proving that prime number is indeed goes to infinity.

but my problem is that I barely understood half of the theorem.

I do understand that :
if p = prime number then
p₁ * p₂ *... pₙ + 1 = q

then q would be either prime or a non prime number.

i understand if you're using the prime number in ascending order, that you would get

2+1=33, is prime
2×3+1=7, is prime
2×3×5+1=31, is prime
2×3×5×7+1=211, is prime
2×3×5×7×11+1=2311, is prime
and so on.

what i didn't understand is the second part, what should i do if the i use a difference sequence of the prime numbers and arrive at a non-prime number of q

for example if i use 3 * 5 + 1 = 16
then what should i do with the 16 to proof that i could make it into a prime number that's not in the list of p? (which is 3 and 5)

and yes, the first example should be enough to proof that the number of primes are infinite, but when i check wikipedia and other site everyone dictate the same thing that suggest you could do something about the non-prime number of q, my brain just couldn't make sense any of it.

can anyone giving me an example for the 2nd part which is easy to understand?

Essentially it means that there is a prime number not included in this list that makes up the product, that is a factor of q. In this case you did not use the prime number 2 that is a factor of 16.

if a list of all primes can create a product + 1 that is not a prime number then that means that there is a factor that is a prime number not included in this list…. Meaning that the list does not include all prime numbers.

in the future ask math homework help elsewhere lol.

 

[J_Chemist]

Yes. I have encountered this before.

No. I am not doing your homework.

 

[Kilolo]

if a list of all primes can create a product + 1 that is not a prime number then that means that there is a factor that is a prime number not included in this list….

what? so the theorem requires to use all of the prime number up to the biggest prime number in the formula?

 

[WinterTimeCrime]

I don't know, but I would like someone to tell me about these things during sex.

​

... I-I could assist with such a complication!​

​

​

​

 

[gaylolis]

just listen to some indian guy on youtube, i think you'll get it.

 

[Titanoktonon]

what? so the theorem requires to use all of the prime number up to the biggest prime number in the formula?

Yes, you need to use all prime numbers. Generally, if y=x*z, then there is no integer w such that y+1=x*w. In that case, you could substitute y in the second equation and get
y+1=x*z+1=x*w
x*(z-w)=-1
x=1/(w-z)
so the only set of integers this would work with requires x=+-1 if w and z are 1 different.
Thus, if you have a number that is a product of all prime numbers up to some limit, then none of those prime numbers can be in the prime factorization of the number 1 greater than it, and the only number in the prime factorization can be is it itself.

 

[EchoingRuby]

This is a proof by contradiction, so let's say that all the prime numbers are 2, 3, 5, and 7. We already know this isn't true but we're trying to find a contradiction, thus disproving the conjecture that "2, 3, 5, and 7 are all the prime numbers".

Let's multiply them all together: 2*3*5*7 = 210. 210 is a multiple of all those numbers because of, well, the definition of what "being a multiple" even means.

Now recall that (natural number) multiplication is defined to be repeated addition: 4*3 = 3 + 3 + 3 + 3 = 12. This means that, say, the next multiple of 2 after 210 is 212, and similar for all the other numbers that got multiplied in.

This means that as long as we add some number smaller than all the numbers we multiplied in, the result will not be a multiple of any of them. So 210 + 1 = 211 is not a multiple of 2, 3, 5, or 7.

Our conjecture was that 2, 3, 5, and 7 were the only prime numbers, but we have just constructed another number that cannot be written by multiplying 2, 3, 5, and 7 together, which fits our definition of what a prime number is. Therefore our conjecture is wrong.

There's a small nuance here when you generalize this to a list of arbitrary size: the number you get through the process could be prime itself, like 211, but it could also be divisible by a number not in our original list, which also disproves the conjecture. For example, if we add 211 to our list, 2*3*5*7*211 + 1 = 44,311, which is not in itself prime, but can be written as a multiple of two numbers not already on the list: 44,311 = 73*607. It's *these* numbers, 73 and 607, you need to add to the list if you want to keep generalizing, NOT 44,311, since it is not prime.

So in general, if you have a finite list of prime numbers p_1, p_2, p_3, ..., p_n, and we are asserting that these are ALL of the primes, we can define a number q = p_1*p_2*p_3*...*p_n + 1, and show that q is either prime itself (meaning it should have been on the list but wasn't), or is divisible by numbers with the primality property that are not on the list (meaning those numbers should have been on the list). The same logic will now work with our new, larger list, so you can just keep repeating this process forever, finding numbers that should be on the list but aren't.

 

[Fox-Trot-9]

Nope. That's all Greek to me.

 

[K5Rakitan]

​

... I-I could assist with such a complication!​

​

​

​

Spoiler

As much as I would appreciate the assistance, there are several other complications. I'm polyamorous and married for one thing. For another thing, I'm not even seeing my local boyfriend in-person right now due to the pandemic.

 

[nullspice]

Euclid's proof of infinite prime numbers is *not* a proof by contradiction. Many people use a contradiction version of it, but originally it was a constructive proof.

The proof shows that if you have a finite set of prime numbers, then you can use that to come up with another, different, prime number. For instance, the set {2,3,5}, then 2*3*5+1=31, 31 is prime and not in that set. Note, however, that adding one does not always get you a new prime in and of itself, but a new prime *will* be a factor of the new number. For instance, 2*3*5*7*11*13 +1 = 30031 = 59 * 509, with 59 being a new prime that isn't 2,3,5,7,11, or 13.

So if you have a finite set of primes, you can always get another new prime

In your example, you talk about 3*5+1=16
16 is 2*2*2*2, and 2 is neither 3 nor 5, so it is a new prime number.

The proof in general goes, let p1, p2, ... pn all be prime numbers.
Multiply them together, p1*p2*...*pn
Add one to that new number, p1*p2*...*pn+1
Now, because all integers must be a product of primes, this new number must be a product of primes
However, because none of p1, p2, ... , pn can divide the number p1*p2*...*pn+1 (because they can divide the left side, but not the 1, they'd get something + 1/pwhatever), then this number must have a new, different prime as a factor. More than that, it cannot have any of the 'p's

(edit starts here)
Oh sorry, to add onto my last post, if you want to have a way of infinitely getting more primes, you can just use this method over and over
{2,3,5}
2*3*5+1=31
{2,3,5,31}
2*3*5*31+1=931=7*13
{2,3,5,7,13,31}
2*3*5*7*13*31+1=84631
{2,3,5,7,13,31,84631}
and so on and so forth

This is not really a computationally efficient method since it requires you to check if your new number is prime and if not, what are its factors, which is fairly difficult to do with large numbers

 

[Tlthon]

Spoiler: Nerd shit about proof by contradiction

Contradiction is a proof where we assume that what we're going to proof is false and then discover that mathematics break down.

Ex, there is no largest natural numbers could be proven by assuming that there's largest natural numbers (Let's called it N) and found that the number would not make sense (N+1 would have to be lower than N) and that's where the math broke down.

Basically it works like this,
1 assume there is a finite prime number let's called it P1, P2, P3,... Pn

2 If we multiply all those prime number and added by one you will get a new number which could not be divided by any of the previous prime number.

3 which could have 2 possibility: the new number is prime and the new number isn't prime. (Let's called the number M)

3.1 If the M is prime, it means that there's more prime than assume in the first line which means the first line is false.

3.2 If the M is not prime than there must be a prime number other than the one on the first line that can divide M. Which also means that the assumption on the first line is false.

4 This is a contradiction which means that there could be no finite prime number, aka there's infinite prime number.

 

[LORD_SHAXX]

so in this light novel I currently read, there's a mention about the MC answering the question about does prime numbers goes infinitely, and then he provide the Euclid theorem to proving that prime number is indeed goes to infinity.

but my problem is that I barely understood half of the theorem.

I do understand that :
if p = prime number then
p₁ * p₂ *... pₙ + 1 = q

then q would be either prime or a non prime number.

i understand if you're using the prime number in ascending order, that you would get

2+1=33, is prime
2×3+1=7, is prime
2×3×5+1=31, is prime
2×3×5×7+1=211, is prime
2×3×5×7×11+1=2311, is prime
and so on.

what i didn't understand is the second part, what should i do if the i use a difference sequence of the prime numbers and arrive at a non-prime number of q

for example if i use 3 * 5 + 1 = 16
then what should i do with the 16 to proof that i could make it into a prime number that's not in the list of p? (which is 3 and 5)

and yes, the first example should be enough to proof that the number of primes are infinite, but when i check wikipedia and other site everyone dictate the same thing that suggest you could do something about the non-prime number of q, my brain just couldn't make sense any of it.

can anyone giving me an example for the 2nd part which is easy to understand?

Bruh why you asking people here most Shub members can barely read let alone do math.

 

[TheEldritchGod]

Step 1 math
Step 2 then a miracle occurs
Step 3 ???
Step 4 profit.

 

[Awasti]

Step 1 math
Step 2 then a miracle occurs
Step 3 ???
Step 4 profit.

G-genius!!

 

[TheEldritchGod]

G-genius!!

I have to admit, as a god, I fall back on miracles often. Its lazy, I know. You're like, hey, everyone is trapped against the red sea. I know, miracle!

But then you get complaints from reddit. And no god wants a bad yelp review. However, it is still a useful part of the tool box.

You know the old saying, when all you have are miracles, everything starts looking like a Mary Sue.

 

[judojimmy]

The whole point of starting with 2 and adding one is to make sure the resulting number is odd because all primes are odd except for 2. Otherwise like your example 3*5+1=16 which is even.