[Discrete Mathematics] Primes and GCD 

Thank you, really useful

3*5+1=16 isn't prime?

just, because you forgot 2. obviously 2 divides 16. you really need to take the product of all primes up to some maximal number, eg. 2+1=3, which is prime. also 2*3+1=7, 2*3*5+1=31, which are both primes

The Fundamental Theorem of Arithmetic states that EVERY single composite number can be expressed as the product of 2 or more primes that aren't just the product of 1 and the number in question, take that as an axiom. That means if we assume (p1*p2*...*pn + 1) is a composite number (not prime), we can express it as the product of 2 or more prime numbers that isn't just 1 multiplied by itself. We already have our established, finite list of prime numbers {p1, p2,..., pn}. This means that (p1*p2*...*pn + 1) is really just the product of a selection of primes from our list. If that's the case, this means that at least one of the primes successfully divides (p1*p2*...*pn + 1) without a remainder. Upon dividing this allegedly composite number by our primes, we always end up with a remainder of 1. This establishes that it's impossible for (p1*p2*...*pn + 1) to be composite, this implies it is prime. And this fundamentally shatters the idea that prime numbers are finite, since we assumed our list contained all possible primes which conflicts with the fact that we created an entirely new prime number.

@@commenting000 try doing 2 x 3 x 5 x 7 x 11 x 13 +1, you will get 30031 which is composite

It means "if and only if"

Numbers having no other common factor than 1 are said to be co-prime...

It only produces candidates of prime number. It doesn't say it will always produce prime numbers for every Pn+1 value. Each number needs to be double checked if you want to make sure that it's prime. The set of all prime numbers is a subset of Pn+1. In the video, he says that it proves that prime numbers are infinite. This can be proved by using mathematical induction.

Its to prove that prime numbers are infinite. Pn+1 is not prime. But if you assume prime numbers are finite, for example 2,3,5,7,11,13, then you should be able to write any number bigger than 13 as product of these numbers since every composite can be written as product of primes. But 2*3*5*7*11*13+1 cant be written as product of numbers in 2,3,5...,13(we assumed these are all the primes). Then only possible solution is 2*..13+1 is prime. But thats contradiction. So what we assume must be wrong. Basically pn+1 becomes prime because of our assumption that prime numbers are finite(this is how we got contradiction). But pn+1 is not true when primes are infinite

+Abhishek Tiwari The way this proof is set up is he assumed that it was finite at first. Pretend no one in the world knows which answer(finite or infintite)is correct yet so youre just assuming. Then when you find a contradiction within this assumption, you can conclude that your assumption was wrong.

I'm asking that in the proof he assumed that p(n) =p1*p2...*pn is set of finite primes then he calculated p(n+1)=(p1*p2*....*pn)+1 and said that this would add up a new prime...how he made this statement..??

+Abhishek Tiwari p(n+1) is not divisible by p1, not divisible by p2, ..., not divisible by pn. I neglected to expand upon it, but instead of typing it out, I'll copy and paste the proof from the following site: primes.utm.edu/notes/proofs/infinite/euclids.html "Call the primes in our finite list p1, p2, ..., pr. Let P be any common multiple of these primes plus one (for example, P =p1p2...pr+1). Now P is either prime or it is not. If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p. Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible. So this prime p is some prime that was not in our original list. Either way, the original list was incomplete."

Exactly that is wrong. You have to prove the summation of Pn+1 wrt to P1...Pn