6
$\begingroup$

I was trying to think of another way of showing that there are an infinite number of primes. I came up with the following argument, but I am not sure if it is valid. I don't know how to make it more formal (I'm not a mathematician). The basic approach I'm attempting is to assume that there are a finite number of primes, and then to show that a finite set of prime numbers cannot be combined to produce every natural number in some arbitrary set of natural numbers. Thus, some natural numbers would be neither prime nor composite, but since every natural number is in fact either prime or composite, this creates a contradiction and thus there are infinite primes.

Let $P$ be the set of all primes $\{2,3,5,...p_m\}$ and let $S$ be the set of all natural numbers between $1$ and $p_m^n$ (i.e. $\{1,2,3,...,p_m^n\}$), where $n$ is a natural number. Note that $P$ is a subset of $S$. Every element of $S$ is either prime, or can be written as a product of primes. We can think of each number in $S$ as a product of every prime in $P$, each raised to an exponent of $\ge0$. For instance, $10=2^1*3^0*5^1*7^0*11^0*...p_m^0$.

Let $a$ be a whole number such that $2^a < p_m^n$ and $2^{a+1}>p_m^n$. In other words, $a$ is the greatest power of $2$ that is smaller than $p_m^n$. Since exceeding the power of $a$ for the smallest prime would be greater than $p_m^n$, it follows that any other prime number raised to a power $>a$ would also exceed $p_m^n$. This sets the upper bound for exponents in the prime factorization of any element of $S$, therefore the prime factorization of any element of $S$ will contain only powers of primes $\le a$.

Every element of $S$ can therefore be written as $2^{q_1}*3^{q_2}*5^{q_3}*...*p_m^{q_m}$, where $0\le q \le a$. Let $C$ be the set of every possible combination of the above. Since there are $m$ primes, and each prime can have an exponent from $0$ to $a$, there are therefore $(a+1)^m$ numbers that can be generated in this way (these numbers include composite and prime numbers, since the primes are formed when a single prime has a power of $1$ and every other prime has a power of $0$). Note, $S$ must be a subset of $C$ since every element of $S$ can be represented in this way, but $C$ contains elements that are clearly $> p_m^n$ and thus those elements are not in $S$, i.e. $p_m^a$ where $a$ is clearly larger than $n$. Since $S$ is a subset of $C$, then $S$ must have fewer elements than $C$:

1) $|S| < |C|$

since $|S| = p_m^n$ and $|C| = (a+1)^m$

2) $p_m^n < (a+1)^m$

If the above statement is true, then replacing $a+1$ with a value greater than $a+1$ should also be true. Since $2^a<p_m^n$ by definition, multiplying both sides by 2 gives:

$2^{a+1}<2p_m^n$

Taking the $log_2$ of both sides:

$a+1<log_2(2p_m^n)$
$a+1<log_2(2) + nlog_2(p_m)$
$a+1<1+nlog_2(p_m)$

Now replacing $a+1$ in equation 2) with $1+n*log_2(p_m)$:

$p_m^n < [1+n*log_2(p_m)]^m$

Clearly if this inequality holds for any value of $n$, it does not do so for all values of $n$. The left side grows exponentially as $n$ increases. The right side is a polynomial of the form $(1+bn)^m$ where $b$ and $m$ are constants. Thus for sufficiently large $n$, the inequality fails. Since the inequality is false for at least some values of $n$, then $|S|$ must be sometimes larger than $|C|$, which means there must exist elements of $S$ that are not contained within $C$. These element would be neither prime, nor composite. However, all natural numbers must be either prime or composite, thus there exists a contradiction and the proposition that there are a finite number of primes must be false.

I challenged myself to construct a proof that there are infinite primes before looking at any existing solutions. I have since looked, and while this is not very elegant, I wonder if it is actually valid. I would appreciate any feedback.

$\endgroup$
  • $\begingroup$ It looks alright! $\endgroup$ – baharampuri May 1 '17 at 8:48
  • $\begingroup$ This looks good to me. Nice! (+1) $\endgroup$ – Jair Taylor May 1 '17 at 8:48
  • $\begingroup$ I'm thinking now that $|C| = (a+1)^m$ but I don't think that changes the proof in any substantial way. $\endgroup$ – Chris Michael Sullens May 1 '17 at 9:02
  • $\begingroup$ You defined $a$ to be such that $2^a<p_m^n<2^{a+1}$. Are you allowed to replace $a$ by a larger value ? $\endgroup$ – Yves Daoust May 1 '17 at 10:29
  • $\begingroup$ I think this argument can be modified to show a minimum frequency of primes as well. I.e, for a given $m$ there is an $n$ such that increasing $n$ by 1 will invalidate the inequality. At that point, m must be increased to compensate to preserve the inequality, thus indicating the need for additional primes to be contained in the set. Primes could be more frequent than this, but they could not be less frequent. $\endgroup$ – Chris Michael Sullens May 1 '17 at 16:23
0
$\begingroup$

Apart from some minor details ($0$ to $a$ is $a+1$ different exponents so there are actually $(a+1)^m$ numbers in $C$, like you commented yourself), this seems correct, but unnecessarily complicated as anything but a purely intellectual exercise in creating proofs and familiarising oneself with natural numbers, primes and factorisations of natural numbers..

$\endgroup$
  • $\begingroup$ There's nothing wrong with a 'purely intellectual exercise'. Most of mathematics fits under this category. Having different proofs of the same statement can reveal different perspectives which can be very fruitful. I do not think the proof is unnecessarily complicated, although it could be compressed. $\endgroup$ – Jair Taylor May 1 '17 at 13:40
  • $\begingroup$ I would be interested to know if there are any other details that you noticed that were wrong so I can correct them. If you see a way to simplify the argument, I would love to see that as well. $\endgroup$ – Chris Michael Sullens May 1 '17 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.