Learn AAHL 1.15.8 Proof by contradiction (infinite primes) in this free IB Mathematics Analysis and Approaches (AA) video lesson for AHL 1.15—Proof by induction, contradiction, counterexamples.
Learn AAHL 1.15.8 Proof by contradiction (infinite primes) in this free IB Mathematics Analysis and Approaches (AA) video lesson for AHL 1.15—Proof by induction, contradiction, counterexamples.
The video discusses the proof that there are an infinite number of prime numbers, originally introduced by Euclid around 300 BC. The proof employs a method of contradiction, assuming a finite set of primes and demonstrating that a number constructed from these primes plus one cannot be divisible by any of them, thus leading to a contradiction.
Key points include:
The video concludes by emphasizing the significance of this proof in the context of mathematical reasoning and proof by contradiction.
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:22
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.