# 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?

## 1 Answer

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? – Max Mar 24 '17 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. – Ivan Neretin Mar 24 '17 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? – Max Mar 29 '17 at 9:09
• If $\binom nk$ is not squarefree, that is, divides by some square, it can't be the square of $p$. – Ivan Neretin Mar 29 '17 at 9:18
• Thank you for your answer and follow up explanations! – Max Mar 30 '17 at 0:58