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:


    If you know of any more, please let me know! In particular, I am really hoping for a proof from homological algebra.
  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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Infinitude of primes
  1. Product of primes (Replies: 10)

  2. Germain primes (Replies: 1)

  3. Prime numbers (Replies: 8)