Finding largest prime factor for checking if a number is squarefree

Question

I'm working on project Euler problem 203 that reads like this:

[...]

A positive integer n is called square-free if no square of a prime divides n. Of the twelve distinct numbers in the first eight rows of Pascal’s triangle, all except 4 and 20 are square-free.

[...]

Find the sum of the distinct square-free numbers in the first 51 rows of Pascal’s triangle.

I basically understand how to solve this, what was bugging me was how to find the largest prime factor that I need to check against.

I found online a solution that says:

Only a few primes are required. For example, $51!$ is the biggest numerator $(\binom{n}{k} = \frac{n!}{k! (n-k)!} )$ and the largest prime factor required is $≤ √51$ which is 7.

Why does this work - how can I know that I only need to check divisibility by prime number squares up until $7^2$? The next prime number is 11, so how would I know that I don't need to check the numbers of pascals triangle against e. g. $11^2$, $13^2$, etc. given that I only need to check the numbers up until row 51 of pascals triangle?

Answer 1

As with every PE problem, this is true because when you compute your answer using this and enter it on a certain website, you see that victorious guy proudly brandishing a green sign.

Seriously, the highest power of a prime $p$ dividing $n!$ is $$\left\lfloor{n\over p}\right\rfloor+\left\lfloor{n\over p^2}\right\rfloor+\left\lfloor{n\over p^3}\right\rfloor+\dots$$ Now, when $n<p^2$, all terms except the first are reduced to $0$. The same applies to the smaller factorials of $k$ and $n-k$, so the power of $p$ in $\binom nk$ is simply $$\begin{aligned} \left\lfloor{n\over p}\right\rfloor-\left\lfloor{k\over p}\right\rfloor-\left\lfloor{n-k\over p}\right\rfloor & = \left({n\over p}-\left\{{n\over p}\right\}\right)-\left({k\over p}-\left\{{k\over p}\right\}\right)-\left({n-k\over p}-\left\{{n-k\over p}\right\}\right) \\ & = \left({n\over p}-{k\over p}-{n-k\over p}\right)+\left(\left\{{k\over p}\right\}+\left\{{n-k\over p}\right\}-\left\{{n\over p}\right\}\right) \\ & = \left\{{k\over p}\right\}+\left\{{n-k\over p}\right\}-\left\{{n\over p}\right\} \\ & \leqslant\left\{{k\over p}\right\}+\left\{{n-k\over p}\right\} \\ & \color{red}{\mathbf<\ 1+1=2} \end{aligned} $$ i.e., strictly less than 2, so if $\binom nk$ happens to not be squarefree, this is not because of $p$.