# Using the fact that any integer can be written as the product of a square and a square free number show that there are infinitely many primes?

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?

• 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. – lulu Mar 30 '17 at 13:26
• To get the upper bound do I use the fact that a^2 divides n? – John O'Neil Mar 30 '17 at 14:46
• 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. – lulu Mar 30 '17 at 14:48
• 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)$ – 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.

• 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? – John O'Neil Mar 30 '17 at 15:30
• $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. – 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.

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