Problem 1

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

Problem 1

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

12 posts

#1 h Apr 4, 2025, 3:00 PM

Y by

Prove that
$C(p-1, k-1) \equiv (-1)^{k-1} \pmod{p}$ for $1 \leq k \leq p-1$ , where $C(n, m)$ is the binomial coefficient $n$ choose $m$ .

Z K Y

The post below has been deleted. Click to close.

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

152 posts

KAME06

#2 h Apr 4, 2025, 4:14 PM

Y by

Is that $p$ prime? If the answer is yes:
Case 1: $k=2t+1, t \ge 0$
(1)Then, $\binom{p-1}{(2t+1)-1} = \frac{(p-1)!}{(2t)!(p-2t-1)!} \equiv (-1)^{2t} = 1 \pmod{p} \Rightarrow p \mid \frac{(p-1)!}{(2t)!(p-2t-1)!} -1 = \frac{(p-1)!-(2t)!(p-2t-1)!}{(2t)!(p-2t-1)!}$ , so we must prove that $p$ divides that.
(2)Notice that, by definition of $k$ ; $2t,p-2t-1 <p$ , so $(2t)!(p-2t-1)!$ doesn't have $p$ as a factor. That implies, using (1) and (2):
$p \mid (p-1)!-(2t)!(p-2t-1)!$ (We must prove that).
(3)Claim: $(2t)!(p-2t-1)! \equiv -1 \pmod{p}$ . Demo: By induction on $t$ ...
$t=0$ : Using Wilson Theorem: $(0)!(p-1)!=(p-1)! \equiv-1 \pmod{p}$
If $(2l)!(p-2l-1)! \equiv -1 \pmod{p}$ , notice that $(2l+1)(2l+2) \equiv (p-(2l+1))(p-(2l+2)) = (p-2l-1)(p-2l-2) \pmod{p}$ .
Using that : $-1 \equiv (2l)!(p-2l-1)! \equiv (2l)!(p-2l-3)!(p-2l-2)(p-2l-1) \equiv (2l+1)(2l+2)(2l)!(p-2l-3)!$
$= (2l+2)!(p-2l-3)!=(2(l+1))!(p-2(l+1)-1)! \pmod{p}$ and that ends the induction.
(4)Using (1)-(3) and Wilson Theorem: $(p-1)!-(2t)!(p-2t-1)! \equiv (-1)-(-1) =0 \pmod{p} \Rightarrow p \mid (p-1)!-(2t)!(p-2t-1)! \Rightarrow \binom{p-1}{(2t+1)-1} \equiv (-1)^{2t} \pmod{p}$

Case 2: $k=2t, t > 0$
(1)Then, $\binom{p-1}{(2t)-1} = \frac{(p-1)!}{(2t-1)!(p-2t)!} \equiv (-1)^{2t-1} = -1 \pmod{p} \Rightarrow p \mid \frac{(p-1)!}{(2t-1)!(p-2t)!} +1 = \frac{(p-1)!+(2t-1)!(p-2t)!}{(2t-1)!(p-2t)!}$ , so we must prove that $p$ divides that.
(2)Notice that, by definition of $k$ ; $2t-1,p-2t <p$ , so $(2t-1)!(p-2t)!$ doesn't have $p$ as a factor. That implies, using (1) and (2):
$p \mid (p-1)!+(2t-1)!(p-2t)!$ (We must prove that).
(3)Claim: $(2t-1)!(p-2t)! \equiv 1 \pmod{p}$ . Demo: By induction on $t$ ...
$t=1$ : Using Wilson Theorem: $(1)!(p-2)!=(p-1)! \cdot (-1) \equiv (-1)(-1) =1 \pmod{p}$
If $(2l-1)!(p-2l)! \equiv 1 \pmod{p}$ , notice that $(2l)(2l+1) \equiv (p-(2l))(p-(2l+1)) = (p-2l)(p-2l-1) \pmod{p}$ .
Using that : $1 \equiv (2l-1)!(p-2l)! \equiv (2l-1)!(p-2l-2)!(p-2l-1)(p-2l) \equiv (2l)(2l+1)(2l-1)!(p-2l-2)!$
$= (2l+1)!(p-2l-2)!=(2(l+1)-1)!(p-2(l+1))! \pmod{p}$ and that ends the induction.
(4)Using (1)-(3) and Wilson Theorem: $(p-1)!+(2t-1)!(p-2t)! \equiv (-1)-(1) =0 \pmod{p} \Rightarrow p \mid (p-1)!-(2t-1)!(p-2t)! \Rightarrow \binom{p-1}{(2t)-1} \equiv (-1)^{2t} \pmod{p}$ .

This post has been edited 1 time. Last edited by KAME06, Apr 4, 2025, 4:16 PM

Z K Y

The post below has been deleted. Click to close.

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

Raven_of_the_old

25 posts

Raven_of_the_old

#3 h Apr 4, 2025, 4:32 PM • 1 Y

Y by KAME06

SlovEcience wrote:

Prove that
$C(p-1, k-1) \equiv (-1)^{k-1} \pmod{p}$ for $1 \leq k \leq p-1$ , where $C(n, m)$ is the binomial coefficient $n$ choose $m$ .

Considering p as prime (otherwise it doesn't work as well).
As we very well know
C(p-1, k-1) + C(p-1,k) = C(p,k), hence the result is obvious <3

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a