# Finding largest prime factor for checking if a number is squarefree

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?

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$.

• Thanks for your answer, can you expand a bit on the part "Now, when n < p^2", all terms except the first are reduced to 0" - is there an example?
– BMBM
Commented Mar 24, 2017 at 1:10
• What kind of example would you like? If $b>a$, then $a/b<1$, hence $\lfloor a/b\rfloor=0$ - it is as simple as that. Commented Mar 24, 2017 at 5:29
• I understand that part now, thank you. What does "strictly less than 2, so if (nk) happens to not be squarefree, this is not because of p" mean?
– BMBM
Commented Mar 29, 2017 at 9:09
• If $\binom nk$ is not squarefree, that is, divides by some square, it can't be the square of $p$. Commented Mar 29, 2017 at 9:18