1
$\begingroup$

I'm working through questions that I'm not familiar with and would like some help on the following:

If $π(x)$ counts the number of primes less than or equal to $x$, how many primes are there greater than $n$ but less than or equal to $2n$ ?

And if prime $p$ satisfies $n < p ≤ 2n$, what is the largest power of $p$ that divides $2n$ choose $n$ ?

Thanks!

$\endgroup$
4
$\begingroup$

As for the first question, the number of primes less than or equal to $2n$ is $\pi(2n)$ and the number of primes less than $n$ is $\pi(n)$; thus, the number of primes less than or equal to $2n$ but not less than or equal to $n$ is $\pi(2n)-\pi(n)$.


Secondly, recall that ${2n\choose n}=\frac{(2n)!}{n!^2}$. Since $p>n$, we know $p$ cannot divide $n!^2$. Since there's only one multiple of $p$ between $n$ and $2n$ (because $n<p$, we know $2n<2p$), we know $p$ divides $(2n)!$ only once. Thus, $p$ divides ${2n\choose n}$ exactly once.

$\endgroup$
  • $\begingroup$ This helps a lot! I was wondering and also wanted to ask: why is it that n^(𝜋(2𝑛)−𝜋(𝑛)) ≤ (2𝑛 choose 𝑛)? $\endgroup$ – Shanker May 7 at 16:57

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.