I was reading Julian Havil’s book Gamma where he talks about a short proof by Paul Erdős on the infinitude of primes.

As I understand it, here are the steps:

(1) Let $N$ be any positive integer and $p_1, p_2, p_3, \dots, p_n$ be the complete set of primes less than or equal to $N$

(2) Each $1 \le x \le N$ can be written as $p_1^{e_1}p_2^{e_2}p_3^{e_3}\ldots p_n^{e_n} \times m^2$ where $e_i \in \left\{0,1\right\}$

(3) So, there are $2^n$ ways of choosing square-free numbers and $m^2 \le N$

(4) Since $m \le \sqrt{N}$, each $2 \le x \le N$ can be chosen in at most $2^n \times \sqrt{N}$ ways.

(5) Thus, $N \le 2^n \times \sqrt{N}$ and $2^n \ge \sqrt{N}$ so that $n \ge \dfrac{1}{2}\log_2 N$

I am confused by step #4. Why does it follow that $x$ can be chosen in at most $2^n \times \sqrt{N}$ ways. I would think that it would be chosen in $2^n \times m^2$ ways. Why is he allowed to replace $m^2$ with $m$ in this case?

Edit: I figured out my misunderstanding.

When I reread the proof in the book this morning, I noticed the following sentence in the paragraph before the proof:

"In 1938 the consummate practitioner Paul Erdos (1913-1996) gave the one that follows, which uses a counting technique and a neat device used by number theorists: that any integer can be written as the product of a square and a square-free integer"

This device is easily proven. Let $u = p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n}$ so that for any $x \le N$, $x = um^2$:

  • Let $p^v | x$ where $p^{v+1} \nmid x$ and $v \ge 1$
  • If $v \equiv 0 \pmod 2$, then $p \nmid u$ and $p^v | m^2$
  • If $v \equiv 1 \pmod 2$, then $p | u$ and $p^{v-1} | m^2$

So that it follows that $m$ is an integer. Now, the full proof works for me.

  • $\begingroup$ Isn't it true that $m$ is not necessarily an integer. For example, if $x=4$, then $m^2 = 2$ In that case, wouldn't there be $m^2$ choices for $m$? I have a feeling that I am missing something obvious. $\endgroup$ – Larry Freeman Jan 23 '15 at 10:54
  • $\begingroup$ @LarryFreeman $m$ is an integer!! That's where the even powers of $p_i$ go. Apparently, your problem was the step 2. $\endgroup$ – user2345215 Jan 23 '15 at 11:01
  • $\begingroup$ Would it be possible to give the page reference for the passage in Havil since it is not in the index? $\endgroup$ – daniel Jan 23 '15 at 12:31
  • 1
    $\begingroup$ Hi Daniel, It is on page 29 of my edition which is in Chapter 3: Sub-Harmonic Series. $\endgroup$ – Larry Freeman Jan 23 '15 at 15:06
  • 1
    $\begingroup$ Just a detail, but shouldn't it be $1\leq x\leq N$? Or there is $2^n-1$ ways to chose a square-free number in (3). This also make more sense in (5). $\endgroup$ – Lehs Jan 24 '15 at 11:19

The number of values $m^2$ can have is given by $m$. If you used $m^2$, it would look as if it could have any value from $1$ to $m^2$, which isn't true.

You "replace" $m^2$ by $m$ in the same sense you replaced $p_1^{e_1}\ldots p_n^{e_n}$ by $2^n$ (and not by $p_1\ldots p_n$).

  • $\begingroup$ Thanks very much! I am almost getting it. I guess I just need to better understand why you replace $m^2$ by $m$. I appreciate your point. $\endgroup$ – Larry Freeman Jan 23 '15 at 10:56
  • 1
    $\begingroup$ @LarryFreeman Think of $x$ as a function $f(e_1,\ldots, e_n, m)$. The number of outputs never greater than the number of inputs. Do you understand now? $\endgroup$ – user2345215 Jan 23 '15 at 10:58
  • $\begingroup$ Thanks! I think that my issue was that I thought $m$ wasn't necessarily an integer. Once I see that it must be an integer, I am clear on your explanation. $\endgroup$ – Larry Freeman Jan 24 '15 at 3:07

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.