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?
$\endgroup$ 42 Answers
$\begingroup$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.
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.
$\endgroup$ 2
