4

Seemingly simple question:

Quote from Wikipedia:

First note that every integer $n$ can be uniquely written as
$rs^2$
where $r$ is square-free, or not divisible by any square numbers (let $s^2$ be the largest square number that divides $n$ and then let $r = n/s^2$). Now suppose that there are only finitely many prime numbers and call the number of prime numbers k.

Fix a positive integer $N$ and try to count the number of integers between $1$ and $N$. Each of these numbers can be written as $rs^2$ where $r$ is square-free and $r$ and $s^2$ are both less than $N$. By the fundamental theorem of arithmetic, there are only $2^k$ square-free numbers $r$ as each of the prime numbers factorizes $r$ at most once, and we must have $s < \sqrt N$. So the total number of integers less than $N$ is at most $2k\sqrt N$; i.e.:

$2^k\sqrt N\ge N.$
Since this inequality does not hold for $N$ sufficiently large, there must be infinitely many primes.

What leads us to say $2^k \sqrt N ≥ N $ in Erdős's proof?

I understand that $2^k$ is the number of combinations and $\sqrt N$ is so that $s^2 < N$, but why do we take the product $2^k \sqrt N$?

Trademark
  • 117
  • 1
    $2^k\sqrt{N}$ was an estimation (non-conservative, i.e. from above) of the numbers of the form $rs^2$ that are $\leq N$, with $r$ square-free. All the numbers $\leq N$ are of that form $rs^2$. Therefore $2^k\sqrt{N}\geq N$, where the $\geq$ accounts for the possibility of having counted a number more than once or having produced more than the numbers $\leq N$. – Nathanson Mar 28 '15 at 21:30
  • The number of choices for $r$ times the number of choices for $s$. – André Nicolas Mar 28 '15 at 21:30
  • 1
    We take the product of $2^k$ and $\sqrt{N}$ in the counting because for each number $rs^2$ we need tho choose the $r$ and the $s^2$. The multiplicative principle of enumerative combinatorics tells us to translate the and as a product. – Nathanson Mar 28 '15 at 21:31
  • 2
    @Nathanson, that stated perfectly how to view that inequality. Thank you. – Trademark Mar 28 '15 at 22:11

0 Answers0