# Bertrand's Theorem: prime-power decomposition proof

In a book on elementary number theory (pp 177-179, Underwood Dudley 2ed) I am having trouble understanding the following paragraph based on Erdos's proof using Binomial theorem:

"...each prime power in the prime-power decomposition of $N$ is at most $2n$. So if $p$ appears in the prime-power decomposition to be a power greater than 1, then $p^2 \leq 2n$ and $p \leq \sqrt(2n)$.

Where $N=\binom{2n}{n}$.

There are at most $\sqrt(2n)$ such primes, and since each prime power is at most $2n$, their contribution is at most $2n^{\sqrt(2n)}$ "

1) I can see that each prime power is less than $2n$ even from $n!$:

$\color{blue} {20! = 2^{18}3^85^47^211\,13\,17\,19}$

Indeed that is proved earlier in the text, but why for powers greater than 1 is $p^2$ used to show $p \leq \sqrt(2n)$ when the power can be $p^{2n}$?

2) then he says since each prime power is at most $2n$, their contribution is at most $2n^{\sqrt(2n)}$, if the prime power is a maximum of $2n$ and there are $\sqrt(2n)$ of them why would the maximum possible prime-power be raised to the maximum possible number of them to give the maximum possible product of primes greater than power 1 in $N=\binom{2n}{n}$?

• In the first line of your quote, you have "decomposition of $n$." Dudley's book has "decomposition of $N$." You need to sort out your n's before we can even understand your questions. Also, there's a typo in your factoriztion of $20!$. – B. Goddard Feb 24 '18 at 15:04
• okay thanks for pointing that out, where is the error in 20!, I copied it from the book pp 166? – onepound Feb 24 '18 at 19:52
• You have $20^{18}$ instead of $2^{18}.$ And I think people will need to know what $N$ is. – B. Goddard Feb 24 '18 at 20:39

Let $p_i$ represent the $i$th prime dividing $n$ where $i$ is at most $\root \of{2n}$. Each $p_i < 2n$ so $$\prod_i p_i \le \prod_i 2n \le 2n^{\root \of{2n}}$$
As for the reason we only consider $p^2$ is because if we used $p^3$ for example we get $$\prod_i p_i \le 3n^{\root \of{3n}}$$