5
$\begingroup$

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense):

$\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n \over k, & \text{if $k | n$} \\ 0, & \text{otherwise} \end{cases} $

for: $1<k \le \lfloor n/2 \rfloor$

Its very simple, so my questions are:

  1. Is it true for all $n$? (I am fairly sure)
  2. What is the proof, if true?

I understand how the primes work (due to $\begin{pmatrix} p \\ k \end{pmatrix} \mod p = 0$ for all: $0<k<n$, but how about composites?

$\endgroup$
  • 2
    $\begingroup$ $\binom{4}{2}=6\equiv 2\mod 4$. However, it is in general true that different combinations from the same row (except the ends) have a gcd greater than 1. $\endgroup$ – Robert Wolfe Jul 16 '14 at 20:29
  • 2
    $\begingroup$ $\binom{14}{4} = 1001 \equiv 7 \pmod{14}$ $\endgroup$ – Daniel Fischer Jul 16 '14 at 20:38
  • 1
    $\begingroup$ $\dbinom{12}{6} = 924 \equiv 0\pmod{12}$ $\endgroup$ – rogerl Jul 16 '14 at 20:39
  • 1
    $\begingroup$ Thanks for the counterexamples, I still find it interesting how a large amount of numbers follow this pattern. $\endgroup$ – Dane Bouchie Jul 16 '14 at 21:04
  • 2
    $\begingroup$ Given $n$, I wonder how many $k$ follow this pattern... That might yield something interesting. $\endgroup$ – apnorton Jul 16 '14 at 21:23
2
$\begingroup$

Kummer's Theorem states that the number of times a prime $p$ divides $\binom{n}{k}$ is equal to the number of carries when $n-k$ is added to $k$. By considering the primes dividing $n$ individually it is easy to see that $\binom{n}{k}$ is divisible by $\frac{n}{\gcd(n,k)}$. This is equivalent to your statement if $n$ and $k$ are relatively prime (about 60% of the pairs). Your statement is also true if $n$ is a product of two primes and $k$ divides $n$ (rare in general, but common for small values of $n$).

$\endgroup$

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.