1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinitude of primes

  1. Apr 2, 2008 #1
    Hi all,

    I am for some reason interested in creative or weird proofs of the fact that there are infinitely many prime numbers. I have started writing down all of the proofs that seemed sufficiently different in the following file:

    http://www.ocf.berkeley.edu/~ssam/primes.pdf [Broken]

    If you know of any more, please let me know! In particular, I am really hoping for a proof from homological algebra.
    Last edited by a moderator: May 3, 2017
  2. jcsd
  3. Apr 3, 2008 #2


    User Avatar
    Homework Helper

  4. Apr 3, 2008 #3
    I wrote a proof a few months ago, I will post it here when I get home.
  5. Apr 3, 2008 #4
    Suppose there are only n primes, and they are [tex] p_1 ... p_n [/tex] these are all greater than or equal to 2.

    every number <= 2^k will be a product of powers of prime numbers, and all those powers have exponent <=k because all primes are at least 2. Those products thus have the form

    [tex] \prod_{i=1}^{n} p_i^{a_i} [/tex]

    with [tex] a_i <= k [/tex]

    There are at most [tex] k^n [/tex] such products. for sufficiently large k, [tex] 2^k [/tex] will be larger than [tex]k^n[/tex], so there must be numbers that are not a product of these primes.
  6. Apr 3, 2008 #5
    There are also plenty of proofs involving modular arithmetic, e.g. proof that there are infinitely many primes 3 modulo 4:

    Quite evidently, any number 3 modulo 4 must have a prime factor that is also 3 modulo 4. Supposing there is a finite number of primes 3 modulo 4, we consider

    [tex] q = \prod_{p\equiv\mbox{3 (mod 4)}}^{} p[/tex]

    If q = 3 (modulo 4), then we reach a contradiction by showing that no prime 3 modulo 4 divides into q + 4, if q = 1 (modulo 4), we reach a contradiction with q + 2.


    Also, you can look at different proofs of the divergence of the sum of the primes' reciprocals.
    Last edited: Apr 4, 2008
  7. Apr 4, 2008 #6
    The promised proof:

    Suppose there is a finite number of primes, n. Consider the integer [tex]m = 2^{2(n+1)} [/tex]. Of course, m > n. Now, for every integer [tex]1 \leq k \leq m[/tex], factor out its largest square factor, so to express k as [tex]ab^{2}[/tex] where in the prime factorization of a, the exponents are either 0 or 1. Because there are only n primes, there are only [tex]2^n[/tex] possible values for a. Also, since [tex] b^2\leq2^{2(n + 1)}[/tex], we get [tex]b\leq2^{n+1}[/tex], so there are at most [tex]2^{n+1}[/tex] possible values for b and b^2 consequently. Since [tex] k = ab^{2}[/tex], it follows that there are at most [tex]2^{n}2^{n+1} = 2^{2n + 1} < m [/tex] possible values for k. But k has been said to be any integer from 1 to m; contradiction. So our assumption that there is a finite number of primes is false.
    Last edited: Apr 4, 2008
  8. Apr 4, 2008 #7
    http://sums.mcgill.ca/delta-epsilon/mag/0610/mmm061034.pdf [Broken]
    Last edited by a moderator: May 3, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook