Apparently there is a way that I can use the fact that for any positive integer $n$ there are positive integers $a$ and $b$ such that $n=a^2b$ where $b$ is the possibly empty product of distinct primes (i.e squarefree?) to show that there are infinitely many primes.

My current tactic (the one that was hinted to me) was to fix x then assuming there are a finite number of primes show that there are only a finite number of possibilities for $n=a^2b$ knowing that $a^2 \leq b$

I believe it is mostly that last part that causes me issues as I am not sure how we can only consider $a^2$ and not $b$. I also assume that I have to do something with divisibility here though I am not sure what. I can't help but think that the overall approach is reminiscent of Euclid's though I am not sure?

  • 1
    $\begingroup$ Hint: For the $i^{th}$ prime $p_i$ Let $N_i(x)$ be the number of positive integers less than $x$ which are not divisible by any prime greater than $p_i$. Use your decomposition to get an upper bound on $N_i(x)$. Derive a contradiction from the assumption that $p_i$ is in fact the largest prime. $\endgroup$ – lulu Mar 30 '17 at 13:26
  • $\begingroup$ To get the upper bound do I use the fact that a^2 divides n? $\endgroup$ – John O'Neil Mar 30 '17 at 14:46
  • $\begingroup$ Oh, no. It's a lot simpler than that...no divisibility involved. Every $n<x$ which is built out of the first $i$ primes can be written as $r^2s$ where $r≤\sqrt x$ and $s$ just has each of the first $i$ primes either to the power $0$ or the power $1$. So now just count. $\endgroup$ – lulu Mar 30 '17 at 14:48
  • $\begingroup$ Euclid proved it as follows : $(1)$ Every integer $n>1$ is divisble by some prime $p$. Prove : The set $S$ containing the positive divisors of $n$ greater than $1$ is not empty because of $n|n$. The smallest element , denote it with $m$, must be a prime, because if $a$ is a divisor of $m$ with $1<a<m$, it is also a divisor of $n$ greater than $1$, but smaller contradicting that $m$ is the smallest element in $S$. $(2)$ If $2,3,5,\cdots ,p_k$ are all the primes, the number $2\cdot 3\cdot5\cdots \cdot p_k+1$ is not divisble by any prime, contradicting $(1)$ $\endgroup$ – Peter Mar 30 '17 at 22:33

Here is an elementary solution.

Let $p_i$ denote the $i^{th}$ prime. For any natural number $x$ let $N_i(x)$ denote the number of natural numbers $≤x$ which are not divisible by any prime greater than $p_i$.

We want a (crude) upper bound on $N_i(x)$. To get it, note that any $n≤x$ which is only divisible by primes in $\{p_1,p_2,\cdots, p_i\}$ can be written as $$n=m^2\prod_{k=1}^i p_k^{\epsilon_k}$$

Where $\epsilon_k$ is either $0$ or $1$ for each $k$. Thus there are $2^i$ ways to assign the $\epsilon's$ and as $m≤\sqrt x$ we get $$N_i(x)≤\sqrt x\;2^i$$

Note: This holds whether there are infinitely many primes or not (it's quite crude).

Now suppose that there are only finitely many primes, and that in fact $p_i$ is the largest possible prime. In that case of course $N_i(x)=x$ Thus $$x≤\sqrt x\;2^i\implies \sqrt x ≤ 2^i$$ for all $x$, which is absurd.

Note: as far as I know this is one of the easiest ways to get an (admittedly crude) lower bound on the number of primes less than $x$. Playing with the above inequality gives us $$\pi(x)≥ \frac 12\log_2(x)$$

This is a terrible lower bound, but at least it's something.

  • $\begingroup$ This is fantastic. I believe I understand what is going on. Just to clarify though It is absurd because x is defined to any natural number and we are saying that is less than $2^i$ for some i? And this is probably a stupid question but how can we know that that inequality cant hold if for every x we choose an i? $\endgroup$ – John O'Neil Mar 30 '17 at 15:30
  • $\begingroup$ $i$ is fixed because, under the assumption that there are only finitely many primes, I can choose $p_i$ to be the largest possible prime. Nothing to do with $x$. In that case then, yes, we'd be free to let $x$ be arbitrarily large. $\endgroup$ – lulu Mar 30 '17 at 15:32

If you know that every positive natural number can be written as $a^2 b$ with $b$ being the product of distinct primes (not dividing $a$), just assume that there are just $M$ primes $p_1,p_2,\ldots,p_M$ and consider $$ \sum_{n=1}^{N}\frac{1}{n} \tag{1}$$ for some large $N$. It is well known that such sum behaves like $\log(N)$. On the other hand, every $n\in[1,N]$ can be written as $a^2 b$ with $a\leq \sqrt{N}$ and $b$ being the product of the elements of a (possibly empty) subset of $\{p_1,\ldots,p_M\}$. In particular:

$$ \sum_{n=1}^{N}\frac{1}{n} \leq \sum_{a\leq \sqrt{N}}\frac{1}{a^2} \prod_{k=1}^{M}\left(1+\frac{1}{p_k}\right)\leq \zeta(2)\cdot C_M\tag{2} $$ is bounded by an absolute constant, depending on $M$ only.
But the LHS of $(2)$ is arbitrarily large, hence the set of prime numbers cannot be finite, qed.
Indeed $(2)$ can be used to prove a very weak form of the prime number theorem: $$ \sum_{\substack{p\text{ prime}\\p\leq N}}\frac{1}{p}\geq \log\log N-O(\log\log\log N).\tag{3}$$ About that, see Mertens' theorems.

  • 1
    $\begingroup$ This is very interesting but unfortunately well beyond my level. $\endgroup$ – John O'Neil Mar 30 '17 at 14:14

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.