I don't think its about editing the video. I think its about sharing a thought in the most precise manner possible. Can't do that when the mistake is still floating there, hence the pause and reset.
25:06 I’m adding one more conjecture (and yes, I know there is plenty of them) : For any positive integer n>=1, there is at least a prime number between n^2 and (n+1)^2 25:14 Homework 26:12 Good Place To Stop
14m08s: In your expression for a general polynomial, the sum should start at k=0, not 1. Of course, when you take f(1+mp) - f(1), the constant term, k=0, drops out. But the polynomial still needs to include a₀ . 25m47s: Goldbach Conjecture. It's every even nr. ≥ 4 (2 can't be written as a sum of two primes). Fred
Spoiler alert. For those who want to check their warm-ups. We will use a^(mn) + 1 = (a^(m))^n + 1 = (a^m + 1) . (a^(m(n-1)) - a^(m(n-2)) + ... + 1) where n is odd. The signs alternate in the second factor. and a^(mn) - 1 = (a^(m))^n - 1 = (a^m + 1) . (a^(m(n-1)) + a^(m(n-2)) + ... + 1) for all n . This is difference between squares for n=2. *Factorise 2^24 - 1.* It's easiest to keep m big and n small to avoid too much arithmetic. We can use 12 = 6x2 for (2^12 - 1), but we have to use 12 = 4x3 for the (2^12 + 1 ) factor. 2^24 - 1 = (2^12)^2 - 1 = (2^12 - 1).(2^12 + 1) = (2^6 - 1)(2^6 + 1) . (2^4 + 1)(2^8 - 2^4 + 1) we can factor the first two terms, but not the last two by these methods. = (2^3 - 1)(2^3 + 1)(2^2 + 1)(2^4 - 2^2 + 1) . (2^4 + 1)(2^8 - 2^4 + 1) Time to work out the powers and factorise any remaining primes: 2^24 - 1 = 7 x 9 x 5 x 13 x 17 x 241 = 3^2 x 5 x 7 x 13 x 17 x 241 *Factorise 2^15 - 1.* I think it's easier to keep n small, but I'm familiar with most of the powers of 2 from computing. Others may prefer to factorise (2^3)^5 - 1 to get smaller powers. 2^15 - 1 = (2^5)^3 -1 = (2^5 - 1).(2^10 + 2^5 + 1) = 31 x 1057 but we know that the alternate factorisation (2^3)^5 - 1 will give a factor of (2^3 - 1) = 7, so we know 7 will divide 1057. 2^15 - 1 = 31 x 1057 = 31 x 7 x 151 The alternate route looks like this: 2^15 - 1 = (2^3)^5 - 1 = (2^3 - 1)(2^12 + 2^9 + 2^6 + 2^3 + 1) = 7 x (4096 + 512 + 64 + 8 + 1) you'll note that each part of the second term is 2^3 times the next one, so it's easy to build as 1 + 8 + 8*8 + and so on; there are 5 terms. 2^15 - 1 = 7 x 4681 but we know that 31 has to be a factor, so 2^15 - 1 = 7 x 31 x 151 *Find all primes of form 2^(2^n) + 5.* This is straightforward using modular arithmetic because 2^2 = 4 ≡ 1 (mod 3). However, for those who are not familiar with modular arithmetic, there is an equivalent solution: 2^2^n = 2^(2*2^(n-1)) = 4^2^(n-1) But we can write 4 as (1+3). That then gives (1+3)^2^(n-1). If n>0, we can expand that using the binomial expansion. That gives 1 + 2^(n-1).3 + (2^(n-1).(2^(n-1) - 1)/2).3^2 + ... But all of the terms except the first one contain a power of 3 and are therefore divisible by 3. That means 2^2^n always leaves a remainder of 1 when divided by 3, for all n>0. So 2^2^n + 5 when divided by 3 leaves a remainder of 0 (because 1 + 5 = 6 which is divisible by 3) for all n>0, so cannot be prime. That leaves us to check n=0: 2^2^0 + 5 = 2 + 5 = 7 which is prime. And that's the only one.
Was the homework 2^(2^n) or (2^2)^n? (the first formula will result in much larger numbers then the second) For 2^2^n+5=4^k +5 you need the second formula To get 7 (with n=0) you need the first formula because with formula 2 you get (2^2)^0 + 5 = 6
I discovered a super simple proof of the infinitude of primes in 1983 in high school geometry class. Here it is: Start with any 2 odd prime numbers, like 3 and 5. Multiply them together--3x5=15. Now add 2: 15+2 =17. One of two things must occur when multiplying 2 odd primes together and then adding 2. Either the resulting number is prime, as in the case of 3 and 5, or the result is composite, as in the case of 3 and 11, where multiplying and adding 2 yields 35, which is composite. Either way, the resulting number cannot be a multiple of the two numbers we started with. Odd prime numbers A and B, when multiplied together and then adding 2, it is evident that the very next multiple of A would be by adding A, and the very next multiple of B would be by adding B. But we are only adding 2, which results in either another prime, or a composite that is relatively prime to both the numbers we started with. Now, take the resulting number, put it back into the method, add 2, and the resulting number is relatively prime to those three numbers. Going back to 3 and 5: 3x5 =15. 15+2 =17, which must be relatively prime to 3 and 5. Put 17 back into the method: 3x5x17=255. 255+2=257, which must be relatively prime to 3, 5, and 17. Put 257 into the method. 3X5x17x257=65,535. 65,535+2 = 65,537, which must be relatively prime to 3, 5, 17, and 257. Put 65,537 back in and we have 3x5x17x257x65,537, add 2, etc. We can continue this as many times as we like, ad infinitum, and thus there are an infinite number of primes. Again, you could start with any two odd primes and use the same method. 7 and 11, or 31 and 89, or 109 and 997, etc. A nearly identical method starts with 2 and any other prime number, then adding 1. Say 2 and 11. 2x11=22, 22+1=23. 2x11x23=506. 506+1=507. In this case, 507 is composite as it factors as 3 x13 x13. We don't need the 2nd factor of 13, so just put 3 and 13 back in. 2x11x23x3x13=19,734, 19,734+1=19735=5 x 3,947. 2x11x23x3x13x5x3947, add 1, etc. ad infinitum. The Sieve of Eratosthenes is used to find all prime numbers up to a given limit. I found a method that uses the sieve to prove the infinitude of primes. Perhaps I'll post that on a future video.
"One of two things must occur when multiplying 2 odd primes together and then adding 2. Either the resulting number is prime, as in the case of 3 and 5, or the result is composite" You do not show in your proof that your procedure will not always start returning composites above a certain value. Furthermore relatively prime does not mean prime, 3*5*7*11+2 = 1157 which is relatively prime to all the constituents used up to that point, but which is not itself a prime.
@@johangamb I state that in my proof. That doesn't negate anything. The fact that a composite number occurs at times still necessitates that composite number to be relatively prime to the numbers that are started with. In any case, just factor the composite number into it's prime factorization and put those primes back into the procedure.
You can identify most composites without actually performing the multiplications. Ever prime greater than 3 is of form 6k+/-1. Multiplying two primes of this format will yield another number of the same format… (6k-1) (6j-1) = 36jk -6j -6k +1 = 6(6jk -j -k)+1 (6k+1) (6j+1) = 36jk +6j +6k +1 = 6(6jk +j +k)+1 (6k-1) (6j+1) = 36jk -6j +6k +1 = 6(6jk -j +k)-1 (6k+1) (6j-1) = 36jk +6j -6k +1 = 6(6jk +j -k)-1 In the first two cases, adding 2, makes the result a multiple of 3, so it’s always composite. It’s only when multiplying a (6k+1) by (6k-1) number that the result after adding 2 can be a possible prime, and will always be of the form 6k+1 Note also that if 3 is one of the primes in your set, then the final result before adding 2 is of form (6k+/-1) x 3, which is of course an odd multiple of 3, so adding 2 will always produce a number of the form 6k+5, aka 6(k+1)-1, which is a possible prime. Of course, you would still need to perform the multiplications and factor the composite numbers and add them to your set, but in terms of turning it into a proof, the above analysis is much more useful as it doesn’t depend on performing infinite operations.
18:21 An interesting note on the proof that there is no polynomial that can generate primes is that the proof he showed actually also proves that, if f is a polynomial and f(1) = n for some natural number n, then for all naturals m, f(1 + mx) is a multiple of n. It doesn't actually matter here whether or not x is prime, all that matters is f is a polynomial and f(1) is a natural number. This actually is kind of a surprising result at face value. You would think that, just maybe, you could find a polynomial f(x) such that f(1) = 6 but f(1 + m6) is not a multiple of 6 for some m. But no matter what polynomial you try if f(1)=6 then f(7), f(13), f(19), etc are all multiples of 6 too. Another way to prove this by the way would be to assume f(1) = n then consider f(1 + mn) mod n. Then f(1) = 0 mod n. But note that all the non-constant parameters in f will then be the same mod n as when you put in 1 mod n, and the constant in f will still be the same constant, so the result will be identical mod n to f(1), which means it will be 0 mod n.
Professor Michael Penn, thank you for a fantastic lecture/video on Proofs and Conjectures involving Primes. I watched and took notes on all 123 videos, and they were all incredible. I took an undergraduate class in Number Theory at the University of Maryland College Park in the early 1990's and it was a mess. I did not learn a single thing from the instructor. Over the years, I had to review the class on my own, to finally understand the basic material.
12:08 - if |a0| > 1, f(a0) is the non prime (factoring with |a0|) - if a0 = 0, (f(n) is the non with any n st |n|>1) if a0 = ± 1 (f(0) is the non prime)
2^(2^n)+5 problem can be nicely solved using induction. We want to prove that 2^(2^n)+5 is always divisible by 3 for n >= 1 we check the base case (n=1) 2^(2^1)+5 =9= 3*3 which holds. In the induction hypothesis we assume that this property holds for some natural number k which means that 2^(2^k) + 5 = 3d, where d is a natural number so 2^(2^k) = 3d -5 then 2^(2^(k+1)) + 5 = (2^(2^k))^2 + 5 = (3d-5)^2 +5 =9d^2 -30d + 25 + 5 = 9d^2 - 30d + 30 = 3(3d^2 -10d + 10)
For the last exercise, here's my solution: First try to put some number into n, like 0, 1, 2, 3...And in each cases, we have n=0: 7 (prime) n=1: 9 (not prime) n=2: 21 (not prime) n=3: 261 (not prime) .... And notice that when n is larger than 0, the result is always divisible by 3. So then I proved it via Mathematical Induction. Base case: n = 1, which equals to 9, is divisible by 3. Inductive Hypothesis: for some k > 1, 3 | 2^{2^k} + 5, which means 2^(2^k) = 3m-5. Now for the case of k + 1 we have, 2^{2^{k+1}} + 5, and 2^(2^{k+1}) = (2^{2^{k}} )^2. Then the expression can be rewritten as (3m-5)^2+5. By expandng this we can see that it equals to (9m^2-30m+30) = 3(3m^2-10m+10). And it's again can be divided by 3. Which completes the proof.
@@romajimamulo The bound on N can be reduced under the assumptions of other, yet unproven conjectures. One such conjecture, if true, brings the bound to 6.
At 11:30 ish, shouldn't it be that there's a list of *at least* n composite numbers, since (n+1)! + (n+2) might also be composite? E.g. for n=4 you have 5! + 6 = 120 + 6 = 126, which is composite.
For the proof of the no-constant polynomial thing, if we let f(x)=a_nxˆn+...+a_1x+a_0 (a general polynomial with integer coefficients), then we know that f(a_0) will be divisible by a_0, and thus not a prime. For the case where a_0 = 0, x will divide f(x) for all x. Now if it just so happens that a_0 = 1, we can look at g(x)=f(x+1), which if f(x) always yields primes will, surely also yield only primes. If we expand f(x+1) we see that the constant term of g(x), b_0, is NOT 1, and since b_0 divides g(b_0), it is not a prime, thus we get a contradiction!
Does anybody have a solution to homework #2 without using modular arithmetic? The only I found involves mod 3 and I want a solution using “current knowledge” built from previous videos.
Yes. 2^2^n = 2^(2*2^(n-1)) = 4^2^(n-1) = (1+3)^2^(n-1). If n>0, we can expand that as a binomial = 1 + 2^(n-1).3 + ... But all of the terms except the first one contain a power of 3 and are therefore divisible by 3. That means 2^2^n always leaves a remainder of 1 when divided by 3 for all n>0. Then it is clear that for n>0, 2^2^n + 5 leaves a remainder of 0 when divided by 3, so cannot be prime. It avoids using modular arithmetic, _per se,_ but is the same reasoning.
@@RexxSchneider Thanks. This is what I was looking for, I see now that it is kind of the same process, splitting 4 into 1 + 3 and binomial expansion. What I argued was that if 4 ≡ 1 (mod 3), then 4^k ≡ 1^k (mod 3) for any natural number k, but 1^k = 1 (obviously if k = 2^(n-1), this only holds for k > 0).
The second proof that M should be the infinite sum of the harmonic series is wrong: if there existed a biggest prime then there would be holes in the sum. Thus it would not anymore be proven that M is infinite. Let‘s suppose 5 was the biggest prime then there would be no terms of (1/7), (1/11) etc. and no powers of them in the series.
Maybe there is a kind of formula to find a prime. Multiplying the first n primes and add one, you will get a bigger prime. Unfortunately doesn't work to find the primes between 😬 E. G. 2*3*5*7 + 1 must be prime
excuse me, but 2*3*5*7*11*13+1 = 30031 = 59*509 is the smallest counter example... you won't always get a bigger prime, but might get a number that is divisible by a bigger prime!
2 is prime so an exception You have to use only primes 2+2=4 3+3=6 (but 2+4 is not allowed) 5+5=10 But you can't do 6+6 for 12, you have to do 5+7 so they're primes
At 13:40, "sort of m times p for obvious reason", well it is not obvious to me, and as an educator you should not make such an assumption, just be direct and to the point.
OK, so as a Physics student I took all these math classes. I did benefit from them in how I learned to think, but never actually used abstract algebra and number theory proofs in my work in Physics.
Why is it that when Euclid or somebody proved that there are an infinite number of primes, people were cool with it, but when Gödel proved that there are an infinite number of axioms, people lost their heads?
Because Godel’s Incompleteness theorem challenges the notion that we can know anything with certainty, and people cling to having certainty and “knowing the truth”. To assert that we can’t know with certainty is very confronting, it creates cognitive dissonance and that triggers fear for many people.
To be more accurate, Euclid had no notion of "infinitely many". He proved that given any set of primes, there is a prime not in that set (proved the way Michael proved it). Euclid then inferred that there are arbitrarily large sets of primes. But he didn't make the next conceptual leap to "infinitely many".
Godel's result is stronger than the result that some theories cannot be finitely axiomatised. He proved that every (consistent) axiomatisation is incomplete. So, even with theories with infinitely many axioms, incompleteness remains. People were cool with infinitely many axioms -- but when it was found that even those theories were incomplete, that's when people lost their heads.
You can show that this gives a polynomial infinitely many roots, and thus must be a contradiction Consider such a polynomial f(x) that achieves the same value C for infinitely many inputs x_1, x_2, etc. Look at the polynomial g(x) = f(x) - C. g(x) now has infinitely many roots at each x1, x2, etc. This is because g(x_j) = f(x_j) - C = C - C = 0. This is a contradiction because polynomials only have finitely many roots
Technical logical question: isn't proof by contrapositive really the same as proof by contradiction? You're assuming the opposite of the thing you're trying to prove, and proving a contradiction-in this case contradicting the assumption. Why call them two different things?
Proof by contrapositive relies on the fact that A=>B ~B=>~A. Both statements are equivalent, but it is sometimes easier for practical purposes in a particular problem to assume ~B and show that ~A follows, rather than assuming A and showing that B follows. By contrast, a proof by contradiction begins by assuming A is true, and a contradiction follows, thus demonstrating that the assumption is false, i.e., ~A is true. Notice a key distinction. In a contrapositive proof, we do NOT disprove our assumption. We show simply that IF ~B, then ~A follows. That does NOT mean that A is logically impossible or that we have contradicted the truth of A, and importantly, it does NOT show that ~B is true. Indeed, if A is true, then so is B (which likewise says nothing about the truth value of A). By contrast, following a proof by contradiction assuming A, we conclude that A cannot be true no matter what, thus proving ~A.
If you include zero among the possible values of n in 2^2^n + 5 , then n=0 gives the only prime of that form, 7. If you don't, then there are no primes of this form because 2^2^n is equal to 4^2^(n-1) , so for n greater than or equal to 1, 2^2^n + 5 is always equal to zero mod 3 . (Generally, 2^2^n + 2 + any multiple of three is never prime.)
Lists of conjectures should not be framed as questions. It is not immediately clear for the audience whether the conjecture is conjectured to be true or false, making it look more like a list of open questions.
![[#2024MAMA] BIGBANG (빅뱅) - 뱅뱅뱅 (BANG BANG BANG) + FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/EQsYfiPR9uM/mqdefault.jpg)
I like how when Michael screws up, he gives some space and restarts so he can edit the video properly, but then ends up not editing anything out!
I don't think its about editing the video. I think its about sharing a thought in the most precise manner possible. Can't do that when the mistake is still floating there, hence the pause and reset.
He cuts it sometimes, so it is definitely a mistake on editing. Not that it matters anyways
25:06 I’m adding one more conjecture (and yes, I know there is plenty of them) : For any positive integer n>=1, there is at least a prime number between n^2 and (n+1)^2
25:14 Homework
26:12 Good Place To Stop
10:04 Glitch in the matrix :)
14m08s: In your expression for a general polynomial, the sum should start at k=0, not 1.
Of course, when you take f(1+mp) - f(1), the constant term, k=0, drops out. But the polynomial still needs to include a₀ .
25m47s: Goldbach Conjecture. It's every even nr. ≥ 4 (2 can't be written as a sum of two primes).
Fred
Spoiler alert. For those who want to check their warm-ups.
We will use a^(mn) + 1 = (a^(m))^n + 1 = (a^m + 1) . (a^(m(n-1)) - a^(m(n-2)) + ... + 1) where n is odd. The signs alternate in the second factor.
and a^(mn) - 1 = (a^(m))^n - 1 = (a^m + 1) . (a^(m(n-1)) + a^(m(n-2)) + ... + 1) for all n . This is difference between squares for n=2.
*Factorise 2^24 - 1.*
It's easiest to keep m big and n small to avoid too much arithmetic. We can use 12 = 6x2 for (2^12 - 1), but we have to use 12 = 4x3 for the (2^12 + 1 ) factor.
2^24 - 1 = (2^12)^2 - 1 = (2^12 - 1).(2^12 + 1) = (2^6 - 1)(2^6 + 1) . (2^4 + 1)(2^8 - 2^4 + 1) we can factor the first two terms, but not the last two by these methods.
= (2^3 - 1)(2^3 + 1)(2^2 + 1)(2^4 - 2^2 + 1) . (2^4 + 1)(2^8 - 2^4 + 1)
Time to work out the powers and factorise any remaining primes:
2^24 - 1 = 7 x 9 x 5 x 13 x 17 x 241 = 3^2 x 5 x 7 x 13 x 17 x 241
*Factorise 2^15 - 1.*
I think it's easier to keep n small, but I'm familiar with most of the powers of 2 from computing. Others may prefer to factorise (2^3)^5 - 1 to get smaller powers.
2^15 - 1 = (2^5)^3 -1 = (2^5 - 1).(2^10 + 2^5 + 1) = 31 x 1057 but we know that the alternate factorisation (2^3)^5 - 1 will give a factor of (2^3 - 1) = 7, so we know 7 will divide 1057.
2^15 - 1 = 31 x 1057 = 31 x 7 x 151
The alternate route looks like this:
2^15 - 1 = (2^3)^5 - 1 = (2^3 - 1)(2^12 + 2^9 + 2^6 + 2^3 + 1) = 7 x (4096 + 512 + 64 + 8 + 1) you'll note that each part of the second term is 2^3 times the next one, so it's easy to build as 1 + 8 + 8*8 + and so on; there are 5 terms.
2^15 - 1 = 7 x 4681 but we know that 31 has to be a factor, so 2^15 - 1 = 7 x 31 x 151
*Find all primes of form 2^(2^n) + 5.*
This is straightforward using modular arithmetic because 2^2 = 4 ≡ 1 (mod 3). However, for those who are not familiar with modular arithmetic, there is an equivalent solution:
2^2^n = 2^(2*2^(n-1)) = 4^2^(n-1)
But we can write 4 as (1+3). That then gives (1+3)^2^(n-1).
If n>0, we can expand that using the binomial expansion. That gives
1 + 2^(n-1).3 + (2^(n-1).(2^(n-1) - 1)/2).3^2 + ...
But all of the terms except the first one contain a power of 3 and are therefore divisible by 3.
That means 2^2^n always leaves a remainder of 1 when divided by 3, for all n>0.
So 2^2^n + 5 when divided by 3 leaves a remainder of 0 (because 1 + 5 = 6 which is divisible by 3) for all n>0, so cannot be prime.
That leaves us to check n=0:
2^2^0 + 5 = 2 + 5 = 7 which is prime. And that's the only one.
Thankyou sir 😀
Homework: 2^2^n+5=4^k +5 if n>0 - 4 is 1 mod 3 and 5 is two mod 3. So the only prime in this form is 7
Was the homework 2^(2^n) or (2^2)^n? (the first formula will result in much larger numbers then the second)
For 2^2^n+5=4^k +5 you need the second formula
To get 7 (with n=0) you need the first formula because with formula 2 you get (2^2)^0 + 5 = 6
I discovered a super simple proof of the infinitude of primes in 1983 in high school geometry class. Here it is:
Start with any 2 odd prime numbers, like 3 and 5. Multiply them together--3x5=15. Now add 2: 15+2 =17. One of two things must occur when multiplying 2 odd primes together and then adding 2. Either the resulting number is prime, as in the case of 3 and 5, or the result is composite, as in the case of 3 and 11, where multiplying and adding 2 yields 35, which is composite. Either way, the resulting number cannot be a multiple of the two numbers we started with. Odd prime numbers A and B, when multiplied together and then adding 2, it is evident that the very next multiple of A would be by adding A, and the very next multiple of B would be by adding B. But we are only adding 2, which results in either another prime, or a composite that is relatively prime to both the numbers we started with. Now, take the resulting number, put it back into the method, add 2, and the resulting number is relatively prime to those three numbers.
Going back to 3 and 5: 3x5 =15. 15+2 =17, which must be relatively prime to 3 and 5. Put 17 back into the method: 3x5x17=255. 255+2=257, which must be relatively prime to 3, 5, and 17. Put 257 into the method.
3X5x17x257=65,535. 65,535+2 = 65,537, which must be relatively prime to 3, 5, 17, and 257. Put 65,537 back in and we have 3x5x17x257x65,537, add 2, etc. We can continue this as many times as we like, ad infinitum, and thus there are an infinite number of primes. Again, you could start with any two odd primes and use the same method. 7 and 11, or 31 and 89, or 109 and 997, etc. A nearly identical method starts with 2 and any other prime number, then adding 1. Say 2 and 11. 2x11=22, 22+1=23. 2x11x23=506. 506+1=507. In this case, 507 is composite as it factors as 3 x13 x13. We don't need the 2nd factor of 13, so just put 3 and 13 back in. 2x11x23x3x13=19,734, 19,734+1=19735=5 x 3,947. 2x11x23x3x13x5x3947, add 1, etc. ad infinitum. The Sieve of Eratosthenes is used to find all prime numbers up to a given limit. I found a method that uses the sieve to prove the infinitude of primes. Perhaps I'll post that on a future video.
excellent
seems like you discovered the original Euclid's proof
"One of two things must occur when multiplying 2 odd primes together and then adding 2. Either the resulting number is prime, as in the case of 3 and 5, or the result is composite"
You do not show in your proof that your procedure will not always start returning composites above a certain value. Furthermore relatively prime does not mean prime, 3*5*7*11+2 = 1157 which is relatively prime to all the constituents used up to that point, but which is not itself a prime.
@@johangamb I state that in my proof. That doesn't negate anything. The fact that a composite number occurs at times still necessitates that composite number to be relatively prime to the numbers that are started with. In any case, just factor the composite number into it's prime factorization and put those primes back into the procedure.
You can identify most composites without actually performing the multiplications. Ever prime greater than 3 is of form 6k+/-1. Multiplying two primes of this format will yield another number of the same format…
(6k-1) (6j-1) = 36jk -6j -6k +1 = 6(6jk -j -k)+1
(6k+1) (6j+1) = 36jk +6j +6k +1 = 6(6jk +j +k)+1
(6k-1) (6j+1) = 36jk -6j +6k +1 = 6(6jk -j +k)-1
(6k+1) (6j-1) = 36jk +6j -6k +1 = 6(6jk +j -k)-1
In the first two cases, adding 2, makes the result a multiple of 3, so it’s always composite. It’s only when multiplying a (6k+1) by (6k-1) number that the result after adding 2 can be a possible prime, and will always be of the form 6k+1
Note also that if 3 is one of the primes in your set, then the final result before adding 2 is of form (6k+/-1) x 3, which is of course an odd multiple of 3, so adding 2 will always produce a number of the form 6k+5, aka 6(k+1)-1, which is a possible prime.
Of course, you would still need to perform the multiplications and factor the composite numbers and add them to your set, but in terms of turning it into a proof, the above analysis is much more useful as it doesn’t depend on performing infinite operations.
18:21 An interesting note on the proof that there is no polynomial that can generate primes is that the proof he showed actually also proves that, if f is a polynomial and f(1) = n for some natural number n, then for all naturals m, f(1 + mx) is a multiple of n. It doesn't actually matter here whether or not x is prime, all that matters is f is a polynomial and f(1) is a natural number.
This actually is kind of a surprising result at face value. You would think that, just maybe, you could find a polynomial f(x) such that f(1) = 6 but f(1 + m6) is not a multiple of 6 for some m. But no matter what polynomial you try if f(1)=6 then f(7), f(13), f(19), etc are all multiples of 6 too.
Another way to prove this by the way would be to assume f(1) = n then consider f(1 + mn) mod n. Then f(1) = 0 mod n. But note that all the non-constant parameters in f will then be the same mod n as when you put in 1 mod n, and the constant in f will still be the same constant, so the result will be identical mod n to f(1), which means it will be 0 mod n.
Professor Michael Penn, thank you for a fantastic lecture/video on Proofs and Conjectures involving Primes. I watched and took notes on all 123 videos, and they were all incredible. I took an undergraduate class in Number Theory at the University of Maryland College Park in the early 1990's and it was a mess. I did not learn a single thing from the instructor. Over the years, I had to review the class on my own, to finally understand the basic material.
Is it possible for you to share your notes for other's benefit? Thanks.
12:08
- if |a0| > 1, f(a0) is the non prime (factoring with |a0|)
- if a0 = 0, (f(n) is the non with any n st |n|>1)
if a0 = ± 1 (f(0) is the non prime)
2^(2^n)+5 problem can be nicely solved using induction.
We want to prove that 2^(2^n)+5 is always divisible by 3 for n >= 1
we check the base case (n=1) 2^(2^1)+5 =9= 3*3
which holds.
In the induction hypothesis we assume that this property holds for some natural number
k which means that 2^(2^k) + 5 = 3d, where d is a natural number
so 2^(2^k) = 3d -5
then 2^(2^(k+1)) + 5 = (2^(2^k))^2 + 5 = (3d-5)^2 +5 =9d^2 -30d + 25 + 5 =
9d^2 - 30d + 30 = 3(3d^2 -10d + 10)
For the last exercise, here's my solution:
First try to put some number into n, like 0, 1, 2, 3...And in each cases, we have
n=0: 7 (prime)
n=1: 9 (not prime)
n=2: 21 (not prime)
n=3: 261 (not prime)
....
And notice that when n is larger than 0, the result is always divisible by 3. So then I proved it via Mathematical Induction.
Base case: n = 1, which equals to 9, is divisible by 3.
Inductive Hypothesis: for some k > 1, 3 | 2^{2^k} + 5, which means 2^(2^k) = 3m-5.
Now for the case of k + 1 we have, 2^{2^{k+1}} + 5, and 2^(2^{k+1}) = (2^{2^{k}} )^2. Then the expression can be rewritten as (3m-5)^2+5. By expandng this we can see that it equals to (9m^2-30m+30) = 3(3m^2-10m+10). And it's again can be divided by 3. Which completes the proof.
12:30 So this is like a really...
His soul proceeds to abandon his body
The man needs his thoughts to be shared in precise form. Seems like a mathematician to me.
@@jasonroberts2010 yeah I know, it usually happens, he just didn't edit it haha
The second proof is so cool
I think the twin prime type result (from Yitang Zhang and Polymath 8 I think) is that it's been shown that there exists an even integer N
I thought the bound on N has gone down to like, 8
@@romajimamulo The bound on N can be reduced under the assumptions of other, yet unproven conjectures. One such conjecture, if true, brings the bound to 6.
Hi,
For fun:
2:22 : "great",
6:28 : "and so on and so forth",
6:56 : "so on and so forth",
7:30 : "and so on and so forth".
Can you make video on merrene numbers and some special numbers and their properties
That Euler's Proof of infinite many primes, could you break down the arithmetic steps after writing M?
19:30 In the Fermat Prime proof why is p|n and p = odd prime equivalent to ¬(n=0 or n = 2^k)?
23:06 - In mostly cases, is that what happens, as GIMPS can attest.
At 11:30 ish, shouldn't it be that there's a list of *at least* n composite numbers, since (n+1)! + (n+2) might also be composite? E.g. for n=4 you have 5! + 6 = 120 + 6 = 126, which is composite.
For the proof of the no-constant polynomial thing, if we let f(x)=a_nxˆn+...+a_1x+a_0 (a general polynomial with integer coefficients), then we know that f(a_0) will be divisible by a_0, and thus not a prime. For the case where a_0 = 0, x will divide f(x) for all x. Now if it just so happens that a_0 = 1, we can look at g(x)=f(x+1), which if f(x) always yields primes will, surely also yield only primes. If we expand f(x+1) we see that the constant term of g(x), b_0, is NOT 1, and since b_0 divides g(b_0), it is not a prime, thus we get a contradiction!
in the last expression 3 divides al such numbers. Bcoz 3|2^2^n-1
I think k should start at 0. Polynomials can have constant terms. For the proof of the generating functions.
Can you do something on semiprimes? Very little content related to it on youtube.
Does anybody have a solution to homework #2 without using modular arithmetic? The only I found involves mod 3 and I want a solution using “current knowledge” built from previous videos.
Yes. 2^2^n = 2^(2*2^(n-1)) = 4^2^(n-1) = (1+3)^2^(n-1). If n>0, we can expand that as a binomial = 1 + 2^(n-1).3 + ... But all of the terms except the first one contain a power of 3 and are therefore divisible by 3.
That means 2^2^n always leaves a remainder of 1 when divided by 3 for all n>0. Then it is clear that for n>0, 2^2^n + 5 leaves a remainder of 0 when divided by 3, so cannot be prime. It avoids using modular arithmetic, _per se,_ but is the same reasoning.
@@RexxSchneider Thanks. This is what I was looking for, I see now that it is kind of the same process, splitting 4 into 1 + 3 and binomial expansion. What I argued was that if 4 ≡ 1 (mod 3), then 4^k ≡ 1^k (mod 3) for any natural number k, but 1^k = 1 (obviously if k = 2^(n-1), this only holds for k > 0).
@@infopek3221 That's exactly right, and precisely how it would be done using modular arithmetic. Well done!
Which book should I follow to learn Number Theory
MONT by Aditya Khurmi. There's a link on AoPS and it's free
The second proof that M should be the infinite sum of the harmonic series is wrong: if there existed a biggest prime then there would be holes in the sum. Thus it would not anymore be proven that M is infinite. Let‘s suppose 5 was the biggest prime then there would be no terms of (1/7), (1/11) etc. and no powers of them in the series.
Maybe there is a kind of formula to find a prime. Multiplying the first n primes and add one, you will get a bigger prime. Unfortunately doesn't work to find the primes between 😬
E. G. 2*3*5*7 + 1 must be prime
excuse me, but 2*3*5*7*11*13+1 = 30031 = 59*509 is the smallest counter example...
you won't always get a bigger prime, but might get a number that is divisible by a bigger prime!
@@karl131058 you got me... Good point 👍
2, 4, 6, 10 all fail the Goldbach conjecture (unless you allow 3+3 in which case every even number is n/2 + n/2)... what am I missing?
2 is prime so an exception
You have to use only primes
2+2=4
3+3=6 (but 2+4 is not allowed)
5+5=10
But you can't do 6+6 for 12, you have to do 5+7 so they're primes
@@romajimamulo In that case, the two summands must be n/2-m and n/2+m; the question is whether these both must be composite for 0
Prove, except 3 all other Mersenne primes end with 1 or 7.
all primes greater than 2 are odd
if 2^n - 1 is prime n is prime
if n is odd 2^n is congruent to 2 or 8 mod 10.
For proof 1…why can’t we just assume largest prime P…then P!+1 would either BE prime or have a new prime factor > than P??
Very entertaining video. The topics are laid out in a very clear and neat way.
At 13:40, "sort of m times p for obvious reason", well it is not obvious to me, and as an educator you should not make such an assumption, just be direct and to the point.
Unless, n=0 this object:- 7 is prime!
The first proof should be "all and only primes are the list..."
The powers in the binomial sum is not correct. Needs some adjustment.
OK, so as a Physics student I took all these math classes. I did benefit from them in how I learned to think, but never actually used abstract algebra and number theory proofs in my work in Physics.
Why is it that when Euclid or somebody proved that there are an infinite number of primes, people were cool with it, but when Gödel proved that there are an infinite number of axioms, people lost their heads?
Because Godel’s Incompleteness theorem challenges the notion that we can know anything with certainty, and people cling to having certainty and “knowing the truth”. To assert that we can’t know with certainty is very confronting, it creates cognitive dissonance and that triggers fear for many people.
To be more accurate, Euclid had no notion of "infinitely many". He proved that given any set of primes, there is a prime not in that set (proved the way Michael proved it). Euclid then inferred that there are arbitrarily large sets of primes. But he didn't make the next conceptual leap to "infinitely many".
Godel's result is stronger than the result that some theories cannot be finitely axiomatised. He proved that every (consistent) axiomatisation is incomplete. So, even with theories with infinitely many axioms, incompleteness remains. People were cool with infinitely many axioms -- but when it was found that even those theories were incomplete, that's when people lost their heads.
Why does a polynomial having infinite of its values getting mapped to the same value imply the polynomial is constant?
You can show that this gives a polynomial infinitely many roots, and thus must be a contradiction
Consider such a polynomial f(x) that achieves the same value C for infinitely many inputs x_1, x_2, etc. Look at the polynomial g(x) = f(x) - C. g(x) now has infinitely many roots at each x1, x2, etc. This is because g(x_j) = f(x_j) - C = C - C = 0.
This is a contradiction because polynomials only have finitely many roots
@@stevenschaefer7314 great explanation!
Thanks
@@stevenschaefer7314 p
Technical logical question: isn't proof by contrapositive really the same as proof by contradiction? You're assuming the opposite of the thing you're trying to prove, and proving a contradiction-in this case contradicting the assumption. Why call them two different things?
Because while the contropositive is logically equivalent to the negation, they are different.
The contropositive of A then B is B then A.
@@romajimamulo The contrapositive of (A then B) is (not B then not A).
@@Macieks300 oh. Wait . Then I labeled a few things wrong and it's too early in the morning to figure out which
Proof by contrapositive relies on the fact that A=>B ~B=>~A. Both statements are equivalent, but it is sometimes easier for practical purposes in a particular problem to assume ~B and show that ~A follows, rather than assuming A and showing that B follows.
By contrast, a proof by contradiction begins by assuming A is true, and a contradiction follows, thus demonstrating that the assumption is false, i.e., ~A is true.
Notice a key distinction. In a contrapositive proof, we do NOT disprove our assumption. We show simply that IF ~B, then ~A follows. That does NOT mean that A is logically impossible or that we have contradicted the truth of A, and importantly, it does NOT show that ~B is true. Indeed, if A is true, then so is B (which likewise says nothing about the truth value of A). By contrast, following a proof by contradiction assuming A, we conclude that A cannot be true no matter what, thus proving ~A.
@@simonreiff3889 thank you for explaining way better than I did
Where in proof #2 is the fact, that we are looking on prime numbers? It could be everything else....
If you include zero among the possible values of n in 2^2^n + 5 , then n=0 gives the only prime of that form, 7.
If you don't, then there are no primes of this form because 2^2^n is equal to 4^2^(n-1) , so for n greater than or equal to 1, 2^2^n + 5 is always equal to zero mod 3 .
(Generally, 2^2^n + 2 + any multiple of three is never prime.)
Lists of conjectures should not be framed as questions. It is not immediately clear for the audience whether the conjecture is conjectured to be true or false, making it look more like a list of open questions.
except your strong math ability, i also notice your strong back muscle😁
Uhm... There are prime-number enumerating formulas. Sieve of Eratosthenes is the most ancient one.
@@last3239 it's not an algorithm either as it doesn't terminate