2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

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

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.