2
$\begingroup$

To analyze questions like this

On variations of Erdős squarefree conjecture: presentation and a question as a simple case

it would be nice to have a simple criterion when $\binom{n}{m}$ is divisible by $q^2$, when $q$ is a prime and $n>m>1$ integers. We can assume $2m\le n$. Maybe creating pascal's triangle modulo $q^2$ gives a structure.

Does anyone know a criterion that is easy to check without calculating the binomial coefficient ?

$\endgroup$
  • 2
    $\begingroup$ Count the number of factors $q$ in both $n!$ and $m!(n-m)!$ is what I'd do $\endgroup$ – vrugtehagel Apr 5 '18 at 7:31
  • $\begingroup$ @vrugtehagel And to do that, I just have to add the $p$-adic valuations with respect to $q$, right ? $\endgroup$ – Peter Apr 5 '18 at 7:32
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Kummer%27s_theorem $\endgroup$ – Lord Shark the Unknown Apr 5 '18 at 8:02
  • 3
    $\begingroup$ Kummer's theorem - Just count the number of carries when you add $m$ to $n-m$ in base $q$. If it has two or more carries, then $q^2| \binom{n}{m}$. $\endgroup$ – achille hui Apr 5 '18 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.