$2n\choose n$ is divisible by all the primes between $10$ and $30$.

Question

Find the smallest positive integer $n$ such that $2n \choose n$ is divisible by all the primes between $10$ and $30$.

Answer 1

Legendre's Criterion states that $v_p(n)=\dfrac{n-s_p(n)}{p-1}$ where $s_p(n)$ is the sum of the digits of $n$ written in base $p$. Proving this is just algebra after you write out $n$ in base $p$.

Applying this, we see we simply need $2s_p(n)>s_p(2n)$ for all these primes. If we don't get into squares of these primes, this means that $\lfloor \dfrac{2n}{p}\rfloor$ needs to be odd. There doesn't seem to be a nice way to check this however, so we use brute force:

For $p=29$ we need $n\ge 15\ge 11$, so we need another power of $11$ on the top, giving $2n\ge 33\Rightarrow n\ge 17$. This means we need another power of $17$ on the top, giving $2n\ge 51\Rightarrow n\ge 26$. Thus we need another power of $23$ (and $29$ of course) so we end up with $2n\ge 87\Rightarrow n\ge 44$. Then we need another power of $11$ so we get $2n\ge 100\Rightarrow n\ge 50$, which unfortunately fails for $p=23$.

Darn. Looks like we have to keep going. Repeating this process we eventually get $2n\ge 222\Rightarrow n=111$, which works! (I think...did this all by hand)

Note that the process gets marginally easier as we get larger since we get squares on the top for the smaller primes. But it's still very bashy and I doubt there's a much better way to do this by hand.