Infinite number of primes :)


In today’s post , I will present a very well known proof. What makes this proof especially appealing is that it is not too complex. Even so, it is very powerful. This theorem was first presented in Euclid’s Elements (Book IX, Proposition 20).

Theorem: There are an infinite number of primes.

Proof:

(1) Assume that there is only a finite number of primes.

(2) Then, there exists a prime pn that is the largest prime.

(3) Let p1, p2, …, pn be the list of all primes that exist.

(4) Let x = p1*p2*…*pn + 1.

(5) By the fundamental theorem of arithmetic (see Theorem 3, here), we know there is at least one prime that divides x. Let us call this prime p*.

(6) But none of the primes p1 … pn divide x since x ≡ 1 (mod pi) for any of the primes p1 … pn

(7) Therefore, we have a contradiction. We have a prime p* that is not in the complete list of primes.

(8) So, we reject our assumption in step#1 and conclude that there are an infinite number of primes that exist.

QED

Advertisements

About shivang1729

I am a young student who loves math . I like number theory and inequalities part the most , and preparing for Math Olympiads :)

Posted on Tuesday,July 3, 2012, in Uncategorized and tagged , , , , , . Bookmark the permalink. 28 Comments.

  1. Good read, I just passed this onto a colleague who was performing slightly research on that. And he just bought me lunch since I identified it for him smile So let me rephrase that: Thank you for lunch! 836444

  2. I love your insightful blog. brilliant contribution. I hope you produce more. I will continue reading

  3. Hi there! Nice stuff, please do tell me when you finally post something like this! 413033

  4. Spot on with this write-up, I actually assume this site wants way a lot more consideration. Ill probably be once a lot more to read far a lot more, thanks for that information. 153578

  5. This will likely be a fantastic internet web site, will you be involved in performing an interview regarding how you developed it? If so e-mail me! 177845

  6. I saw your post awhile back and saved it to my computer. Only recently have I got a chance to checking it and have to tell you nice work. 541250

  7. Thanks thanks 🙂
    This is all for you.. 🙂
    Thanks for the work 🙂

  8. dress shops that offer discounts are quite common in our spot and i always shop at them,. 612440

  9. It is truly a terrific and valuable piece of information. Im pleased which you just shared this beneficial information with us. Please stay us informed like this. Thank you for sharing. 778098

  10. I dont leave a lot of comments on a lot of blogs each week but i felt i had to here. Do you need many drafts to make a post? 196253

  11. Hello DropshipDragon provides dropping for quality, affordable products direct from China to your customers. Perfect for eBay sellers and website owners alike! 173725

  12. hey there i stumbled upon your internet site looking about the internet. I wanted to let you know I enjoy the appear of items about here. Maintain it up will bookmark for confident. 350028

  13. Im impressed, I ought to say. Genuinely rarely do you encounter a weblog thats both educative and entertaining, and let me let you know, you could have hit the nail about the head. Your concept is outstanding; ab muscles something that too couple of men and women are speaking intelligently about. Im delighted i identified this in my hunt for something about it. 916066

  14. Really superb details can be located on weblog . 459281

  15. Some truly good stuff on this internet web site , I like it. 455002

  16. document imaging services

    Awesome inkling Grace! ego was luxurious youd bring about this about your biz bump into upstanding lineage. We reason you! 834231

  17. Enjoyed reading this, extremely great stuff, thankyou . 690219

  18. Deference to internet site author , some wonderful entropy. 505054

  19. I like this site really significantly so significantly superb details. 355012

  20. Some genuinely intriguing details, properly written and broadly user pleasant. 623296

  21. I enjoy your writing style truly enjoying this internet web site . 613765

  22. Yeah bookmaking this wasnt a risky determination outstanding post! . 955946

  23. What host are you the use of? Can I am getting your associate link for your host? I desire my website loaded up as fast as yours lol 372369

  24. Why didnt I take into consideration this? I hear exactly what youre saying and Im so pleased that I came across your weblog. You genuinely know what youre talking about, and you produced me feel like I really should learn far more about this. Thanks for this; Im officially a huge fan of your weblog 508899

  1. Pingback: URL

  2. Pingback: visit website

  3. Pingback: kitchen countertop

  4. Pingback: read more

Comments / doubts/answers here:

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: