Infinitely Many Primes & Why I DON'T Like Euclid's Proof

This video is all about why I dislike Euclid's classic proof that there are infinitely many primes. I present two different proofs of the infinitude of primes that are more methodical rather than random.

#InfinitelyManyPrimes #InfinitudeOfPrimes #EuclidInfinitePrimes

GET MY BOOK ON AMAZON!!
========================

"Number Theory Towards RSA Cryptography in 10 Undergraduate Lectures"

CHECK OUT OTHER TYPES OF VIDEOS:
================================

Improve Your Putnam Math Competition Performance:

------------------------------------------------------
Math Theorems:

------------------------------------------------------

GRE Math Subject Test:

------------------------------------------------------

Road to RSA Encryption:

-------------------------------------------------------

CHECK ME OUT ON THE INTERNET!!
==============================

Twitter: @mohamedomarphd
Instagram: profomarmath

And of course, subscribe to my channel!

[goodplacetostop]

18:20 I like the last proof a lot, very interesting... but I’m not gonna lie, I still prefer Euclid proof.

[hrs]

Great video !
You always have A+ content for us

I’ve got few more proofs
(Euler) suppose there are only finitely many primes
{p1, p2, p3, ...}
Product(i=1, k) 1/1-(p_i)^-1 = product(i=1, k) (1 + 1/p_i + 1/(p_i)^2+...) = sum(1/n)
And we know sequence of harmonic number diverges
Thus a contradiction

There also one which is essentially generalisation of Euclid’s proof
What you do is partition the ‘finite’ set of primes into A and B
Construct N = Product of primes in A + product of primes in B
Notice that non of the primes from A union B (entire set of primes) divide N

There is also one where you use the fact that gcd(a^(2^n)+1, a^(2^m)+1) = 2 (if a is odd) 1 else
you can also deduce from here there are infinitely many primes
I’ve also heard there is a very nice topology proof for infinitude of prime but I am yet to take that course

[owainthorp]

There's also a really cool proof with Fermat numbers that I suggest people check out.

[thedoublehelix]

Wow that's actually super cool! I'm definitely going to switch from always going for the standard proof to experimenting with different ones.

[kapoioBCS]

I really don’t thing this number is out of nothing; you just searching for the existence of bigger prime number from the primes of your finite set

[coycatrett]

furstenberg’s topology proof is my all time favorite but i really enjoyed these two and had never seen them before

[antormosabbir]

First time knowing different proofs of this famous problem!

[JPiMaths]

Wow... Great video! I hadn't seen either of those proofs before, and I was amazed!!! ++ I love intuitive proofs - it's very difficult to motivate a proof that has a seemingly magic 'moment of brilliance' step in it

[yashvardhan]

Really loved both the proofs .
Felt very happy after seeing them.

[deepjyoti]

Ya true, in euclid proof when i studied i cannot able to think how he think of constructing that number.


Nycc vedio

[TheEternalVortex]

I like the combinatoric proof (I think it's from Erdos), which I guess is basically the same as your first proof, just stated differently:
Each natural number n can be written as a^2 b, where b is squarefree. Observe that there are at most sqrt(n) choices for a. Now assume there are only M primes. Since b is a product of distinct primes, there are 2^M choices for b. Therefore the number of possible choices for a^b is sqrt(n)2^m, and there must be at least n of these. So n <= sqrt(n)2^m and we can rearrange to get n <= 2^(2M). But this must be true for all n, which is clearly impossible if M is finite.

I like this one because it kind of explains *why* there have to be infinitely many primes. If there weren't then we wouldn't have "enough" primes to construct all the natural numbers.

I also like Euler's proof based on diverge of the 1/p series although it's more complicated to state.

[yoyokojo]

My favorite proof uses group theory and langranges theorem:
asume there exists a largest prime p, consider the number 2^p-1, we will show, that every prime divisor q of this number is larger than p giving a contradiction.
if q is a prime dividing 2^p-1, then 2^p=1 (mod q). since p is a prime we have that the multiplikative order of 2 in Z_q is p.
by lagranges theorem the order of the group generated by 2 is a divisor of the order the multiplaktive group Z_q which has order q-1. hence we have that p divides q-1 and therefor p<q which completes the contradiction.
Edit: but yeah 2^p-1 seems even more out of context then Euclids number

[TheEternalVortex]

Here's another fun proof, which is a generalization of Euclid's. Let a_n be a sequence which is pairwise relatively prime (and > 1). Then for each a_i pick any prime divisor of a_i. These must all be distinct, thus there are infinitely many primes.

Of course we need to exhibit that at least one such sequence exists. Actually Euclid's sequence is one such example, i.e. a_1 = 2, a_2 = 2 + 1 =3, a_3 = 2*3 + 1 = 7, a_4 = 2*3*7 + 1 = 43, and so on.

[riyaghosh]

i have one question about the proof using the logarithm function, are you entirely sure that in the construction of real numbers( from natural/integer to rational to real numbers) the fact that there are infinitely prime numbers is never used, i am asking this because log function is defined only after having defined the real numbers.

[tracyh]

14:10 This only shows that the period of f1+f2 divides p1p2. The actual period should be lcm(p1, p2). This won't be a problem for prime numbers or the remaining argument though.

[matthartley]

What isn't intuitive about creating a number congruent to 1 mod every single prime? It's way more intuitive than "the sum of two functions with integer periods is itself periodic" or looking at bounds on exponents for no reason and relating it to a function that comes out of nowhere. And then you have to take care of less than signs, which is always the least intuitive part of proofs.

[maximusideal]

Personally I disagree. I found it natural to multiply all the primes together and add one. However, I do see your point, and now that I think about it I have seen some people struggle with the proof.

[kingplunger]

You are right. While some proofs are short and very beautiful, they don't really help the people trying to learn math. Maybe motivate and they can be very satisfying, but systematic approaches can also be applied to other problems and most people will probably get more out of those, even though they aren't as pretty. Edit: The second is great

[xCorvusx]

Thank you for introducing different proofs for this theorem. These new perspectives on a known thing are always elucidating.
However, while your first proof requires an understanding of limits and the logarithm, Euclid's proof is more basic and I have doubts whether it really isn't about as straightforward as your two proofs, just starting from a different perspective.
That perspective includes an approach from the number theory side, i. e. knowing that every natural number either is or is not a prime number, and Euclid's historical context where infinity was not a common concept (likewise, one may do without it in modern classrooms). Euclid didn't claim that there are infinitely many prime numbers but that for any given set of prime numbers there exists another prime number not in that set.
I am not very far in my study of physics (and mathematics) and don't know much about teaching but since prime numbers are usually introduced as the "elementary particles of the natural numbers", so to speak, it does seem relatively straightforward to me to try to construct new numbers with the given primes: this endeavour would either yield all the naturals without the need for more primes or new primes as one finds natural numbers that cannot be composed from the given primes.
Therefore Euclid's proof should be easy to follow, straightforward, at least once one gets to the point where the question how many prime numbers exist arises.
It may even be particularly well suited for a mathematics course since it is a generalization of naive attempts to construct new numbers with example sets of primes.

However, my mind may be tainted by being introduced to the infinitude of primes with Euclid's proof or a proof phrased slightly differently but pursuing the same strategy.

Edit: though, that second proof is a really interesting rephrasing (if it isn't more than that) of Euclid's proof.
Just my couple of cents.

[theproofessayist]

ah yeah i=0 would imply you have no primes - or maybe you'd need to explicitly state i \in{1, k} where [1, k]\in\doubleZ (the integers)