/sci/ - Science & Math

[Anonymous No.2421547]

Can somebody explain Euclid's Theorem of Infinite Primes to me?
I understand most of it, just not the final bit, which is probably the most important.

"Take any finite list of prime numbers p1, p2, …, pn. It will be shown that some additional prime numbers not in this list exist. Let P be the product of all the prime numbers in the list: P = p1…pn. Letq = P + 1: 1 more than this product. Then, q is either prime or not:

If q is prime then there is at least one more prime than is listed.
If q is not prime then some prime factor p divides q. This factor p is not on our list: if it were, then it would divide P (since P is the product of every number on the list); but as we know, p dividesP + 1 = q. Then p would have to divide the difference of the two numbers, which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list."

That’s what Wikipedia has for the Theorem. It all makes sense to me until the very last bullet point. I don’t get what it’s trying to say. Can somebody give it to me simply? Just, y’know, dumb it down a bit. I just don’t understand the reasoning behind “If P+1 isn’t prime then it’s prime.”

Thanks

[i- !LoVeEKpnh2 No.2421594]

We assumed we had all primes. We know every number can be factored into primes. So we create a number, and show that it isn't divisible by any of our primes. Therefore our list of primes must be missing some primes.

[Anonymous No.2421631]

what if the number you are testing is a prime?
need philosoraptor

[i- !LoVeEKpnh2 No.2421649]

>>2421631
Then, clearly, it isn't in our list.

[Anonymous No.2421647]

>>2421631

Then it's the prime that your list is missing.

[Anonymous No.2421674]

Okay, let's say all the primes I know are 1, 2, 3, 5. By multiplying them all I get 30. 31 is prime. If it isn't, then it can be factored by a prime I have no clue about.

[Anonymous No.2421690]

It is a proof by contradiction. We want to show that there are infinitely many prime numbers.

Suppose that our premise is not true and there is a finite number of prime numbers.Then, Euclid's theorem shows how to build a new prime number not in your finite list. Then there must be infinitely many prime numbers.

[Anonymous No.2421714]

>>2421674

Why does it have to be a prime that factors into it, though? If you multiplied all the primes you know and added one and it isn't a prime, what makes us so sure that a prime HAS TO go into that number?

[i- !LoVeEKpnh2 No.2421715]

>>2421690
It doesn't build primes. But it does build numbers that, if not prime, have a prime factor not in our list.

[i- !LoVeEKpnh2 No.2421722]

>>2421714
The fundamental theorem of arithmetic.

[Anonymous No.2421786]

Bwah, mathematicalprooffail.

>>No prime number divides 1

You can't be sure about that since you do not know all the prime numbers.
You haven't even proved that there is an infinite amount of prime numbers, and you can't prove that there is, without taking for granted the fact that no prime number divides 1, and you can't prove no prime number divides one without knowing all the prime numbers...

AXIOMS ARE CONDUCIVE TO POORLY REASONED ARGUMENTS.

KINDA LIKE RELIGION.

SCIENCE : 0
RELIGION : 0
ME: over 9000

[Samefag !SHjzCSZsqE No.2421820]

>>2421786

[Anonymous No.2421870]

>>2421715
I stand corrected

[Anonymous No.2421874]

>>2421722

...damn it, why didn't they teach me that in school!

[Anonymous No.2421897]

>>2421714
We're assuming that it is not prime by the second bullet point. A number is either prime or not prime, this partitions all possibilities.

[Anonymous No.2421934]

>>2421714
>>2421722
>>2421874
Actually that's not the most basic reason. :D

The theorem "every integer greater than 1 is divisible by a prime number" can be proven by using the well-ordering principle, the definition of prime/composite, and the transitivity of divisibility.

Also, >that goth bitch

[i- !LoVeEKpnh2 No.2421942]

>>2421934
oh fuck yes

[Anonymous No.2421949]

>>2421874
Also, this is why I say the public school system depresses me and that people should give homeschooling a chance whenever their parents are able to put forth a really nice effort to teach.

[Anonymous No.2421953]

>>2421942
Hot damn my balls are tingling

[i- !LoVeEKpnh2 No.2421956]

>>2421949
Information is out there for free right now. Libraries, textbooks on the internet, math and science forums... If you want to learn something, the only thing standing in your way is you (and a few trolls).

[Anonymous No.2421988]

>>2421949
To be fair, it's not math history but just how to manipulate numbers that's taught in school. Most high school courses are algebra, geometry and the like, not number theory.

The reason public education isn't comprehensive enough to cover this sort of stuff is that it tries to get people ready for jobs, and this isn't necessary.

That may be the problem, but...

[Anonymous No.2422002]

Isn't q always prime?

[Anonymous No.2422008]

>>2421988
>it tries to get people ready for jobs

It also completely fails to do that, at the pre-university level... Mostly because the people who are currently in charge of education are more concerned about federal money than anything else.

But yeah I see where you're coming from.

[Anonymous No.2422019]

>>2421949
Sounds like a massive headache
You'll be helping them more if you use that energy to tutor them instead

[i- !LoVeEKpnh2 No.2422021]

>>2422002
No. <span class="math">2\cdot 7 + 1 = 15[/spoiler] is not prime, but it is divisible by 3 (not in the list of (2,7)). If you insist on contiguous primes, wiki has a counterexample.

[Anonymous No.2422024]

>>2422002
No, it just isn't divisible by anything in our list.

[Anonymous No.2422030]

I'm taking discreet mathematics and I'm just learning about this stuff
Its like nothing I've ever seen before
Its also scary

[Anonymous No.2422039]

>>2422030
discrete mathematics*
typo

[Anonymous No.2422056]

>>2422030
You respect the numbers, they will respect you.
Kind of like wasps.

>>2422039
Discreet mathematics is what I do with my girlfriend, we're both huge nerds, especially in bed. Ever heard of rectilinear motion?

[Anonymous No.2422062]

>>2422024
>>2422021
Thanks. I'm having a little problem with the second bullet point, as OP:
1- It says that no prime number divides 1. Does this mean that, 1 isn't divided by any prime number? THat is, 1/prime
If it's that, I know it's obvious, but English is not my mother language and I get confused by stupid little things such as these, sorry.

2- Then p would have to divide the difference of the two numbers, which is 1.
What does it mean by this?

[Anonymous No.2422070]

>>2422056
>You respect the numbers, they will respect you.
I have yet to see a number on that class

[Anonymous No.2422076]

>>2422056
>Implying wasps aren't mean motherfuckers that do what they want.
Bees are the true bros.

[Anonymous No.2422103]

>>2422076
...except for Irrational Bees

[μαθμαν - the enlightened undergraduate !!vnLoxcfyRGs No.2422111]

>>2422103
and spelling bees.

[Anonymous No.2422153]

>>2422062
I need an answer, plz.

[Anonymous No.2422224]

bump

[Anonymous No.2422228]

>>2422062
1. Yes, 1/prime is not an integer
2. If p divides a and b, then it must divide their difference, |a-b| (can be proved).

[Anonymous No.2422248]

>>2422228
Here a=P, b=P+1 => |a-b| = |P-(P-1)|=1.

[Anonymous No.2422259]

>>2422228
But doesn't p divide q only? It doesn't divide P, does it?

[Anonymous No.2422294]

>>2422259
Yes you are right, but the reason why is because if p did divide P as well as q, then p would also divide 1. We know this is not possible, hence it does not divide P (this is a proof by contradiction).

[Anonymous No.2422317]

>>2422294
Thanks man. Now I understand it and I can finally go to bed in peace.
Here, have some troll physics.

[Anonymous No.2422331]

>>2422317
Cheers, goodnight.