00:00Hi guys, so in this
00:01video we are going to
00:02prove that there are infinite
00:04primes and what I mean
00:05by that is there there
00:06are an infinite number of
00:08prime numbers. So we actually
00:10have I've written down here
00:10the largest prime number that
00:12we know of. So there's
00:13computers that spend all their
00:17time working out prime numbers
00:19and the largest one we
00:20have is this. This is
00:22a prime number 2 to
00:23the power of 77 ,232
00:25,917 minus 1.
00:28obviously without that minus one
00:30it's not a prime number.
00:33So this is the largest
00:35one that we know of
00:36but we're going to prove
00:38that there are larger ones
00:40and in fact there are
00:41an infinite number of prime
00:44numbers. This number here is
00:46so big that if you
00:48were to write it out,
00:49if you were to write
00:50out the number and let's
00:52say you could write one
00:53digit, let's say you could
00:56write one digit every second,
00:58it would take you about
00:59nine months just to write
01:00out the number. So it's
01:01a pretty, it's a pretty
01:02big number. And for sure,
01:05there's no way any human
01:08could have calculated that without
01:10the help of computers. So
01:13what we're going to do
01:14now is we're going to
01:15prove by contradiction that there
01:18are an infant number of
01:19primes that this proof was
01:20first discovered or
01:24introduced by Euclid in 300
01:28BC so a long, long
01:29time ago and it was
01:32published actually in his one
01:35of his famous books called
01:38The Elements of Euclid. Now
01:40I actually have... well I
01:43thought I had the book.
01:44I went to a student
01:45actually gave me as a
01:47gift, the book and I
01:49went to find this proof
01:50because I know this proof
01:51is in the book
01:52but it turns out there
01:54are 13 books and I
01:55have the first six books
01:57so it didn't actually have
01:58it. But I of course
02:01do have Google which I
02:02also had to find this.
02:04So this is the largest
02:05at this at the time
02:06that I'm recording this video.
02:08Maybe they'll find a bigger
02:09one soon. Who knows? Anyway,
02:13this is how we're going
02:13to do it. As always,
02:15we assume the opposite. So
02:18if we're trying to prove
02:18that there are an infinite
02:19number
02:20prime numbers, we're going to
02:21assume there are a finite
02:26number of prime numbers. And
02:37we're going to let P
02:40be the set of all
02:47primes.
02:48So we're saying there's a
02:51set p and we're gonna
02:54say p is the set
02:57of all we say p1,
02:58p2, p3, p4 all the
03:03way up to pn. So
03:06this is the set of
03:08prime numbers and it's finite.
03:10There's a finite number of
03:11primes and this is the
03:12smallest one. This is the
03:13biggest one. So this is
03:14like two, three,
03:16five, seven, et cetera. Okay,
03:20next thing we're gonna do,
03:23this is what you could
03:24came up with. We're gonna
03:25say let n, let n
03:29equal p1 times p2 times
03:33p3 times p4 times all
03:38the way to pn plus
03:43one.
03:44I'll show you what we
03:46do in a second. So
03:48n is we're multiplying all
03:51of the prime numbers that
03:53exist. We're assuming there's a
03:54finite set. We're going to
03:55multiply them all together and
03:56we're going to add one.
04:00Now, because we've multiplied all
04:04these together and added one,
04:07we cannot divide n. So
04:10n
04:12is not divisible by any
04:22element of P. So we
04:30cannot divide n by any
04:34element of P as in
04:35any prime number. Because, well,
04:40you can divide it, but
04:41you're going to get a
04:42remainder, a remainder one. So
04:44it's not divisible by it.
04:45None of these numbers go
04:46into n nice and evenly.
04:50We always have a remainder
04:51one. Because think about it,
04:52if you divide by p1,
04:54you're going to, the p1's
04:55are going to cancel, and
04:56you're going to be left
04:56with p2 times p3 times
04:58p4 all the way up
04:59to p times n plus
05:011 over p1. So you
05:03have your remainder one, same
05:04if you divide by p2,
05:05same if you divide by
05:06p3 all the way up
05:07to pn.
05:08So n is not divisible
05:10by any element of peanut.
05:11This is the most important
05:14part of the whole proof.
05:18Okay, now assuming we have
05:20that, I'm gonna say n
05:24is bigger than n is
05:29bigger than, and actually before
05:31I do that, we're gonna
05:32say, therefore, if n is
05:36not
05:36divisible by any of these.
05:39Therefore, n has to be
05:44n must be a prime
05:47number. Now the reason for
05:53that is because remember what
05:54I said, I can write
05:5670 as 7 times 5
06:00times 2. Every single number
06:03that is not a prime
06:04number
06:04number can be written as
06:06a product of prime factors.
06:08So if none of these
06:09numbers, if n cannot, if
06:13n does not have one
06:14of these as a factor,
06:16then it has to be
06:17itself a prime number. For
06:19example, let's say I pick
06:22the number 37, 37 equals
06:27what times what? Nothing. I
06:28can't. There are no numbers.
06:30So 37 must be a
06:32prime.
06:33Okay, so n must be
06:36a prime, but, but, and
06:41let's do not keep this
06:43in your proof. I'm gonna
06:45say but n is bigger
06:49than all of these, it's
06:55actually bigger than all of
06:56these multiplied together, because I'm
06:58gonna add one. So I'm
06:59just gonna say, but n
07:00is bigger than
07:01Pn where Pn is the
07:09largest element of P. So
07:19n is bigger than this.
07:20It's bigger than all of
07:21them, but it's clearly way
07:22bigger than any of these
07:23elements. Therefore, therefore again,
07:29n because n is bigger
07:32than all these n is
07:34not an element of p.
07:45So, can we see the
07:47contradiction? I've said here, I've
07:49shown here that n must
07:51be a prime number because
07:52of this thing because it's
07:53not divisible by any of
07:54these.
07:57But here I've said n
08:00is not an element of
08:01p. But p is the
08:03set of all prime numbers.
08:04So how could it be
08:05a prime? How can n
08:06be a prime and not
08:07be a set and not
08:09be in the set of
08:12all prime numbers? So there's
08:15your contradiction. So we say
08:17this is a contradiction.
08:25as P and again always
08:32write this as a contradiction
08:33and Y because as P
08:37is as P is the
08:41set of all primes and
08:51there we go. So and
08:53finished off
08:53by saying, um, what are
08:56we trying to prove there
08:56are infinitely many prime numbers.
08:59Therefore, there are an infinite
09:06number of prime numbers.
09:21done. That is a really
09:26nice proof and you could
09:29be asked that in an
09:31exam for sure. In fact
09:33it specifically mentions this example
09:36in the guide where we
09:38look at proof by contradiction.
09:41You certainly don't need to
09:42know this number here but
09:45for sure it is interesting.
09:48Okay that's
09:49That's it. That's the last
09:52lesson on proof by contradiction
09:53I'm going to do. One
09:55more lesson on proofs. See
09:58you then.