# Infinitude of primes

1. Apr 2, 2008

### masnevets

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. Apr 3, 2008

3. Apr 3, 2008

### Werg22

I wrote a proof a few months ago, I will post it here when I get home.

4. Apr 3, 2008

### kamerling

Suppose there are only n primes, and they are $$p_1 ... p_n$$ 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

$$\prod_{i=1}^{n} p_i^{a_i}$$

with $$a_i <= k$$

There are at most $$k^n$$ such products. for sufficiently large k, $$2^k$$ will be larger than $$k^n$$, so there must be numbers that are not a product of these primes.

5. Apr 3, 2008

### Werg22

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

$$q = \prod_{p\equiv\mbox{3 (mod 4)}}^{} p$$

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.

Edit:

Also, you can look at different proofs of the divergence of the sum of the primes' reciprocals.

Last edited: Apr 4, 2008
6. Apr 4, 2008

### Werg22

The promised proof:

Suppose there is a finite number of primes, n. Consider the integer $$m = 2^{2(n+1)}$$. Of course, m > n. Now, for every integer $$1 \leq k \leq m$$, factor out its largest square factor, so to express k as $$ab^{2}$$ where in the prime factorization of a, the exponents are either 0 or 1. Because there are only n primes, there are only $$2^n$$ possible values for a. Also, since $$b^2\leq2^{2(n + 1)}$$, we get $$b\leq2^{n+1}$$, so there are at most $$2^{n+1}$$ possible values for b and b^2 consequently. Since $$k = ab^{2}$$, it follows that there are at most $$2^{n}2^{n+1} = 2^{2n + 1} < m$$ 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
7. Apr 4, 2008

### Dragonfall

http://sums.mcgill.ca/delta-epsilon/mag/0610/mmm061034.pdf [Broken]

Last edited by a moderator: May 3, 2017