Divisibility of Binomial Differences

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Divisibility of Binomial Differences

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: SAMO 2016 Q6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

445 posts

djb86

#1 h Sep 24, 2016, 10:44 AM • 1 Y

Y by Adventure10

Let $k$ and $m$ be integers with $1 < k < m$ . For a positive integer $i$ , let $L_i$ be the least common multiple of $1,2,\ldots,i$ .
Prove that $k$ is a divisor of $L_i \cdot [\binom{m}{i} - \binom{m-k}{i}]$ for all $i \geq 1$ . [Here, $\binom{n}{i} = \frac{n!}{i!(n-i)!}$ denotes a binomial coefficient. Note that $\binom{n}{i} = 0$ if $n < i$ .]

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2541 posts

#2 h Sep 24, 2016, 2:17 PM • 2 Y

Y by Adventure10, Mango247

Just show $n(n-1)\cdots (n-i+1)\equiv (n-k)(n-1-k)\cdots (n-i+1-k)\text{ (mod }k\cdot\frac{i!}{L_i})$
Which can be done by considering prime parts.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a